オートマトン・言語と計算理論「文脈自由文法」

本シリーズでは、以下の本に沿って解説を書いている。

Amazon.co.jp

前回までで、正規文法編が完了だ。

前回はその正規文法の名前の紹介と、正規文法には限界があるよという内容を解説した。

以下がその記事だ。

さて、今回から新しい内容、参考書で言うと第3章に入る。

ここでは、タイトルにも入れた文脈自由文法というものが新登場する。

これまでの感覚を持ちつつ、新しい内容に慣れていこう。

文脈自由文法
正規表現を生成するcfg
おわりに
1. オマケ：正規表現を生成するcfgの証明
  1. 右向き
  2. 左向き

文脈自由文法

早速紹介しよう。

文脈自由文法(以降cfgと呼ぶ)とは、以下4つの要素で構成されるシステムのようなものだ。

$V$：変数の有限集合
$\Sigma$：終端記号の有限集合
$P$：生成規則の有限集合
$S$：開始記号($S \in V$)

これらを使って、例えば$G = (V, \Sigma, P, S)$といった形で書き表される。

そして、この$G$はある言語を生成する。

そういった意味では、正規表現に似ていると考えられるだろう。

後でも触れるが、このcfgによって生成される言語のことを文脈自由言語と呼ぶ。

具体例

さて、いきなりこれを見てもわけがわからないと思うので、具体例を交えながら解説していこう。

まず、具体的なcfg$G = (V, \Sigma, P, S)$を以下のように決めてみる。

$V = \{S\}$
$\Sigma = \{0, 1\}$
$P = \{S \rightarrow \varepsilon, S \rightarrow 0S1\}$

これが生成する言語がどんなものか、見てみよう。

まず、最初に開始記号から始める。

$$S$$

次に、生成規則を使って書き換える。

一つ目を使うと$\varepsilon$になり、二つ目を使うと…

$$0S1$$

と置き換わる。

一つ目の場合、すでに変数がないのでこれで完了、まず$\varepsilon$が言語に含まれる。

次に、二つ目からさらにどちらかを適用してみる。

$0S1 \Rightarrow 0 \varepsilon 1 = 01$
$0S1 \Rightarrow 00S11$

この一つ目も、変数が無くなったので$01$という列が言語に含まれ、二つ目はさらに続く。

こんな感じで、開始記号$S$から出発して生成規則に従って変数を置き換えていき、変数がなくなった時点で出来上がった列が言語に含まれることになる。

よって、このcfg$G$が生成する言語は…

$$\{\varepsilon, 01, 0011, …\} = \{0^n1^n | n \in \mathbb{Z}, n \geq 0\}$$

となるのだ。

これは前回正規言語でない例として出したものであり、この時点で正規言語ではない言語を生成できることが分かる。

数学的な定義

これで、感覚的にどういうものかは分かったと思うので、数学的に定義していこう。

まず、$\varepsilon$nfaでやったようなステップの概念を導入する。

cfg$G = (V, \Sigma, P, S)$において、変数と終端記号からなる二つの列$u, v \in (V \cup \Sigma)^*$を考える。

このとき、ある$\alpha, \gamma \in (V \cup \Sigma)^*$とある生成規則$A \rightarrow \beta \in P$が存在し、$u = \alpha A \gamma$、かつ$v = \alpha \beta \gamma$と書けるとき、$v$は$u$から1ステップで導出されるという。

このままでは分かりづらいので言い換えると、生成規則のうち一つを一回だけ使って変換できるような関係のときに、1ステップで導出される、となる。

このとき、記法としては$u \Rightarrow v$と書き表す。

また、このステップを複数回辿って導出されるとき、単に導出されるという。

$u$から$v$が導出されるとき、$u \overset{*}{\Rightarrow} v$と表記しよう。

また、0回もこれに該当するので、$u = v$なら常に$u \overset{*}{\Rightarrow} v$が成り立つ。

これを使って、cfgが生成する言語の定義を。

cfg$G = (V, \Sigma, P, S)$について、$x \in \Sigma^*$とする。

$S$から$x$が導出されるとき、つまり$S \overset{*}{\Rightarrow} x$のときに、$x$は$G$によって生成されると言う。

