Finite Automata

DFA

$$\begin{array}{rl}& \text{Finite Automaton}=(Q,\Sigma ,\delta ,q_0,F)\\ & \text{where:}\\ & Q\text{ is a finite set of states}\\ & \Sigma \text{ is a finite set of symbols called the alphabet}\\ & \delta :Q\times \Sigma \to Q\text{ is the transition function}\\ & q_0\in Q\text{ is the start state}\\ & F\subseteq Q\text{ is the set of accept states}\end{array}$$

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

3. For the new DFA D'
   • The start/accept state S' contain the original start/accept state
   • Every set of state is a new state

Links

• Regular Expression