NFAs

Question 1

Difference between DFA and NFA

Answer 1

In a NFA there can be more than one choice from the same input e.g. input ‘a’ has two transitions. Also some states have no outgoing transitions whereas in DFA each state has exactly one transition per input

Question 2

In an NFA how do you choose which path to take

Answer 2

Work out if the string is accepted for all paths and if it is accepted for at least one then the string is accepted even if all other paths are rejected

Question 3

An NFA accepts a string if:

Answer 3

If there is at least one computation of the NFA that accepts the string

Question 4

If there is still string left over after reaching an acceptance state with no transitions is it accepted or rejected

Answer 4

Rejected

Question 5

An NFA rejects the string if:

Answer 5

For each computation:

The entire input string is consumed and the last state is not an accepting state

OR

The input string cannot be scanned entirely/the input cannot be consumed

Question 6

What is the epsilon transition (ε)

Answer 6

The transition happens without reading an input. If there is a ε transition from q1 to q2, the NFA can decide whether to stay at q1 or jump to q2

Question 7

what does L = {ab}^+ mean

Answer 7

L = {ab,abab,ababab, …}

Question 8

What does L = {ab}^* mean

Answer 8

L = {empty string, ab, abab, ababab, …}

Question 9

Formal definition of NFA’s, give the states symbols and definitions

Answer 9

Question 10

what does the set Delta(q,x) contain

Answer 10

All the states you can reach from the transition x from q, including states which you can get to via an x and epsilon transition

Question 11

What is the extended transition function

Answer 11

deltaHat({q0},aa) gives the set of states where the NFA can end up after the transition aa

Question 12

How is extended transition function different to normal transition function

Answer 12

Extended transition function takes a string of multiple transitions

Question 13

Machine m1 is equivalent to machibe m2 if?

Answer 13

They have the exact same language

Question 14

If an NFA has k states what is the most states the DFA can have

Answer 14

2^k

Question 15

When converting from an NFA TO A DFA how are the states labeled in the DFA

Answer 15

In the DFA, every state is a set

Question 16

Convert this NFA to a DFA

Answer 16

Question 17

For any DFA state, if at least one state in the set is an accepting state in the NFA then…

Answer 17

That set is an accepting state in the DFA