Chapter 3 - Finite Automata

Question 1

What is a DFA (include all features of a DFA)

Answer 1

A finite set of states - Q
A finite set of input symbols, the alphabet (sigma)
A transition function (used to go between states)
An initial state Q0
A set of final states F (subset of set of states - Q)

Question 2

What does this mean? Delta D (Q0, 0) = Q1

Answer 2

Go from state 0 to state 1 if the input is 0

Question 3

How does a DFA reject/accept words?

Answer 3

Rejection - the word doesn’t finish in a final state
Acceptance - the word does finish in a final state

Question 4

What is the difference between a DFA and an NFA?

Answer 4

NFAs can have multiple starting states, whereas DFAs can only have one
NFAs can also have a ‘choice’ between states it transitions to

Question 5

How do you follow through a NFA?

Answer 5

When going from one state to another, you ‘split’ the path, and follow both. If one of those states eventually finishes on a final state for the last character of the word, then it will be ‘accepted’

Question 6

When following through an NFA, what happens if you have another character for your word, and you can’t go anywhere?

Answer 6

You ‘lose’ that state i.e. you cannot go from there, so you wipe it out

Question 7

How would you go about converting an NFA to a DFA?

Answer 7

Look at each connection, and then turn them into little ‘sets’ i.e. if a state q0 links to q1 and q0 through the character 0, then the set q0,q1 is now a node for the DFA which is reached using 0 from q0.
If a connection isn’t present i.e. the node cannot link to another node using a character, then link it to a theta state.
(If this doesn’t make any sense, look at page 22)