Finite Automata

State diagram

State table

$q$	$σ$	$δ (q, w)$
$q_{0}$	$0$	$q_{1}$
$q_{0}$	$1$	$q_{0}$
$q_{1}$	$0$	$q_{2}$
$q_{1}$	$1$	$q_{0}$
$q_{2}$	$0$	$q_{2}$
$q_{2}$	$1$	$q_{0}$

DFA & NFA

DFA

DFA: Deteministic Finite Automata

A finite automata $M = (K, Σ, δ, s, F)$

$K$ : a finite set of states.
$Σ$ : input alphabet.
$δ$ : the transition function, is a function from $K \times Σ$ to $K$ .
$s \in K$ : inital state.
$F \subseteq K$ : a set of final state.

$⊢_{M}$ and $⊢_{M}^{*}$ is different:

$(q, w) ⊢_{M} (q^{'}, w^{'})$ : an edge from q to q'
$(q, w) ⊢_{M}^{*} (q^{'}, w^{'})$ : a path from q to q'

M

accepts

w \in Σ^{⋆}

(s, w) ⊢_{M}^{*} (q, e)

for some

q \in F

说人话，就是输入纸带后，若能从初始状态到达指定的结束状态，就接受该纸带输入。

$L (M) = {w \in Σ^{*} : M a c c e p t s w}$ , thus $M$ accepts $L (M)$ (unique).

NFA

NFA: Non-deteminstic Finite Automata

traits
- several choices for the next state（同样的输入有多种路径）
- e-transition (不读入的情况下改变状态)
strict definition: A NFA is 5-tuple $M = (K, Σ, Δ, s, F)$ ， $Δ \subseteq K \times (Σ \cup {e}) \times K$
the defination of $⊢_{M}$ , $⊢_{M}^{*}$ and acceptance rule is same with DFA

The NFA always make the right guess if possible.

如果 NFA 在当前输入下有机会到达最终态，它一定会到达最终态。

Any NFA M always can be transformed to a DFA M' with

L (M^{'}) = L (M)

为解决不读入情况下的状态转移，引入符号 $E$ ：for $q \in K$ let $E (q) = {p \in K : (q, e) ⊢_{M}^{*} (p, e)}$ .
NFA $M = (K, Σ, Δ, s, F)$ -> DFA $M^{'} = (K^{'}, Σ, δ, s^{'}, F^{'})$

$K^{'} = 2^{k} = {Q : Q \subseteq K}$
$F^{'} = {Q \subseteq K : Q \cap F \neq \emptyset}$
$s^{'} = s$
for $Q \subseteq K$ and $a \in Σ$ , $δ (Q, a) = ⋃_{q \in Q} E ({p : (q, a, p) \in Δ}) = ⋃_{q \in Q} ⋃_{p : (q, a, p) \in Δ} E (p)$