形式言語

　もとになる記号の集合（アルファベット）と，生成規則（文法）から，生成することの出来る文字列（言葉）の集合を形式言語（formal language）と呼ぶ。 プログラミング言語などをモデル化したもの。 〜人工言語⇔自然言語

文法（Grammer）言語（Language）受理するオートマトン（Automaton）
正規文法
（Regular Grammer）		正規言語（３型）有限オートマトン
（Finite Automaton）
文脈自由文法
（Context Free Grammer）		文脈自由言語（２型）プッシュダウンオートマトン
（Push Down Automaton）
文脈依存文法
（Context Sensitive Grammer）		文脈依存言語（１型）線形有界オートマトン
（Linear Bounded Automaton）
無制約文法（句構造文法）句構造言語（０型）チューリングマシン
（Turing Machine）

　形式言語に関してはこちら

オートマトン

　オートマトンＡの入力記号で作られる入力系列ｗ を、その初期状態から加えたとき、 Ａが最終状態になるならば、オートマトンＡは入力系列ｗ を受理する（accept）という。 そうでないときには、Ａはｗ を受理しない・拒否する（reject）という。 系列の集合Ｌが与えられたとき、オートマトンＡがその集合に属する系列を全て受理し、それ以外のものを受理しないとき、Ａは集合Ｌを受理するという。

オートマトン（Automaton）オートマトンの構造
有限オートマトン
（Finite Automaton）		FA
プッシュダウンオートマトン
（Push Down Automaton）		FA＋スタック
線形有界オートマトン
（Linear Bounded Automaton）		FA＋入力と同じ長さのテープ
チューリングマシン
（Turing Machine）		FA＋テープ

有限オートマトン

　Ｍ＝（Ｑ、Σ、δ、ｑ0、Ｆ）

正規言語

　正規表現（regular expression）として知られる言語。 　　によって表される言語。

正規表現と言語と有限オートマトン

正規表現 = 言語 受理するＦＡ
a = {a}

入力列：
ab = {ab}

入力列：
a|b = {a, b}

入力列：
(a|ab)(a|b) = {aa, ab, aba, abb}
　　　　　　　　　　NFA　　　　　　　　　　　　　　　　　DFA

入力列：
ab* = {a, ab, abb, abbb, ... }

入力列：
c(a|b)* = {c, ca, cb, caa, cbb, ... }

入力列：

正規表現からDFAへ

NFAからDFAへ

　 定理：LをNFAで受理される集合とする。このとき、Lを受理するDFAが存在する。


ε動作を含むNFAからε動作を含まないNFAへ

　 定理：Lがε動作を含むNFAで受理されるならば、Lはε動作を含まないNFAでも受理することができる。


正規表現からε動作を含むNFAへ

　 定理：与えられた正規表現 r に対して、L(r) を受理するε動作を含むNFAが存在する。


DFAから正規表現へ

　 定理：LがDFAで受理されるならば、Lは正規表現で表される。 （これも帰納法で証明することができる。）


戻る