Finite Automaton=(Q,Σ,δ,q0,F)where:Q is a finite set of statesΣ is a finite set of symbols called the alphabetδ:Q×Σ→Q is the transition functionq0∈Q is the start stateF⊆Q is the set of accept states
NFA
multiple paths possible (0, 1 or many at each step)
ε-transition is a “free” move without reading input
Divide the states into two sets. One contain all accepting states and other contain non-accepting states.
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
For the new DFA D'
The start/accept state S' contain the original start/accept state