4. Review DFA & NFA

13/02/23

	DFA	NFA
States	00000	00000
Initial State	1	Several
Transition	For every state, there is exactly 1 condition for each symbol	Several or none
Final State	Several or none	Several or none
Run	One (initial)	Several
Language	The token in final state	A token in a final state

Maths

	DFA	NFA
States	Q a finite state	Q a finite state
Initial State	$q_0:Q$	$S : Q\to prop$
Transition	$δ:Q\to\Sigma\to Q$	$δ:Q\to\Sigma\to Q \to prop$
Final State	$F:Q\to prop$	$F:Q\to prop$
Run	$??:Q\to\Sigma*\to Q$	$??:Q\to\Sigma*\to Q \to prop$
Language	The token in final state	A token in a final state

Theorem 1 (Easy)

For every DFA A there is a NFA NA that accepts the same language $LA=L(NA)$ Needs a lemma $NA = (Q,\Sigma,δ_N$ $S_N g * g' = (δqx=q')$ $S q = (q=q_?)$

Theorem 2

For every NFA $A=(Q,\Sigma,δ,S,F)$ there is a DFA DA that recognises the same language $LA=L(D(A))$ $PQ=Q\to prop ~ Q\to Bool$