The Final Iteration

Question 1

What is a transition table?

Answer 1

A transition table is used when creating a DFA. States the connections between the different states, as well as what that connection requires to be ‘crossed’

Question 2

What are some general ‘practices’ when creating DFAs?

Answer 2

(0,a),1 - means going from state 0 to state 1 if the character is a.
Multiple of three - create a triangle pattern, whereby the character required connects the three points
Evens and odds - use a ‘pair’ formation i.e. a path above for evens, and a path below for odds, with crossover when the character amount changes

Question 3

When told to ‘calculate’ something for a DFA, what does it actually mean?

Answer 3

It means just follow through the DFA until you terminate either successfully or not, and show your steps taken.

Question 4

When describing a language, what sort of things should you be looking for?

Answer 4

Look for patterns, such as multiples of a character or palindromes or equal amounts of letters. Anything that appears as a ‘regular’ occurrence

Question 5

How would you go about minimising a finite automata?

Answer 5

Use the table filling algorithm:
Take all the nodes and write them across in ascending order (except the last one), then take all the nodes and write them down the side in descending order (except the last one). Any pair that has one final state (not BOTH), cross off. Then, for the remaining pairs, ‘explore’ their connections. If the resulting pairs have only one final state in them, then cross off the original pair, as they are distinguishable. Otherwise, if they equal another pair that has not been crossed off, then add them below that pair. Once fully finished, if there are any pairs that are unmarked, then ‘overlap’ them and their connections.

Question 6

How do you convert from an NFA to a DFA?

Answer 6

Using the subset construction method:
Take all the initial states, and start to write their connections which they make using certain characters e.g. state 0 can go to itself and state 1 through a.
Once you have exhausted all possibilities, simply connect everything in a new DFA. Any set that includes a final state is now a final state in the new DFA, and is marked by an outgoing arrow.

Question 7

What are some general practices when creating regular expressions?

Answer 7

At most, one letter - (x+epsilon)
Any number of letter/s - (x)*
At least one letter - x(x+y)*
At most one letter - x(y+z)*
Ensuring a certain sequence - xyyx(x+y)*

Question 8

What does plus mean in regular expressions?

Answer 8

Plus is treated as an OR symbol. If used, you can pick either one or the other, you cannot have both. If an even arises like this - x(y+z)*, you can have xy, xz, but not xyz.

Question 9

What is a CFG?

Answer 9

CFG is defined by a set of nonterminals, a set of terminals, a start symbol and a production defining how to create a word.

Question 10

What does it mean by ‘left-linear’ and ‘right-linear’ for CFGs?

Answer 10

Left-linear - all productions are left-recursive
Right-linear - all productions are right-recursive

Question 11

What is a derivation tree?

Answer 11

A derivation tree dictates how a word has been created based on the steps through the production.

Question 12

How can a CFG be ambiguous?

Answer 12

When a CFG can produce the same word, but with two or more different ways, then it is ambiguous
(a problem with this is that if you want to assign words value, then multiple ways of creating the word causes issues with that)

Question 13

How can CFGs be equivalent?

Answer 13

CFGs can be equivalent when they both represent the same language

Question 14

What does it mean by ‘Elimination of Useless/Unreachable Productions’?

Answer 14

Any production that cannot be reached by any other nonterminal is useless, and therefore can be removed.
Any production that causes an infinite loop i.e. there isn’t an end condition or any way to get to one, is considered a useless/unproductive nonterminal, and thus can be removed.
When removing a production, you take out EVERYTHING it is associated with i.e. there is plenty of collateral damage. Example - S -> AB | a | b
If B is marked for removal, then it will look like this:
S -> a | b

Question 15

What does it mean by ‘Substitution’?

Answer 15

Exactly as it sounds. Take a production, and wherever it occurs, replace it with it’s results i.e. A -> XBY & B -> C | D | epsilon
This would turn into:
A -> XCY | XDY | XY

Question 16

What does it mean by ‘Left Factoring’?

Answer 16

Find a common prefix (or pattern) within a production, and replace it with a new production that takes its place. Example:
A -> XYYX | XYZZY
Would become this:
A -> BYX | BZZY
B -> XY

Question 17

How can you make a CFG unambiguous?

Answer 17

