Converting between DFA and NFA

Math for CS · Axiom Academy

Nondeterminism, epsilon-transitions, and subset construction Nondeterministic Finite Automata (NFA) An NFA relaxes the DFA's rules in two ways: Multiple transitions: From a state, on a given symbol, the machine may have 0, 1, or many possible next states -transitions: The machine can change state without reading any input symbol — transition function returning a set of states The NFA accepts a string if there exists some sequence of transitions leading to an accept state. It rejects only if every possible path leads to rejection. Design an NFA over that accepts strings containing the substring "01". The nondeterminism is at state q_0 on input 0: the NFA "guesses" whether this 0 is the start of the pattern "01". If it guesses right, it reaches q_2 and accepts. An -transition lets the NFA move to a new state without consuming any input. This is useful for combining smaller NFAs. Subset Construction: NFA → DFA The remarkable theorem: NFAs and DFAs recognize exactly the same class of languages. We can convert any NFA to an equivalent DFA using the subset construction . — states of D are sets of NFA states — start with -closure of NFA start — accept if any NFA state in the set is accepting Subset Construction: Worked Example Convert the "contains 01" NFA to a DFA. NFA transitions (no -transitions in this example): Build DFA states (each is a subset of ): The resulting DFA has 4 reachable states (out of 2^3 = 8 possible subsets). States containing q_2 are accept states.

This is the written version of the interactive lesson above. See the full Math for CS course.