うさぎでもわかるオートマトンと言語理論　第07羽　文脈自由文法

こんにちは、ももやまです。

今回はオートマトンと言語理論の中でも重要な文脈自由文法についてまとめていきたいと思います。

１．文脈自由文法とは
２．文脈自由文法の読み方
３．特別な文法・標準形
４．練習問題
- 練習
５．練習問題の答え
６．さいごに

前回の記事の内容（Myhill-Nerodeの定理・正則ではない言語の証明法）はこちら↓

www.momoyama-usagi.com

１．文脈自由文法とは

文脈自由文法は、以下の4つの要素で構成されるような文法を表します。
（出発記号 $S$ 以外はすべて集合です。）

f:id:momoyama1192:20190906161600g:plain

非終端記号（変数） $N$

後ほど説明する生成規則 $P$ によって書き換えることができるような文字（記号）の集まりを表します。基本的に $S$ , $A$ , $B$ などの大文字が使われます。

終端記号 $\Sigma$

それ以上書き換えることができない文字の集まりです。

生成規則 $P$

1文字の終端記号を終端記号と非終端記号が組み合わされた複数の記号に変換するためのルール（置き換えルール）の一覧が書かれています。

生成規則は「○は□△である」のルールが集まっているものだと考えてください。

出発記号 $S$

文法解析の出発記号（非終端記号の1つ）を表します。
最初に置き換える記号です。

文脈自由文法を用いることで、正則言語よりも多くの文法、言語を表現することができます。また、多くのプログラミング言語の文法は文脈自由文法で構成されています。

２．文脈自由文法の読み方

では、実際に文脈自由文法を読み取る練習をしてみましょう。先ほどの文法\[
G = \left( \{S,A,B\}, \{a,b\}, P,S \right)
\\ P = \{ S \to AB, \ A \to a, \ A \to aAa, \ B \to b, \ B \to bBb \}
\]はどんな文法なのかを調べてみましょう。

(1) 文字列の導出の方法

まずは、文字列がどのように導出されるかについて説明してみましょう。

文脈自由文法を導出する際には出発記号 $S$ から生成規則（変換ルール）を連鎖的に適用していきます。

例えば、 $abbb$ を導出する場合、下のように4回生成規則を適用することで文字列を導出することができます。

f:id:momoyama1192:20190906161606g:plain

(2) 最左導出・最右導出

導出の際に「テキトーに非終端記号選んで置き換えちゃえ！☆ヾ(￣￣*)えいっ」とやるのは受理する文字列の列挙忘れの原因になったりします。

なので、実際に受理する文字列を列挙する際には左から優先的に非終端記号を変形していく最左導出、もしくは右から優先的に非終端記号を変形していく最右導出のどちらかで行うことが多いです（本記事では最左導出を採用しています）。

先ほどの文法で $abbb$ を最左導出、最右導出した場合、以下のような変形で求めることができます。

最左導出の場合

f:id:momoyama1192:20190906161611g:plain

最右導出の場合

f:id:momoyama1192:20190906161615g:plain

(3) 列挙していく

文字列がどのように導出されるかを説明したので、実際に上の文法 $G$ に含まれるような言語 $L(G)$ を列挙していきましょう。

今回は練習なので6文字以下の $L(G)$ に含まれる言語を探していきます。

列挙していく際には下のような木構造（ほぼ樹形図）を書いていくとわかりやすいかと思われます。

f:id:momoyama1192:20190906161619g:plain

よって、 $L(G)$ に含まれる6文字以下の文字列は\[
ab, \ abbb, \ abbbbb, \ aaab, \ aaabbb, \ aaaaab
\]の6個となります。

(4) 列挙の結果からどのような言語かを推測する

ある程度列挙すると、文法の法則がつかめてきますよね。

今回の場合は、少し考えると、 $a$ が奇数回続いたあとに $b$ がさらに奇数回続くような文字列が受理されていることがわかりますね。

数式で表すと、下のように表せます。

f:id:momoyama1192:20190906161624g:plain

おまけ：決定性オートマトンを書いてみよう

実は、言語 $L(G)$ は決定性オートマトンを用いて表すこともできます。決定性オートマトンを用いると、

f:id:momoyama1192:20190906161628g:plain

と表せます。
（難しいと思った人は $a^{2n+1}$ と $b^{2n+1}$ を受理するようなオートマトンを書いてから連接してあげるといいと思います。でも状態数増えてこっちもめんどくさい……）

３．特別な文法・標準形

文脈自由文法の中でも特別な条件を満たすような言語は名前がつけられています。

今回は名前がつけられている文脈自由文法の中でも有名なものを3つほど紹介していきましょう。

(1) 正則文法

正則文法は、右正則文法と左正則文法の2つに分けられています。
（区別せずに正則文法と呼ぶ人も多い）

正則文法の特徴として、正則文法で記述される言語は必ず正則である、つまり（決定性）有限オートマトンを記述することができるという特徴があります*1。

もちろん正規文法に含まれるものは文脈自由文法にも含まれます。

右正則文法

右正則文法とは、下のように $A \to a$ のような非終端記号を終端記号1文字に置き換える規則、もしくは $A \to aB$ のような非終端記号を終端記号1文字のあとに非終端記号1文字をつけたものに置き換えるような規則の2つのみで構成されているような文法を表します。

左正則文法

左正則文法とは、下のように $A \to a$ のような非終端記号を終端記号1文字に置き換える規則、もしくは $A \to aB$ のような非終端記号を終端記号1文字のあとに非終端記号1文字をつけたものに置き換えるような規則の2つのみで構成されているような文法を表します。

f:id:momoyama1192:20190906161633g:plain

注意！

右正則文法の規則 $A \to aB$ と左正則文法 $A \to Ba$ の両方を1つの文法で使うことはできません。どちらか片方のみの規則を使うこと（もしくは両方使わないこと）が正則文法の条件です。

(2) チョムスキー(Chomsky)標準形

チョムスキー標準形とは、下のように $A \to a$ のような非終端記号を終端記号1文字に置き換える規則、もしくは $A \to BC$ のような非終端記号を非終端記号2文字に置き換える規則（もしくは開始記号 $S$ が空文字にしかならない規則のみ）で構成されるような文法のことを表します。

f:id:momoyama1192:20190906161637g:plain

チョムスキー標準形の文法の特徴として、CYK法（CKY法）などによる構文解析が可能なことがあげられます。

また、すべての文脈自由文法は等価なチョムスキー標準形に変換してあげることができます（今回はチョムスキー標準形への変換については割愛します）。

(3) グライバッハ(Greibach)標準形

グライバッハ標準形とは、下のように $A \to aX$ のような非終端記号を終端記号1文字のあとに非終端記号が1文字以上並んだものに変換する規則（もしくは開始記号を空文字にするような規則）のみで構成された文脈自由文法を表します。

f:id:momoyama1192:20190906161641g:plain

グライバッハ標準形の特徴として、生成規則を適用した回数がそのまま文字列の長さになるという特徴があります。（例えば4回適用すると文字列は必ず4文字となります。）

４．練習問題

では、1問だけですが練習をしてみましょう。

練習

つぎの文法 $G_1$ , $G_2$ が定義されているとする。\[
G_1 = \left( \{S,A\}, \{a,b\},\{ S \to aSb, \ S \to A, \ A \to a, A \to aA \},S \right) \\
G_2 = \left( \{S,B\}, \{a,b\},\{ S \to aSb, \ S \to B, \ B \to b, B \to Bb \},S \right)
\]