Week 1 - NFA vs DFA Flashcards
TRUE OR FALSE: There can only exist one machine for each language.
FALSE, there can be multiple machines for one language.
What does it mean if two machines are equivalent?
The two machines recognise the same language.
TRUE OR FALSE: Every NFA has an equivalent DFA for its language.
TRUE, there is an equivalent DFA for each NFA. An NFA can be converted to a DFA too.
How do you convert a NFA to a DFA?
Long answer
You get all the subsets of the set of all states of the NFA (Including an empty subset). Draw out the subsets. The initial state of the DFA will normally be the subset that only has the initial state within it. Start there. For each symbol in the alphabet, draw a transition to the state that it transitions to in the NFA. If it does not have a transition in the NFA, then draw a transition to the empty subset. Next you repeat for the each state you arrived at. If in the NFA a symbol has multiple transitions, then you draw a transition to the subset that has all the states that that symbol could transition to from the current state. For subsets that have multiple states in them, you consider all states transitions and draw the transition to the subset with all states that all state from the current subset could transition to for this symbol. Repeat thes steps until all subsets have transitions.
The final states of this DFA will be any and all subsets that contain the final state of the NFA.
Any state that has no transition to it, and cannot be reached can be taken out of the DFA for simplification.
Then you have your DFA of an NFA.
What happens if there is an Ɛ in a NFA when you are converting to a DFA?
Any state that transitions to the state that has an Ɛ transition out of it, will transition to the subset of states that includes the state it will transition to and the state that the Ɛ transition goes to.
What happens if the initial state of an NFA has an Ɛ transition in it when converting to a DFA?
The initial state of the DFA is no longer the subset that only contains the initial state, but is now the subset of states that contains the initial state of the NFA and the state that the Ɛ transition(s) go(es) to.
TRUE OR FALSE: A language is only regular if and only if some NFA recognises it.
TRUE.