そして、$G$が生成する言語$L(G)$は以下の式で定義される。

$$L(G) = \{x \in \Sigma^* | x \mbox{は} G \mbox{によって生成される}\}$$

まあ、$G$によって生成される列を集めたものが、$G$が生成する言語、ということだ。

最後に、ある言語$L$を生成するcfg$G$が存在するとき、その言語$L$を文脈自由言語と呼ぶ。

以上が、cfgに関する定義だ。

具体例で確認

さて、さっき出した例でステップや列の生成などの定義を確認してみよう。

例として出したcfg$G = (V, \Sigma, P, S)$は以下の通りであった。

$V = \{S\}$
$\Sigma = \{0, 1\}$
$P = \{S \rightarrow \varepsilon, S \rightarrow 0S1\}$

このとき、例えば列$000111$が言語$L(G)$に含まれるか見てみよう。

まず、生成規則の2番目から…

$$S \Rightarrow 0S1$$

が導出できる。

このとき、導出の定義に照らし合わせてみると…

$u = S$
$v = 0S1$
$\alpha = \varepsilon$
$\gamma = \varepsilon$
$A = S$
$\beta = 0S1$

とすれば…

$A \rightarrow \beta = S \rightarrow 0S1 \in P$
$u = \alpha A \gamma = \varepsilon S \varepsilon = S$
$v = \alpha \beta \gamma = \varepsilon 0S1 \varepsilon = 0S1$

となっていることが分かると思う。

同じ生成規則を使って、これをもう2回繰り返そう。

$$0S1 \Rightarrow 00S11$$

$$00S11 \Rightarrow 000S111$$

最後に、もう片方の生成規則を使う。

$$000S111 \Rightarrow 000 \varepsilon 111 = 000111$$

よって、これらを辿ると$S \overset{*}{\Rightarrow} 000111$が言えるので、$000111 \in L(G)$だと分かった。

なんとなく、流れは分かっただろうか。

正規表現を生成するcfg

さて、今回の最後にこれを考えてみよう。

前回まで取り扱っていた正規表現を列として捉え、それによってできる言語をcfgで生成してみる。

念のため、正規表現の定義を再掲しておこう。

なお、$\Sigma$のままだとcfgのものと混同してしまうので、正規表現側は$\Sigma_S$としておく。

$\Sigma_S$をアルファベットとし、$\Sigma_S$上の正規表現$S$と、その正規表現によって生成される言語$L(S)$を以下のように定義する。

$\phi$は正規表現であり、$L(\phi) = \phi$である。
$\varepsilon$は正規表現であり、$L(\varepsilon) = \{\varepsilon\}$である。
任意の$a \in \Sigma_S$は正規表現であり、$L(a) = \{a\}$である。
$R_1, R_2$を正規表現とし、以下3つを定義する。
1. $(R_1 + R_2)$は正規表現であり、$L((R_1 + R_2)) = L(R_1) \cup L(R_2)$である。
2. $(R_1 \cdot R_2)$は正規表現であり、$L((R_1 \cdot R_2)) = L(R_1)L(R_2)$である。
  ただし、この$\cdot$は省略してもよい。
3. $(R_1^*)$は正規表現であり、$L((R_1^*)) = L(R_1)^*$である。

こんな定義になっていたことを思い出そう。

なお、以前は演算に優先順位を設けることによって括弧を省略できると説明したが、今回は括弧の省略をしない形で考える。

では、考えていこう。

今回作成するcfgを$G = (V, \Sigma, P, S)$としておく。

まず、終端記号がどうなっているかについて。

当然だが、正規表現のアルファベット$\Sigma_S$のどの要素も含まなければいけない。

その他に、定義1から$\phi$、定義2から$\varepsilon$も必要になる。

ただし、この$\varepsilon$はこれまでやっていたような空列ではなく、一つの終端記号として取り扱いたい。

生成規則の中でも、空列としての$\varepsilon$が出てくる可能性があるからだ。

そのため、混乱を避けるために終端記号のものには添え字を付けて$\varepsilon_s$としておこう。