Use operator precedence and operator associativity.
Highest precedence goes at the end of the ‘chain’
Wherever the associativity points to, that is where the old ‘link’ goes. The next step in the chain takes the other place. If the associativity is ‘neutral’, then the next ‘link’ takes both spots. If there is no associativity, then only the next element in the chain appears.

Question 18

What is ‘Elimination of Left Recursion’?

Answer 18

Anything that has left recursion, you mark. Within that nonterminal, anything that doesn’t have left recursion, you simply keep and put nonterminal’ on its right hand side. Anything that did have left recursion, you will move down to the nonterminal’ production, and put the rest of the original production, followed by the original nonterminal on its right hand side. After all this is done, you add epsilon to the end of the nonterminal’.
Example:
A -> ABc | a | aa
Becomes:
A -> aA’ | aaA’
A’ -> BcA | epsilon

Question 19

What is a pushdown Automata?

Answer 19

A pushdown automata is basically an NFA, except with a stack added on.

Question 20

What is each connection’s structure and what does it mean?

Answer 20

Three parts to it - x, z, xz
x - the character being read
z - the element on the stack (left most side)
xz - The new result of the stack after ‘crossing’ the connection
After ‘crossing’ the original character that had been read is now removed from the original word.

Question 21

What are IDs?

Answer 21

IDs are the ‘formal’ way of ‘crossing’ over connections. General format - (state you’re in, the rest of the word to be processed, the stack contents)
It takes a ‘snapshot’ after each step has been made and records it in the format above.

Question 22

What is an ID sequence?

Answer 22

An ID sequence is multiple IDs linked in a row

Question 23

What are the two ways a PDA can accept a word?

Answer 23

Acceptance by final state - finishes executing within a final state, doesn’t use the stack contents to determine result
Acceptance by empty stack - can terminate anywhere, uses the stack to determine result

Question 24

How do you create a PDA from a CFG?

Answer 24

For each production, you want to take each option and put them in a single ID ‘set’. Example:
E -> T | E+T
Would be represented as:
(q0, epsilon, E) = {(q0, T), (q0, E+T)}
However, there are exceptions:
Any character that appears, or a symbol, will be represented as above like normal, but they will also have their own ID displayed in the general format below:
(current state, character/symbol, character/symbol) = (current state, epsilon)

Question 25

What are the two strategies for parsing?

Answer 25

Top-down - attempts to carry out a derivation matching the input starting from the start symbol
Bottom-up - tries to construct the parse tree from the leaves upwards by using the productions ‘backwards’

Question 26

How do you calculate the first set?

Answer 26

Take nonterminal
For each production from the nonterminal, you take the first leftmost character and add it to the set. If that character happens to be a nonterminal, then follow it down and repeat the first step.
Disregard any duplicate elements

Question 27

How do you calculate the follow set?

Answer 27

Find the production
Go back a step to where it was previously mentioned in any production.
Anything past it you take the first set of (minus epsilon). If it is a character, then just add it to the follow set. If there is nothing past the instance of the nonterminal, then you add the follow set of the nonterminal you are currently in (usually is S)

Question 28

How do parsers deal with choice?

Answer 28

Full, or partial, backtracking (computationally expensive, not ideal)
Partial Lookahead - makes an informed decision based on the next x characters

Question 29

What are nullable nonterminals?

Answer 29

Anything that can lead to an epsilon, or lead to a nonterminal which can lead to an epsilon.

Question 30

What is a Turing Machine?

Answer 30

A Turing Machine is like a PDA, except instead it has a tape rather than a stack

Question 31

How are connections structured as within a Turing Machine?

Answer 31

General format - x, y, D
x - the character being read
y - the symbol to replace x with
D - the direction the tape rotates (either left or right)

Question 32

How does a Turing Machine connection look in ‘formal speak’?

Answer 32

Two elements - (state currently in, the symbol to be read from the word)
This then transitions to a new format, after ‘crossing’ the connection:
Three elements - (new state, the character that will replace it, and the direction the tape rotates in)

Question 33

How are IDs represented in Turing Machines?

Answer 33

Almost the same as normal ID format, but changes are as follows:
Character being held on the tape, the current state you’re in, and the rest of the word that has yet to be processed