DFA

NFA

  • multiple paths possible (0, 1 or many at each step)
  • ε-transition is a “free” move without reading input
  • Accept input if some path leads to accept state
  • Useful Mathematically

Conversion

Regexp to NFA

  • regex
  • Thompson Construction

NFA to DFA

  • subset construction
    • Epsilon Closure

Minimize DFA

  1. Divide the states into two sets. One contain all accepting states and other contain non-accepting states.
  2. Construct new set based on
while S is changing
	forEach group G of S:
		partition G -> two states are in the same subgroup iff forAll input symbols they transition to the same group
		replace G by the set of all subgroups formed
  1. For the new DFA D'
    • The start/accept state S' contain the original start/accept state
    • Every set of state is a new state