ちなみに$\phi$については生成規則で使われることはないので、特に置き換える必要はないだろう。

さて、他に必要な終端記号は、$(, ), +, \cdot, *$くらいだろうか。

というわけで、cfgの終端記号$\Sigma$は…

$$\Sigma = \Sigma_S \cup \{\phi, \varepsilon_s, (, ), +, \cdot, *\}$$

こうなる。

では、変数を…と進むのではなく、実際に生成規則を作りながら考えてみよう。

なお、開始記号は$S$で、ここから始めていく。

ちなみに、最終的にはこの$S$が正規表現全体を表すことになる。

定義の順番で見ていこう。

まず、定義1から、$\phi$1つでも正規表現だ。

つまり…

$$S \rightarrow \phi$$

という生成規則が出来上がる。

また、定義2から$\varepsilon_s$も正規表現なので…

$$S \rightarrow \varepsilon_s$$

も生成規則だ。

さらに、定義3から任意の$a \in \Sigma_S$一つも正規表現。

$$S \rightarrow a$$

今、$\Sigma_S$の中身が具体的ではないので、$a$を使って置かせてもらっている。

では、定義4に進んでいこう。

まず定義4-1、正規表現でプラスを挟み、その全体を括弧に入れたものが正規表現だと言っている。

さて、今開始記号の$S$が正規表現を表しているのだった。

つまり…

$$S \rightarrow (S + S)$$

という規則が出来上がる。

同じようにして、定義4-2は…

$$\begin{eqnarray}
S & \rightarrow & (S \cdot S) \\
S & \rightarrow & (SS)
\end{eqnarray}$$

こうなる。

二つあるのは、$\cdot$の有無を考えたものだ。

さらに、定義4-3は…

$$S \rightarrow (S^*)$$

これでOK。

ということで、なんと新しい変数が出てこなかった。

改めて、このcfg$G = (V, \Sigma, P, S)$の中身について整理しよう。

まず$V$と$\Sigma$は…

$V = \{S\}$
$\Sigma = \Sigma_S \cup \{\phi, \varepsilon_s, (, ), +, \cdot, *\}$

こうなっている。

そして、生成規則$P$は、$a \in \Sigma_S$として…

$S \rightarrow \phi$
$S \rightarrow \varepsilon_s$
$S \rightarrow a$
$S \rightarrow (S + S)$
$S \rightarrow (S \cdot S)$
$S \rightarrow (SS)$
$S \rightarrow (S^*)$

この7種類で完成だ。

…さて、本当にこれでいいのだろうか。

具体例で確認してみよう。

まず、今回考える正規表現のアルファベットを…

$$\Sigma_S = \{0, 1\}$$

としておく。

これにより、cfgの生成規則が具体的になり、$S \rightarrow a$が…

$$\begin{eqnarray}
S & \rightarrow & 0 \\
S & \rightarrow & 1
\end{eqnarray}$$

この二つに置き換わり、計8個になる。

では、幾つか具体的な正規表現で、$G$から生成されるか確認してみる。

まず、シンプルに$(0 + 1)$で見てみよう。

開始記号$S$から1ステップずつ導出してみる。

$$\begin{eqnarray}
S & \Rightarrow & (S + S) \\
(S + S) & \Rightarrow & (0 + S) \\
(0 + S) & \Rightarrow & (0 + 1)
\end{eqnarray}$$

これで$S$から$(0 + 1)$が導出される…書き換えると$S \overset{*}{\Rightarrow} (0 + 1)$が分かったので、問題ない。

次に、ちょっと複雑にして…

$$((((0 + \phi) \cdot \varepsilon_s) + (11))^*)$$

という正規表現を見てみる。

同じように、開始記号$S$から1ステップずつ見ていく。

なお、どこをどう導出しているか分かるように、導出によって変わる部分を赤字にしておこう。

