18-01-2013, 02:40 PM
Closure Properties of Regular Languages
Closure Properties.pdf (Size: 44.79 KB / Downloads: 282)
Non-deterministic Finite Automata
• A non-deterministic finite automaton (NFA) is a generalization of DFA with the fol-
lowing two changes:
– In DFA for each pair (q, a) with q 2 Q, q 2 , the transition function gave
exactly one next state. In NFA, for each pair (q, a) the transition function may
give 0, 1, or more than one next states.
0 next states – (q, a) is not defined.
In this case, if the NFA is in state q and receives input symbol a, it will reject
the rest of the input, regardless of what it is (it “dies”). This is similar to
going into a trap state.