自然言語処理 - nofx @Wiki

有限オートマトン

１．有限個の状態の集合　Ｋ
２．有限個の入力アルファベット　Σ
３．遷移の集合δ+開始記号　Ｓ（Ｓ∈Ｋ）
４．最終状態の集合　Ｆ（Ｆ⊆Ｋ）

有限オートマトン　Ｍ＝（Ｋ，Σ，δ，Ｓ，Ｆ）

形式文法

１．非終端記号の集合　Ｎ
２．終端記号の集合　Σ
３．生成規則（書き換え規則）　Ｐ
４．開始記号　Ｓ

形式文法　Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）

正則文法（正規文法）（regular grammer : RG）

形式文法　Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）のうち生成規則Ｐが次の形になっているもの。
●Ａ→ａＢ　　　　もしくは
●Ａ→ａ
開始記号Ｓについては
●Ｓ→ε
ただし、　　Ａ，Ｂ∈Ｎ，　　ａ∈Σ

正則文法は３型文法とも呼ばれる。

文脈自由文法（context-free grammer : CFG）

形式文法　Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）のうち生成規則Ｐが次の形になっているもの。
●Ａ→α　　（　Ａ∈Ｎ，　α∈（Σ∪Ｎ）*　）

文脈自由文法は２型文法とも呼ばれる。


プログラミング言語は文脈自由文法で生成できる。
→　ある条件を満たす文脈自由文法　：　ＬＬ（１）文法

チョムスキー標準形（Chomsky normal form : CNF）

形式文法　Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）のうち生成規則Ｐが次の形になっているもの。
１．Ａ→ＢＣ　　（　Ａ，Ｂ，Ｃ　∈　Ｎ　）
２．Ａ→ａ　　　（　ａ∈Σ　）
３．Ｓ→ε

グライバッハ標準形（Greibach normal form : GNF）

形式文法　Ｇ＝（Ｎ，Σ，Ｐ，Ｓ）のうち生成規則Ｐが次の形になっているもの。
１．Ａ→ａＢ1Ｂ2…Ｂm　　（　ａ∈Σ、　　　Ｂ1，Ｂ2，…，Ｂm　∈　Ｎ　）
２．Ａ→ａ　　　（　ａ∈Σ　）
３．Ｓ→ε

s文法

１．生成規則の右辺は終端記号で始まる
２．生成規則の左辺が同じなら右辺は異なる終端記号で始まる

• LL(1)文法