$$\begin{eqnarray}
\color{red}{S} & \Rightarrow & \color{red}{(S^*)} \\
(\color{red}{S}^*) & \Rightarrow & (\color{red}{(S + S)}^*) \\
((\color{red}{S} + S)^*) & \Rightarrow & ((\color{red}{(S \cdot S)} + S)^*) \\
(((\color{red}{S} \cdot S) + S)^*) & \Rightarrow & (((\color{red}{(S + S)} \cdot S) + S)^*) \\
((((\color{red}{S} + S) \cdot S) + S)^*)& \Rightarrow & ((((\color{red}{0} + S) \cdot S) + S)^*) \\
((((0 + \color{red}{S}) \cdot S) + S)^*) & \Rightarrow & ((((0 + \color{red}{\phi}) \cdot S) + S)^*) \\
((((0 + \phi) \cdot \color{red}{S}) + S)^*) & \Rightarrow & ((((0 + \phi) \cdot \color{red}{\varepsilon_s}) + S)^*) \\
((((0 + \phi) \cdot \varepsilon_s) + \color{red}{S})^*) & \Rightarrow & ((((0 + \phi) \cdot \varepsilon_s) + \color{red}{(SS)})^*) \\
((((0 + \phi) \cdot \varepsilon_s) + (\color{red}{S}S))^*) & \Rightarrow & ((((0 + \phi) \cdot \varepsilon_s) + (\color{red}{1}S))^*) \\
((((0 + \phi) \cdot \varepsilon_s) + (1\color{red}{S}))^*) & \Rightarrow & ((((0 + \phi) \cdot \varepsilon_s) + (1\color{red}{1}))^*)
\end{eqnarray}$$

これで完了だ。

以上から$S \overset{*}{\Rightarrow} ((((0 + \phi) \cdot \varepsilon_s) + (11))^*)$なので、この列も生成可能だ。

ちなみに、今は具体例で幾つか確認したのみだが、オマケでこれを数学的に証明してみようと思う。

おわりに

今回は新しい単元に進み、文脈自由文法…cfgというものを解説した。

cfgによって生成される言語を文脈自由言語と呼ぶことも覚えておこう。

また、前回の具体例で見た正規言語でないような言語を生成できることから、少なくとも正規言語と文脈自由言語は異なるものであることが分かったと思う。

では、正規言語は文脈自由言語に含まれるのだろうか。

そのあたりは、次々回で解説することになるだろう。

その前に幾つか重要な考え方があるので、次回はそれについて触れようと思う。

2021/1/26追記

次回の内容である、最左導出と導出木の解説を行った。

知っていると便利なので、是非覚えておきたい。

オマケ：正規表現を生成するcfgの証明

オマケとして、本編の具体例である、正規表現を生成するcfgが、本当に正しいものかを証明してみようと思う。

正規表現の定義は、上に書いたのでそれを参照してほしい。

で、対象となる正規表現のアルファベットを$\Sigma_S$とする。

また、そこで作ったcfg$G = (V, \Sigma, P, S)$の内訳について、$V$と$\Sigma$は以下の通り。

$V = \{S\}$
$\Sigma = \Sigma_S \cup \{\phi, \varepsilon_s, (, ), +, \cdot, *\}$

そして、$a \in \Sigma_S$として、生成規則$P$は以下の通りだった。

$S \rightarrow \phi$
$S \rightarrow \varepsilon_s$
$S \rightarrow a$
$S \rightarrow (S + S)$
$S \rightarrow (S \cdot S)$
$S \rightarrow (SS)$
$S \rightarrow (S^*)$

さて、今示したいことを明確にしておこう。

簡単に書いてしまうと、以下の式を示す。

$$x \in L(G) \Leftrightarrow x\mbox{は} \Sigma_S \mbox{上の正規表現}$$

では、始めていこう。

右向き

まずはこちらから。

ここでは$x \in L(G)$として、その$x$が$\Sigma_S$上の正規表現であることを示す。

もうちょっと書き換えると、$S$から$x$が導出されるならその$x$は正規表現、となる。

この形で、ステップ数による帰納法で証明してみよう。

まず1ステップの導出で$x$を作れるとき。

これは3パターンあり、上に書いた生成規則の上から3つ分が該当する。

これによって生成される列$x$は、以下3つのいずれか。

$x = \phi$
$x = \varepsilon_s$
$x = a$　※$a \in \Sigma_S$

これらは、明らかに正規表現の定義を満たしているので、問題ない。

