本シリーズでは、以下の本に沿って解説を書いている。
前回は、一つ目のcfgの標準形であるチョムスキー標準形について解説した。
変換方法も紹介したが、せめてどういったものかだけでもしっかり把握しておきたい。
以下がその記事だ。
さて、今回はもう一つの標準形、グライバッハ標準形というものを紹介しよう。
…この変換方法がちょいと厄介なので、丁寧に進めていく。
グライバッハ標準形
早速本題に入ろう。
なお、前回のチョムスキー標準形と同様、参考書の内容から少し変えさせてもらう。
あるcfg\(G = (V, \Sigma, P, S)\)の生成規則について、変数\(A \in V\)と終端記号\(a \in \Sigma\)、そして変数列\(\gamma \in V^*\)を使って以下で書き表せるとき、\(G\)をグライバッハ標準形という。
$$A \rightarrow a \gamma$$
ただし、開始記号に限り、空列を生成するような以下の生成規則が存在してもよい。
$$S \rightarrow \varepsilon$$
要するに、一つの終端記号の後ろに開始記号以外の変数がいくつでも続いてよい、という形。
もちろん、その変数部分が空列になっているもの…言い換えると、終端記号一つのみを生成するような規則\(A \rightarrow a\)も存在してよいし、通常は存在すると思っていいだろう。
もしそれがないと、終端記号のみの列を生成できないことになり、\(S \rightarrow \varepsilon\)があればその言語は\(\{\varepsilon\}\)、無ければ\(\phi\)となる。
ちなみに、参考書では空列についての生成規則\(S \rightarrow \varepsilon\)を許さない、という定義になっている。
例を出すと、以下のようなcfg\(G = (V, \Sigma, P, S)\)。
- \(V = \{S, A, B\}\)
- \(\Sigma = \{0, 1, 2\}\)
- \(P\)について
- \(S \rightarrow 0SB\)
- \(S \rightarrow 2A\)
- \(A \rightarrow 2\)
- \(B \rightarrow 1\)
各生成規則について、先頭が終端記号、その後は変数列となっているので、これはグライバッハ標準形だ。
なお、これが生成する言語\(L(G)\)は以下。
$$L(G) = \{0^n221^n | n \in \mathbb{Z}, n \geq 0\}$$
前回、チョムスキー標準形の例として出したものと同じ言語だ。
ちょっとだけ、グライバッハ標準形の利点を述べておこう。
これは、どの生成規則を使えばいいかが分かりやすいのだ。
先頭が必ず終端記号になっているので、最左導出でステップを作ると必ず終端記号列が増えていくことになる。
そのため、その時点で次に来て欲しい終端記号を見れば、それを先頭に生成するような規則の中に使うべきものがあることになる。
例えば、上のcfg\(G\)で、列\(002211\)が生成できるかを確認したいとする。
このとき、まず先頭が0なので、開始記号からは一つ目の生成規則を使えばいいというのが瞬時に判断できる。
最後までのステップ全体を書き出してみよう。
$$\begin{eqnarray}
S & \Rightarrow & 0SB \\
& \Rightarrow & 00SBB\\
& \Rightarrow & 002ABB\\
& \Rightarrow & 0022BB\\
& \Rightarrow & 00221B\\
& \Rightarrow & 002211
\end{eqnarray}$$
どの生成規則を使っているか、かなり分かりやすい。
もう一つ利点があり、長さ\(n\)の列を生成するためには、空列を除き\(n\)ステップが必要で、かつ\(n\)ステップあれば十分だ。
これは、一回のステップで必ず列に含まれる終端記号が一つ増えるから。
空列は、\(S \Rightarrow \varepsilon\)が必要なので例外的に1回となる。
と、以上のようにわりと実用的な標準形だ。
…実は、もう一つ有用な事例があるのだが、それは今後解説する新しいオートマトンであるプッシュダウンオートマトンというものに関わりがある。
その詳細については、その時に書くことにしよう。
グライバッハ標準形への変換方法
では、任意のcfgをグライバッハ標準形に変換する方法を紹介しよう。
なお、参考書は軽くアイディアが述べられている程度なので、別の資料(ここ)を参照している。
英語だがそんなに難しくないので、その気があれば是非読んでみて欲しい。
出発点となるcfgを\(G = (V, \Sigma, P, S)\)としておこう。
さて、今回参照している資料には手順が以下のように書かれている。
Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’ → S.
Greibach Normal Form – Tutorialspoint
Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed earlier)
Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed earlier)
Step 4 − Remove all direct and indirect left-recursion.
Step 5 − Do proper substitutions of productions to convert it into the proper form of GNF.
これを日本語に直してみよう。
- もし開始記号\(S\)が生成規則の右側にあれば、新しい変数\(S’\)を開始記号とし、生成規則\(S’ \rightarrow S\)を追加する
- Null規則を削除する
- 単一規則を削除する
- 直接、あるいは間接の左再帰性を削除する
- 適切に生成規則の置き換えをして、グライバッハ標準形に直す
ステップ2と3の括弧内は省略しているが、どちらも以前解説した内容を使うよ、ということが書かれている。
参考書であったり、他の日本語のサイトなどではほとんどで変換元をチョムスキー標準形としている。
が、この方法はチョムスキー標準形以外からでも問題ない。
では、手順の詳細を見ていこう。
手順1：開始記号を生成しないよう変形
ここは分かりやすい。
全ての生成規則を見て、その生成先に開始記号\(S\)が一つでも出てくれば、以下の操作を行う。
- 変数\(S’\)と、生成規則\(S’ \rightarrow S\)を追加する
- 今追加した\(S’\)を新たな開始記号とする
これで完了。
最初のステップが一つ増えるだけで、生成する言語に差がないことは明らかだろう。
なお、ちょっと分かりづらいので、手順2以降ではこの操作を終えた後、変数名を付け直して改めて開始記号に\(S\)という名前をつけておく。
手順2：Null規則の削除
Null規則(原文ではNull production)とは何ぞやと思われるかもしれないので、定義を。
ある変数\(A\)について、以下の生成規則をNull規則と呼ぶ。
$$A \rightarrow \varepsilon$$
どこかで似たようなものを見たことがないだろうか。
…実は、前回も同じことをしている。
というわけで、ここでの手順は前回解説したこれをすることになる。
ちなみに原文には書かれていないが、開始記号からのNull規則(\(S \rightarrow \varepsilon\))はグライバッハ標準形の定義に沿っているのであっても問題ない。
手順3：単一規則の削除
これも前回出した内容だ。
単一規則の定義もしているので、これを参照してほしい。
手順4：左再帰性の削除
ここからが本番だ。
まず、左再帰性の定義からしていこう。
ある変数\(A \in V\)と任意の列\(\gamma \in (V \cup \Sigma)^*\)を使って以下のように書き表すことのできる生成規則を、直接の左再帰性を持つという。
$$A \rightarrow A \gamma$$
要するに、生成元の変数が生成先の先頭に出てくるような生成規則のことだ。
また、間接も定義していく。
ある変数\(A \in V\)と任意の列\(\gamma \in (V \cup \Sigma)^*\)を使って以下のステップが存在するとき、\(A\)は間接の左再帰性を持つと定義する。
$$A \overset{*}{\Rightarrow} A \gamma$$
例えば以下の形。
- \(S \rightarrow AB\)
- \(A \rightarrow BC\)
- \(B \rightarrow AC\)
- …
このとき、\(A\)に注目すると…
$$A \Rightarrow BC \Rightarrow ACC$$
というステップがあるので、間接的に左再帰性を持つことになる、というイメージだ。
これらを削除していこう。
まず、直接の左再帰性を削除する方法から。
ある変数\(A \in V\)、列\(\gamma_1, \gamma_2, …, \gamma_m \in (V \cup \Sigma)^*\)を使って、以下のような\(m\)個の直接の左再帰性を持つ生成規則があったとしよう。
- \(A \rightarrow A \gamma_1\)
- \(A \rightarrow A \gamma_2\)
- …
- \(A \rightarrow A \gamma_m\)
今、\(\gamma_i = \varepsilon\)となっていた場合…これは、\(A \rightarrow A\)となり、何もしていない生成規則となる。
つまり、これはそのまま削除すればいいので、これ以降は全ての\(\gamma_i\)は空列でないとしよう。
とはいえ、上で単一規則の削除をした段階で、実際の手順ではこの状況にはなり得ない。
このとき、まず新たに変数\(Z\)を追加する。
そして、\(A\)からの生成規則のうち左再帰性でないような以下の生成規則を使う。
- \(A \rightarrow \alpha_1\)
- \(A \rightarrow \alpha_2\)
- …
- \(A \rightarrow \alpha_n\)
ここで、\(\alpha_1, \alpha_2, …, \alpha_n \in (V \cup \Sigma)^*\)だ。
こう置いたとき、まず以下の生成規則を追加する。
- パターン1
- \(A \rightarrow \alpha_1 Z\)
- \(A \rightarrow \alpha_2 Z\)
- …
- \(A \rightarrow \alpha_n Z\)
- パターン2
- \(Z \rightarrow \gamma_1\)
- \(Z \rightarrow \gamma_2\)
- …
- \(Z \rightarrow \gamma_m\)
- \(Z \rightarrow \gamma_1 Z\)
- \(Z \rightarrow \gamma_2 Z\)
- …
- \(Z \rightarrow \gamma_m Z\)
そして、元の左再帰性を持つ\(m\)個の生成規則を削除する。
これで、一つの変数について、左再帰性を持つ生成規則を削除できる。
これが問題ないことを軽く説明しておこう。
\(\beta_i \in \{\gamma_1, \gamma_2, …, \gamma_m\}\)としておく。
まず、変換前は以下のようなステップが存在する。
$$\begin{eqnarray}
A & \Rightarrow & A \beta_1 \\
& \Rightarrow & A \beta_1 \beta_2 \\
& … & \\
& \Rightarrow & A \beta_1 \beta_2 … \beta_k \\
& \Rightarrow & \alpha_i \beta_1 \beta_2 … \beta_k
\end{eqnarray}$$
それに対し、変換後は以下のようなステップになる。
$$\begin{eqnarray}
A & \Rightarrow & \alpha_i Z \\
& \Rightarrow & \alpha_i \beta_1 Z \\
& \Rightarrow & \alpha_i \beta_1 \beta_2 Z \\
& … & \\
& \Rightarrow & \alpha_i \beta_1 \beta_2 … \beta_{k-1} Z \\
& \Rightarrow & \alpha_i \beta_1 \beta_2 … \beta_{k-1} \beta_k
\end{eqnarray}$$
これで、生成できる列に差がないことが分かる。
なお、今は左再帰性を持たない生成規則があることを仮定していたが、もしそのような生成規則が無ければ、そもそも\(A\)を使った瞬間に終端記号のみの列を生成できなくなる。
どんな生成規則を使おうと、必ず変数\(A\)が残り続けてしまうからだ。
よって、その\(A\)の左再帰性を持つ生成規則…もっと言うと、変数\(A\)を含む生成規則全てを削除できる。
これも覚えておこう。
さて、これで直接の左再帰性を持つ生成規則が削除できるようになった。
ということで、まずはこれを使って直接の左再帰性を除去しておこう。
あとは、間接の左再帰性を持つ部分を削除する方法が必要。
この手順は、Wikipediaを参照しよう。
これを使うと、一括で全ての間接の左再帰性を持つ生成規則を置き換えることができる。
上で紹介した手順は、こちらの中でも使うことになる。
Wikipediaに書かれている前提は上の手順でないことが保証されているので、単に以下を実行するだけでいい。
非終端記号を何らかの固定の順序\(A_1, … A_n\)で並べる(ループさせるため)。
for i = 1 to n {
左再帰 – Wikipedia
for j = 1 to i – 1 {
・現在の\(A_j\)生成規則を次のようにする。
\(A_j \rightarrow \delta_1 | … | \delta_k\)
・各生成規則\(A_i \rightarrow A_j \gamma\)を次で置き換える。
\(A_i \rightarrow \delta_1 \gamma | … | \delta_j \gamma\)
・\(A_i\)についての直接左再帰を除去する。
}
}
二つほど補足を。
まず、この中に書かれている非終端記号とは、変数のことだ。
参考書によっては、変数を非終端記号という名前で定義していることもあるので、覚えておくといい。
次に、手順内の生成規則の書き方が以下のようになっている。
$$A_j \rightarrow \delta_1 | … | \delta_k$$
これは、以下全ての生成規則を持つことと同じ意味だ。
- \(A_j \rightarrow \delta_1\)
- \(A_j \rightarrow \delta_2\)
- …
- \(A_j \rightarrow \delta_k\)
この後使わせてもらうので、ちょっと覚えておいて欲しい。
さて、この手順で左再帰性を削除できる理由は…ちょっと省略させてもらう。
今後もし証明できれば、オマケとして追記することにしよう。
手順5：適切な生成規則の変形
ここまで来れば、あとはコツコツ変換していくだけだ。
ここも大きく二つの手順に分けよう。
まずは、各生成先の中に含まれる先頭以外の終端記号を変数に置き直す。
例えば、\(A \rightarrow bCdE\)とあれば、\(X_d \rightarrow d\)を追加して、元を\(A \rightarrow bCX_dE\)と置き直してあげればいい。
これも、前回似たようなことをやっていた。
なお、最初に全ての終端記号それぞれで、それ一つを追加するような生成規則を新たな変数とともに追加しておき、それを使って片っ端から変えていけば大丈夫だ。
もし使わなかったものがあれば、そこで消しておこう。
これで、生成規則は以下のパターンのみになった。
- \(S \rightarrow \varepsilon\)
→OK - \(A \rightarrow a \gamma\) ※\(A \in V, a \in \Sigma, \gamma \in V^*\)
→OK - \(A \rightarrow \gamma\) ※\(A \in V, \gamma \in V^*\)
さらに、左再帰性も一切無くなっている。
最後は、先頭が変数のもの。
ある一つの生成規則\(A \rightarrow B \gamma\)を直したいとする。
この\(B\)からの生成規則が以下の\(n\)個だったとしよう。
$$B \rightarrow \beta_1 | \beta_2 | … | \beta_n$$
このとき、まず以下\(n\)個の生成規則を追加する。
$$A \rightarrow \beta_1 \gamma | \beta_2 \gamma | … | \beta_n \gamma$$
そして、元の\(A \rightarrow B \gamma\)を削除すればOKだ。
これはステップを一つ削減しているだけなので、生成できる言語に差がないことは明らかだろう。
この手順を、全ての条件に当てはまっている生成規則に対して行うことで、最終的にグライバッハ標準形が得られる。
今は左再帰性が無く、この手順では一番左を入れ替えているだけなので、延々と続くことはあり得ない…というかそれを無くすために左再帰性を除去したのだ。
最後に一つだけ、この手順内で追加した生成規則も当然変換対象に入るので、そこは注意しよう。
具体例その1
さて、手順だけ見てもピンと来ないと思うので、具体例を見ていこう。
まず、参考書に載っているチョムスキー標準形の例をグライバッハ標準形に直してみる。
変換元のcfg\(G = (V, \Sigma, P, S)\)は以下の通り。
- \(V = \{S, A, B, C, X\}\)
- \(\Sigma = \{0, 1, 2\}\)
- \(P\)について
- \(S \rightarrow AX\)
- \(S \rightarrow CC\)
- \(X \rightarrow SB\)
- \(A \rightarrow 0\)
- \(B \rightarrow 1\)
- \(C \rightarrow 2\)
では早速手順1から見ていく。
手順1では、生成先に開始記号が出てきているかの確認だった。
今、\(X \rightarrow SB\)があるので、新たに\(S’\)を導入しよう。
- \(S’ \rightarrow S\)
- \(S \rightarrow AX\)
- \(S \rightarrow CC\)
- \(X \rightarrow SB\)
- \(A \rightarrow 0\)
- \(B \rightarrow 1\)
- \(C \rightarrow 2\)
…開始記号が変わると分かりづらいので、元からあった\(S\)の名前を\(Y\)にして、\(S’\)を\(S\)に置き換えておこう。
この書き換えを行った結果、開始記号は\(S\)に戻り、生成規則は以下の通りになる。
- \(S \rightarrow Y\)
- \(Y \rightarrow AX\)
- \(Y \rightarrow CC\)
- \(X \rightarrow YB\)
- \(A \rightarrow 0\)
- \(B \rightarrow 1\)
- \(C \rightarrow 2\)
手順2では、空列のみを生成するNull規則の削除…だが、今回はそれが含まれないので飛ばしてしまおう。
手順3、単一規則を削除。
今回、手順1で追加した\(S \rightarrow Y\)のみが該当する。
つまり、以下二つを追加し、この元を削除することになる。
- \(S \rightarrow AX\)
- \(S \rightarrow CC\)
これで、現状は以下の通りになった。
- \(S \rightarrow AX\)
- \(S \rightarrow CC\)
- \(Y \rightarrow AX\)
- \(Y \rightarrow CC\)
- \(X \rightarrow YB\)
- \(A \rightarrow 0\)
- \(B \rightarrow 1\)
- \(C \rightarrow 2\)
では、ここからがメイン、手順4に移る。
直接の左再帰性はないので、間接の左再帰性を無くしていこう。
順番をつけるために、以下のように変数を置き直す。
- \(S = A_1\)
- \(Y = A_2\)
- \(X = A_3\)
- \(A = A_4\)
- \(B = A_5\)
- \(C = A_6\)
この形に置き直した生成規則一覧も出しておく。
- \(A_1 \rightarrow A_4A_3\)
- \(A_1 \rightarrow A_6A_6\)
- \(A_2 \rightarrow A_4A_3\)
- \(A_2 \rightarrow A_6A_6\)
- \(A_3 \rightarrow A_2A_5\)
- \(A_4 \rightarrow 0\)
- \(A_5 \rightarrow 1\)
- \(A_6 \rightarrow 2\)
これで、\(i\)を1から6まで増やしながら作業をしていこう。
\(i = 1\)のとき、\(j\)は取れないので何もしない。
\(i = 2\)のとき、\(j = 1\)から。
今、\(A_2 \rightarrow A_1 \gamma\)という形がないので、ここも飛ばす。
次に、\(i\)を増やして\(i = 3\)。
\(j = 1\)は\(A_3 \rightarrow A_1 \gamma\)がない。
\(j = 2\)、ここでようやく\(A_3 \rightarrow A_2A_5\)が登場する。
\(A_2 \rightarrow A_4A_3 | A_6A_6\)なので、これを使って以下で置き換えよう。
$$A_3 \rightarrow A_4A_3A_5 | A_6A_6A_5$$
この時点で、生成規則は以下の通り。
- \(A_1 \rightarrow A_4A_3\)
- \(A_1 \rightarrow A_6A_6\)
- \(A_2 \rightarrow A_4A_3\)
- \(A_2 \rightarrow A_6A_6\)
- \(A_3 \rightarrow A_4A_3A_5\)
- \(A_3 \rightarrow A_6A_6A_5\)
- \(A_4 \rightarrow 0\)
- \(A_5 \rightarrow 1\)
- \(A_6 \rightarrow 2\)
次に\(A_3\)についての直接の左再帰性を削除…なのだが、それが生じていないので問題ない。
\(i\)を増やしていこう。
…とはいえ、ここからは\(A_i\)からの生成規則の右側は全て終端記号一つなので、手順によって変わることはない。
つまり、最後に出した一覧で、左再帰性の除去が完了している。
最後、形を整えていく。
まず、先頭以外の終端記号はないので、これも飛ばす。
次に、先頭が変数の生成規則について、その先頭は\(A_4\)と\(A_6\)しかない。
そして、この二つはただ一つの終端記号を生成するのみ。
というわけで、先頭の\(A_4\)、\(A_6\)をそれぞれ\(0\)、\(2\)で置き換えるだけになる。
よって、最終的に…
- \(A_1 \rightarrow 0A_3\)
- \(A_1 \rightarrow 2A_6\)
- \(A_2 \rightarrow 0A_3\)
- \(A_2 \rightarrow 2A_6\)
- \(A_3 \rightarrow 0A_3A_5\)
- \(A_3 \rightarrow 2A_6A_5\)
- \(A_4 \rightarrow 0\)
- \(A_5 \rightarrow 1\)
- \(A_6 \rightarrow 2\)
これで、グライバッハ標準形の完成だ。
オマケで、前回やった不要な生成規則の削除もしてみると…
- \(A_1 \rightarrow 0A_3\)
- \(A_1 \rightarrow 2A_6\)
- \(A_3 \rightarrow 0A_3A_5\)
- \(A_3 \rightarrow 2A_6A_5\)
- \(A_5 \rightarrow 1\)
- \(A_6 \rightarrow 2\)
こうなる。
念のため、冒頭でやった列\(002211\)を生成できるか確認してみよう。
$$\begin{eqnarray}
A_1 & \Rightarrow & 0A_3 \\
& \Rightarrow & 00A_3A_5\\
& \Rightarrow & 002A_6A_5A_5\\
& \Rightarrow & 0022A_5A_5\\
& \Rightarrow & 00221A_5\\
& \Rightarrow & 002211\\
\end{eqnarray}$$
というわけで、問題なさそうだ。
具体例その2
もう一つやってみよう。
導出木のところで出した具体例だ。
なかなかに複雑なので、やりごたえがあると思う。
変換元のcfg\(G = (V, \Sigma, P, S)\)は以下の通り。
- \(V = \{S, A, B\}\)
- \(\Sigma = \{a, b\}\)
- \(P\)について
- \(S \rightarrow SS\)
- \(S \rightarrow \varepsilon\)
- \(S \rightarrow aB\)
- \(S \rightarrow bA\)
- \(A \rightarrow a\)
- \(A \rightarrow bAA\)
- \(B \rightarrow b\)
- \(B \rightarrow aBB\)
ぱっと見グライバッハ標準形に見えるが、先頭の\(S \rightarrow SS\)のせいでグライバッハ標準形ではない。
ちなみにこの\(G\)は、\(a, b\)からなる列のうち、\(a\)と\(b\)の個数が一致しているような列からなる言語を生成する。
では、やっていこう。
まず手順1、生成先に\(S\)があるので、この\(S\)を\(Y\)に置き換え、さらに\(S \rightarrow Y\)を追加する。
- \(S \rightarrow Y\)
- \(Y \rightarrow YY\)
- \(Y \rightarrow \varepsilon\)
- \(Y \rightarrow aB\)
- \(Y \rightarrow bA\)
- \(A \rightarrow a\)
- \(A \rightarrow bAA\)
- \(B \rightarrow b\)
- \(B \rightarrow aBB\)
開始記号は\(S\)だ。
次に手順2、Null規則は\(Y \rightarrow \varepsilon\)のみ。
そのため、生成先に\(Y\)を含むそれぞれの生成規則を見ていく。
まず、\(S \rightarrow Y\)については、\(S \rightarrow \varepsilon\)を追加。
次に、\(Y \rightarrow YY\)については、以下2つを追加。
- \(Y \rightarrow Y\)
- \(Y \rightarrow \varepsilon\)
…なのだが、二つ目はすでにあるので何もせず、一つ目は何もしない生成規則なのでここで消してしまう。
結果、何も追加しない。
そして、\(Y \rightarrow \varepsilon\)だけを削除して、現状は以下の通りだ。
- \(S \rightarrow Y\)
- \(S \rightarrow \varepsilon\)
- \(Y \rightarrow YY\)
- \(Y \rightarrow aB\)
- \(Y \rightarrow bA\)
- \(A \rightarrow a\)
- \(A \rightarrow bAA\)
- \(B \rightarrow b\)
- \(B \rightarrow aBB\)
では、手順3に進もう。
ここでは単一規則の削除、一番上の\(S \rightarrow Y\)のみ該当する。
これを以下で置き換える。
- \(S \rightarrow YY\)
- \(S \rightarrow aB\)
- \(S \rightarrow bA\)
この結果、以下のようになる。
- \(S \rightarrow YY\)
- \(S \rightarrow aB\)
- \(S \rightarrow bA\)
- \(S \rightarrow \varepsilon\)
- \(Y \rightarrow YY\)
- \(Y \rightarrow aB\)
- \(Y \rightarrow bA\)
- \(A \rightarrow a\)
- \(A \rightarrow bAA\)
- \(B \rightarrow b\)
- \(B \rightarrow aBB\)
そして、手順の4。
今回、直接の左再帰性を持つ生成規則\(Y \rightarrow YY\)があるので、これを削除しよう。
変数\(Z_1\)を導入しながら以下二つを追加し、元を削除する。
- \(Y \rightarrow aBZ_1 | bAZ_1\)
- \(Z_1 \rightarrow Y | YZ_1\)
これで、現状は以下の通り。
- \(S \rightarrow YY\)
- \(S \rightarrow aB\)
- \(S \rightarrow bA\)
- \(S \rightarrow \varepsilon\)
- \(Y \rightarrow aBZ_1\)
- \(Y \rightarrow bAZ_1\)
- \(Y \rightarrow aB\)
- \(Y \rightarrow bA\)
- \(A \rightarrow a\)
- \(A \rightarrow bAA\)
- \(B \rightarrow b\)
- \(B \rightarrow aBB\)
- \(Z_1 \rightarrow Y\)
- \(Z_1 \rightarrow YZ_1\)
次に、間接の左再帰性の除去。
…実は、これには間接の左再帰性は存在しない。
というのも、全ての生成先の先頭に変数が来ているものについて、その先頭の変数は\(Y\)しかない。
そして、\(Y\)からの生成規則は全て先頭が終端記号になっている。
これらから、左再帰性が存在しないことが分かるのだ。
とはいえ、練習のため一応やっておこう。
まず、変数名を以下のように変更する。
- \(S = A_1\)
- \(Y = A_2\)
- \(A = A_3\)
- \(B = A_4\)
- \(Z_1 = A_5\)
そして、これで生成規則も書き直しておく。
- \(A_1 \rightarrow A_2A_2\)
- \(A_1 \rightarrow aA_4\)
- \(A_1 \rightarrow bA_3\)
- \(A_1 \rightarrow \varepsilon\)
- \(A_2 \rightarrow aA_4A_5\)
- \(A_2 \rightarrow bA_3A_5\)
- \(A_2 \rightarrow aA_4\)
- \(A_2 \rightarrow bA_3\)
- \(A_3 \rightarrow a\)
- \(A_3 \rightarrow bA_3A_3\)
- \(A_4 \rightarrow b\)
- \(A_4 \rightarrow aA_4A_4\)
- \(A_5 \rightarrow A_2\)
- \(A_5 \rightarrow A_2A_5\)
ではやっていく。
…のだが、よく見てもらうと\(i = 5\)、\(j = 2\)までは一つも条件に該当するものがないので、そこまで飛んでしまおう。
というわけで、\(i = 5\)、\(j = 2\)の時。
\(A_5 \rightarrow A_2\)と、\(A_5 \rightarrow A_2A_5\)があるので、まとめて置き直す。
まず\(A_5 \rightarrow A_2\)については以下で置換。
$$A_5 \rightarrow aA_4A_5 | bA_3A_5 | aA_4 | bA_3$$
次に、\(A_5 \rightarrow A_2A_5\)については以下で置換。
$$A_5 \rightarrow aA_4A_5A_5 | bA_3A_5A_5 | aA_4A_5 | bA_3A_5$$
ただし、\(A_5 \rightarrow aA_4A_5 | bA_3A_5\)が重複しているので、片方だけ残す。
これで、直接の左再帰性も出てこなかったので、以下のようになる。
- \(A_1 \rightarrow A_2A_2\)
- \(A_1 \rightarrow aA_4\)
- \(A_1 \rightarrow bA_3\)
- \(A_1 \rightarrow \varepsilon\)
- \(A_2 \rightarrow aA_4A_5\)
- \(A_2 \rightarrow bA_3A_5\)
- \(A_2 \rightarrow aA_4\)
- \(A_2 \rightarrow bA_3\)
- \(A_3 \rightarrow a\)
- \(A_3 \rightarrow bA_3A_3\)
- \(A_4 \rightarrow b\)
- \(A_4 \rightarrow aA_4A_4\)
- \(A_5 \rightarrow aA_4A_5\)
- \(A_5 \rightarrow bA_3A_5\)
- \(A_5 \rightarrow aA_4\)
- \(A_5 \rightarrow bA_3\)
- \(A_5 \rightarrow aA_4A_5A_5\)
- \(A_5 \rightarrow bA_3A_5A_5\)
…現時点で18個、あと4個ほど増えるのでなんとか頑張ってほしい。
さて、最後の作業、先頭以外の終端記号と先頭の変数をなんとかしよう。
先頭以外の終端記号は、今一つも存在しない。
よって、先頭の変数を見ていく。
該当するのは先頭の一つ、\(A_1 \rightarrow A_2A_2\)。
これを、以下で置き直す。
$$A_1 \rightarrow aA_4A_5A_2 | bA_3A_5A_2 | aA_4A_2 | bA_3A_2$$
というわけで、最終的に…
- \(A_1 \rightarrow aA_4A_5A_2\)
- \(A_1 \rightarrow bA_3A_5A_2\)
- \(A_1 \rightarrow aA_4A_2\)
- \(A_1 \rightarrow bA_3A_2\)
- \(A_1 \rightarrow aA_4\)
- \(A_1 \rightarrow bA_3\)
- \(A_1 \rightarrow \varepsilon\)
- \(A_2 \rightarrow aA_4A_5\)
- \(A_2 \rightarrow bA_3A_5\)
- \(A_2 \rightarrow aA_4\)
- \(A_2 \rightarrow bA_3\)
- \(A_3 \rightarrow a\)
- \(A_3 \rightarrow bA_3A_3\)
- \(A_4 \rightarrow b\)
- \(A_4 \rightarrow aA_4A_4\)
- \(A_5 \rightarrow aA_4A_5\)
- \(A_5 \rightarrow bA_3A_5\)
- \(A_5 \rightarrow aA_4\)
- \(A_5 \rightarrow bA_3\)
- \(A_5 \rightarrow aA_4A_5A_5\)
- \(A_5 \rightarrow bA_3A_5A_5\)
これで完成だ。
…なのだが、あまりにも数が増えすぎている。
ちょっと、余分な生成規則がないか確認してみよう。
まず、終端記号のみの列を導出できない変数について。
先に、空集合\(W\)を用意しておく。
次に、終端記号のみを生成できる変数\(A_3, A_4\)を追加する。
そして、終端記号と、この\(W\)内の変数のみで構成される列を生成する生成規則を見ると…
- \(A_1 \rightarrow aA_4\)
- \(A_1 \rightarrow bA_3\)
- \(A_2 \rightarrow aA_4\)
- \(A_2 \rightarrow bA_3\)
- \(A_5 \rightarrow aA_4\)
- \(A_5 \rightarrow bA_3\)
これらがあるので、\(A_1\)、\(A_2\)、\(A_5\)が\(W\)に追加される。
これで全ての変数が\(W\)に入ったので、これで削除できる変数はなさそうだ。
次に、開始記号から辿れない変数…これも、上から二つの生成規則で全て辿れるので削除できない。
というわけで、上で完成のようだ。
やたらと複雑になってしまったが、元のcfgと同じ列を生成することを幾つか具体的な列で確認してみよう。
\(a\)と\(b\)からなる列で、それぞれの個数が同じ列を生成するのだった。
まず、シンプルに\(ab\)でやってみる。
$$\begin{eqnarray}
A_1 & \Rightarrow & aA_4\\
& \Rightarrow & ab
\end{eqnarray}$$
大丈夫そうだ。
次に、ちょっと増やして\(aaababbb\)。
$$\begin{eqnarray}
A_1 & \Rightarrow & aA_4 \\
& \Rightarrow & aaA_4A_4 \\
& \Rightarrow & aaaA_4A_4A_4 \\
& \Rightarrow & aaabA_4A_4\\
& \Rightarrow & aaabaA_4A_4A_4\\
& \Rightarrow & aaababA_4A_4 \\
& \Rightarrow & aaababbA_4 \\
& \Rightarrow & aaababbb
\end{eqnarray}$$
これも問題なく生成できた。
…変数が\(A_4\)しか出てこなかったので、他の変数が出てくるようなステップも見てみよう。
無理やり、全ての変数が出てくるようなステップを作ってみた。
列\(abbaab\)を生成するステップについて。
$$\begin{eqnarray}
A_1 & \Rightarrow & aA_4A_5A_2 \\
& \Rightarrow & abA_5A_2 \\
& \Rightarrow & abbA_3A_2 \\
& \Rightarrow & abbaA_2 \\
& \Rightarrow & abbaaA_4 \\
& \Rightarrow & abbaab
\end{eqnarray}$$
こんな感じだ。
なお、以下でも問題ない。
$$\begin{eqnarray}
A_1 & \Rightarrow & aA_4A_2 \\
& \Rightarrow & abA_2 \\
& \Rightarrow & abbA_3A_5 \\
& \Rightarrow & abbaA_5 \\
& \Rightarrow & abbaaA_4 \\
& \Rightarrow & abbaab \\
\end{eqnarray}$$
何かもうちょっと簡単な形にできそうではあるが…とにかく、グライバッハ標準形への変換自体は問題なさそうだ。
おわりに
今回は、グライバッハ標準形と、その変換方法を紹介した。
変換方法の証明が残っているが、それは今後の課題ということで、できたらオマケとして追記することにする。
さて、次回は文脈自由言語に関する定理を紹介しよう。
これを使うと、少なくともある言語が文脈自由言語でないことを示す際の武器として使えるようになる。
今回のグライバッハ標準形からは離れるが、後でまた戻ってくるので、忘れないようにしたい。
2021/2/6追記
次回の内容である、\(uvwxy\)定理(反復補題)を解説した。
使い方がちょっと独特な感じがするので、これも幾つか練習してみることをオススメする。
コメント