Nondeterministic Finite Automaton (NFA) Graph with start state, final states, edges labeled by symbols (like DFA) but – Not required to have exactly 1 edge out of each state labeled by each symbol - can have 0 or >1 – Also can have edges labeled by empty string Definition: x is in the language recognized by an NFA iff x labels a path from the start state to some final state Autumn 2012CSE 311 18 s0s0 s2s2 s3s3 s1s1 111 0,1
{}