オートマトン

自分用オートマトンメモ

決定性有限オートマトン

　　　　　↓　拡張

非決定性有限オートマトン

　　　　　↓　拡張

ε遷移付非決定性有限オートマトン

拡張しても、識別能力（受理する言語）は一緒←ポイント

L(dfa) = L(nfa) = L(ε-nfa)

有限オートマトンは

M = < Q , Σ , δ , q₀ , F >

の5字組みであらわす事ができる

Q：　状態の有限集合

Σ：　入力記号の有限集合

δ：　動作関数（ δ ： Q × Σ → Q ）

q₀： 初期状態

F：　受理状態の有限集合

有限オートマトンは正規表現を受理する

（ε-）nfa M_n から dfa M_n を構成するアルゴリズムがちゃんとある

最簡形→同じ言語を受理する決定性有限オートマトンで一番簡単なやつ

次の授業は、スタックをもつプッシュダウンオートマトンについて