次に、$n – 1$回以下のステップは成り立つと仮定し、$n$回のステップで成り立つかを見てみる。

$S \overset{*}{\Rightarrow} x$に、$n$ステップかかったとしよう。

これで、生成規則の下4つそれぞれについて見ていく。

一つ目、$S \rightarrow (S + S)$について。

このとき、列$R_1, R_2 \in \Sigma$を使って、$S \Rightarrow (S + S) \overset{*}{\Rightarrow} (R_1 + R_2) = x$というステップになっている。

この全体で$n$ステップであり、中に含まれる$(S + S) \overset{*}{\Rightarrow} (R_1 + R_2)$は必ず$n – 1$ステップだ。

すると、さらに$S \overset{*}{\Rightarrow} R_1$、$S \overset{*}{\Rightarrow} R_2$はそれぞれ$n$ステップ未満。

ということは、仮定から$R_1, R_2$はともに正規表現の定義を満たしている。

よって、正規表現の定義4-1から、$(R_1 + R_2)$も正規表現なので、$x$は正規表現だ。

残る3つの生成規則を使った場合も、まったく同じ議論ができるので問題ないと思う。

以上から、こちら側は成立だ。

左向き

今度はこちら。

ここでは、$x$が$\Sigma_S$上の正規表現であるなら、$x \in L(G)$であることを示していく。

さて、こちらも帰納法を使いたいのだが…そのために、新しく正規表現側にもステップ数の概念を導入しよう。

まず、定義1から3を使って生成できる正規表現について、これらを1ステップと定義する。

具体的には、$\phi$、$\varepsilon_s$、$a \in \Sigma_S$がそうだ。

次に、定義4の内容について、再帰的に定義する。

$R_1$を$n$ステップ、$R_2$を$m$ステップとする。

このとき、定義4-1、4-2で生成できる三つの正規表現$(R_1 + R_2)$、$(R_1 \cdot R_2)$、$(R_1R_2)$を、$n + m + 1$ステップと定義する。

また、定義4-3で生成できる正規表現$(R_1^*)$を、$n + 1$ステップとする。

具体的に、例えば$(0 + 1)$は…

$0$ : 1ステップ
$1$ : 1ステップ
$(0 + 1)$ : 1 + 1 + 1 = 3ステップ

こんなイメージだ。

では、このステップ数について帰納法を使おう。

まず、1ステップの正規表現について。

これは、上に書いた通り$\phi, \varepsilon_s, a \in \Sigma_S$の3種類がある。

それぞれ…

$S \rightarrow \phi$
$S \rightarrow \varepsilon_s$
$S \rightarrow a$　※$a \in \Sigma_S$

という生成規則があり、明らかに$G$で生成可能なので成立だ。

次に、正規表現$x$が$n$ステップとして、$n$ステップ未満の正規表現は$G$で生成可能と仮定する。

この状態で、$x$が生成可能かを見ていこう。

まず、$x = (R_1 + R_2)$という形の時。

ステップ数の定義から、$R_1$、$R_2$はともに$n$ステップ未満。

ということは、仮定から$R_1$、$R_2$は$G$で生成可能となる。

書き換えると…

$$\begin{eqnarray}
S & \overset{*}{\Rightarrow} & R_1 \\
S & \overset{*}{\Rightarrow} & R_2
\end{eqnarray}$$

という二つの導出が存在することになる。

つまり…

$$\begin{eqnarray}
S & \Rightarrow & (S + S) \\
(S + S) & \overset{*}{\Rightarrow} & (R_1 + S) \\
(R_1 + S) & \overset{*}{\Rightarrow} & (R_1 + R_2) = x
\end{eqnarray}$$

ということで、$S$から$x$が導出可能だと分かった。

よって、$x$は$G$によって生成される。

もう、後の3つは同じことをするだけなので大丈夫だろう。

つまり、正規表現を列として、$G$で生成可能だと分かった。

以上で、証明完了だ。

日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

文脈自由文法

具体例

数学的な定義

具体例で確認

正規表現を生成するcfg

おわりに

オマケ：正規表現を生成するcfgの証明

右向き

左向き

コメント