本シリーズでは、以下の本に沿って解説を書いている。
前回はプッシュダウンオートマトンという新しいものを解説した。
以前の有限オートマトンとは似て非なるものなので、しっかり区別して進めていこう。
参考書の定義から少し変えているので、そちらも見ている方は気を付けていただきたい。
以下がその記事だ。
さて、前回の内容でプッシュダウンオートマトンが何者かは分かった。
しかし、どうやってそれを作ればいいかがいまいちピンと来ないと思う。
そこで、今回はその作り方の部分を見てみよう。
pdaの設計とは
これまでもdfa、nfaなど、色々なオートマトンを解説してきた。
それらの時は、具体的に状態遷移図を書いたり、状態遷移関数を決めたりして作っていた。
しかし、このpdaは簡単な動作をするものでも状態遷移関数が多く、また複雑になりやすく、実際にそれで作ろうとするのはあまり現実的ではない。
まあ、実際に使う際にはこれをしなければいけないのだが…いきなり作れと言われても無理だろう。
そこで、ちょうどいい詳しさでそのpdaの動作を説明することで、その動き方を表現しよう、ということになる。
そこから状態遷移関数に落とし込めば完成、という状況まで持っていくようなイメージだ。
ちょうどいい詳しさって何だよと思われるかもしれないが…そこは要訓練だと参考書に書かれている。
数をこなして慣れていくのが一番かもしれない。
guess
内容に入る前に、一つだけ解説を。
今後、guess(読み：ゲス)という言葉を多用することになると思う。
これは、特に理由なく推測する、という意味で使わせてもらう。
なぜそれをするのかについては、設計方法の中で。
pdaの設計方法
では、大まかな設計方法を解説していこう。
ある言語\(L\)を認識するpdaを設計する際には、ある入力記号を読む時にどんな状況であるか、というのを考える。
で、その状況によってどうするか、という動作を説明していくことになる。
…ちょっと、言葉だけでは説明が難しすぎるので、幾つか具体例を通して解説していこう。
pdaの設計具体例その1
まずは、以下の言語\(L\)を認識するpdaを設計してみよう。
$$L = \{xx^R | x \in \{a, b\}^*, |x| > 0\}$$
これはある列とその逆を連接させたような列からなる言語で、今回は空列を省いている。
これで、具体的な列をpdaで読み込むことを考える。
このとき、列をちょうど真ん中で区切ると、前半は読んだ入力記号に対応したスタック記号をプッシュし、後半では対応するスタック記号をポップすればいいだろう。
スタックの性質上、下から順番にプッシュし、上から順番にポップするので、それを使えばうまく判定できる。
ただ、一番最初だけはスタック初期記号\(Z_0\)を対応するスタック記号に置き換える必要がある。
例えば、列\(abaaaaba\)を読む時、最初の\(a\)だけ\(Z_0\)を置き換え、そこから前半の\(baa\)まではスタックに記号をプッシュしていく。
そして、その次(全体で見れば5個目の記号)の\(a\)を読む時点で後半にモードチェンジし、スタックから対応する記号をポップする。
以降は、そのまま対応している記号を取り出せば綺麗に受理される。
…これをそのままやろうとすると、上手くいかないのが分かるだろうか。
pda\(M\)にとっては、今読んでいる入力記号が真ん中かの目印がないのだ。
そのため、上のままでは最初1文字だけは問題ないが、その後はどこでモードを変えればいいかが分からない。
よって、何かしらの方法でそれを判別…するのではなく、ここでguessというものを使う。
このguessは動作の分かれ道を作るようなイメージで、今回の場合で言うと前半モードの時に読み込む入力記号が、後半の先頭かどうかで分岐させる。
そこで、後半の先頭だと仮定して一旦議論を進めるのだが、このことを後半の先頭だとguessする、という言い方になる。
状態遷移関数に関連付けて考えると、一つの対応元の組に、複数の対応先を含ませる部分になる。
ここで後半の先頭だとguessすれば、上に書いたようにそこから後半モードにチェンジして対応するスタック記号をポップする。
後半の先頭でない…つまり、まだ前半だとguessすれば、これまた上に書いた通りだが対応するスタック記号をプッシュだ。
こうするとどうなるか、具体的な列を読みながらその様子を見てみよう。
まず、シンプルに\(aa\)という列について。
先頭は、スタック初期記号\(Z_0\)を対応するものに置き換えるだけなので、\(A\)に置き換えてみよう。
次の\(a\)を読む時に、まず後半の先頭だとguessしてみる。
すると、状態が変化し、今度は\(a\)に対応する\(A\)をポップすることになる。
今は先頭が\(A\)なので、問題ない。
そして、それで全てを読み終え、スタックも空になったのでOKだ。
上手くいったがちょっと味気ないので、もう少し長い列でやってみる。
\(abba\)でやってみよう。
最初は同じように先頭の\(a\)を読んでスタックを\(Z_0\)から\(A\)に置き換え。
次の\(b\)について、後半の先頭だとguessしてみると、今スタックの先頭は対応していない\(A\)になっているので不適。
つまり、ここではまだ前半だとguessすることになる。
よって、対応する記号\(B\)をスタックにプッシュして続きへ進む。
今のスタックは、先頭から\(BA\)だ。
さらに次の(全体で見ると3文字目の)\(b\)を読む。
ここも後半の先頭だとguessして進めてみよう。
状態が後半モードに変わり、スタックの先頭から対応する\(B\)をポップする。
これで、スタックの中身は\(A\)のみ。
最後の\(a\)を読む時は後半モードなので、対応する記号\(A\)を取り除く。
すると、綺麗にスタックの中身が空になったので、OKだ。
ここまで受理される例を見てみたが、今度は受理されない例を見てみる。
\(abbaa\)で見てみよう。
先頭はやはり変わらず\(a\)を読んでスタックの\(Z_0\)を\(A\)に置き換え。
次の\(b\)は先ほどと同じ理由で後半の先頭とguessはできないので、前半モードのままスタックに\(B\)をプッシュ。
3文字目の\(b\)からが本番だ。
まずは上と同じくここから後半モードに変わるとguessすると、スタックの先頭から\(B\)をポップすればいい。
これで4文字目の\(a\)を読めば、スタックから\(A\)をポップし、この時点でスタックが空になる。
しかし、5文字目が残ってしまったので、このルートはNGだったようだ。
最後にguessしたところを見ると、3文字目の\(b\)の時点。
今度は、まだ前半モードだとguessして続けよう。
\(B\)をスタックにプッシュし、この時点でのスタックは上から\(BBA\)だ。
ここで4文字目\(a\)を読む時に後半モードになるとguessすると、先頭が\(B\)なので不適、これも前半モードとguessすることになる。
今のスタックは\(ABBA\)となっている。
さて、最後の\(a\)は、どちらをguessしてもスタックを空にできないことは明らかだろう。
ここから後半モードになるとすると先頭の\(A\)をポップするが、スタックには\(BBA\)が残ったまま。
まだ前半モードとしてスタックに\(A\)をプッシュしても、\(AABBA\)がスタックにある状態で入力列が無くなった。
よって、どんなguessのルートを辿っても入力列とスタックの両方を空にはできなかったので、この列は受理されない。
これで、なんとなく分かっただろうか。
具体的な列\(x\)において全てのguessルートを確認し、一つでも入力列とスタックの両方を空にすることができるようなルートが存在すれば、またその時に限って列\(x\)は\(M\)で受理される、という形になる。
以上でpda\(M\)の動作説明は完了となる…のだが、折角なのでここから具体的な\(M\)を構成してみよう。
構成するpdaを\(M = (K, \Sigma, \Gamma, \delta, s_0, Z_0)\)として、前者三つを以下のように置く。
- \(K = \{s_0, s_1\}\)
- \(\Sigma = \{a, b\}\)
- \(\Gamma = \{A, B, Z_0\}\)
このようにしている理由を少し補足。
まず状態については、今説明の中で前半モードと後半モードがあるという書き方をした。
それに倣い、二つの状態を持たせている。
初期状態である\(s_0\)が前半モード、\(s_1\)が後半モードだ。
入力記号の集合は言語の定義からこれで問題ないことは明らかだろう。
スタック記号の集合は、入力記号の\(a\)を\(A\)に、\(b\)を\(B\)に対応させることを意図している。
そして、それ以外に一つスタック初期記号\(Z_0\)が必要だったことを思い出そう。
では、これらを使って状態遷移関数を定義していく。
説明で書いた処理の流れ順に見ていこう。
まず、先頭は単純にスタック初期記号を対応するスタック記号に置き換える、という操作だった。
記号は\(a\)、\(b\)の二つあるので、それぞれに定義をしてあげると…
- \(\delta(s_0, a, Z_0) = (s_0, A)\)
- \(\delta(s_0, b, Z_0) = (s_0, B)\)
この二つになる。
次に前半モード、ここでguessによる分岐が発生していた。
その記号が後半に差し掛かっていれば状態を後半へ、スタックの先頭から対応する記号をポップする。
その記号がまだ前半なら状態は変化させず、スタックの先頭に対応する記号をプッシュする。
これを、まず記号\(a\)を読んだ場合で書いてみると…
- \(\delta(s_0, a, A) = \{(s_1, \varepsilon), (s_0, AA)\}\)
- \(\delta(s_0, a, B) = \{(s_0, AB)\}\)
この二つだ。
対応先の状態が\(s_1\)のものがその記号を後半とするguess、対応先の状態が\(s_0\)のものがその記号をまだ前半とするguessを表している。
\(\delta(s_0, a, B)\)の中に状態\(s_1\)のものがない理由は、この時はスタックの先頭が\(A\)ではないので、操作である\(A\)のポップを行えないことにある。
その時はそこで停止する、つまり状態遷移をそれ以上続けられないことを表しており、その遷移は書かない。
\(b\)についてのものも書いておこう。
- \(\delta(s_0, b, A) = \{(s_0, BA)\}\)
- \(\delta(s_0, b, B) = \{(s_1, \varepsilon), (s_0, BB)\}\)
最後に、後半モードの操作。
ここでは対応するスタックの先頭をポップするだけなので、以下二つになる。
- \(\delta(s_1, a, A) = \{(s_1, \varepsilon)\}\)
- \(\delta(s_1, b, B) = \{(s_1, \varepsilon)\}\)
例えば\(\delta(s_1, a, B)\)については、スタックの先頭が\(A\)ではないのでポップできず、そこで停止…言い換えればそこからの遷移はできないので、\(\delta(s_1, a, B) = \phi\)となっている。
これで、説明の中で書いていた操作全てを状態遷移関数に変換したことになる。
一覧で出してみよう。
- \(\delta(s_0, a, Z_0) = (s_0, A)\)
- \(\delta(s_0, b, Z_0) = (s_0, B)\)
- \(\delta(s_0, a, A) = \{(s_1, \varepsilon), (s_0, AA)\}\)
- \(\delta(s_0, a, B) = \{(s_0, AB)\}\)
- \(\delta(s_0, b, A) = \{(s_0, BA)\}\)
- \(\delta(s_0, b, B) = \{(s_1, \varepsilon), (s_0, BB)\}\)
- \(\delta(s_1, a, A) = \{(s_1, \varepsilon)\}\)
- \(\delta(s_1, b, B) = \{(s_1, \varepsilon)\}\)
これで、pdaの完成だ。
実際に幾つか列を用意して、受理様相までたどり着けるかやっておくといいだろう。
pdaの設計具体例その2
今度は、以下の言語\(L\)を認識するpdaを設計してみる。
$$L = \{0^n1^m | n \not = m\}$$
0と1からなる列で、前半は0、後半は1が続くが、その個数が異なるような列からなる言語だ。
例えば、\(0\)、\(1\)はそうだし、他にも\(00111\)とか、\(000001\)なども含まれる。
では、設計を始めよう。
初っ端だが、guessをする必要がありそうだ。
何をguessするかというと、\(n\)と\(m\)の大小比較。
先に、\(n > m\)をguessして議論を始めてみる。
この時は\(0\)の個数の方が大きくなり、以下の方針でいけそうだ。
- 最初の\(0\)は確定で読み飛ばす
- 途中のある時点(そこからの\(0\)と\(1\)の個数が同じになるところ)まで\(0\)を読み飛ばす
- そこから\(0\)を一個読むごとにスタックへ記号を一つプッシュし、\(1\)を一個読むごとにスタックから記号を一つポップする
ただし、\(1\)の後に\(0\)が出てきたら、その時点で動作を終了する(=非受理とする)
さて、この中にもguessが一つ必要なところがあるのが分かるだろうか。
二つ目の、ある時点がどこかが分からないのだ。
つまり、そこで読む記号\(0\)がまだ読み飛ばすものか、次の状態へ進むものかをguessしなければならない。
ということで、ここではその時点以降の\(0\)と\(1\)の個数が同じか、\(0\)の方がまだ多いかでguessをする。
今読もうとしている\(0\)を含め、まだ\(0\)の個数の方が多いとguessすれば、その\(0\)はやはり読み飛ばされる。
\(0\)と\(1\)の個数が同じだとguessすれば、そこから次のモードに入り、記号をプッシュし始める。
…ちなみに、最初に\(0\)を一個読み飛ばしている部分だが、これで数の調整をしている。
もしこれがないと、\(n = m\)も上の方針で受理様相まで行けてしまうので、それを防ぐために\(0\)を多く読み取るようにしている。
これで、\(n > m\)とguessしたパターンは完了だ。
今度は、\(n < m\)とguessした場合を見ていこう。
この時は、以下のような方針になる。
- \(0\)を読むごとに記号をプッシュする
- 最初に\(1\)を読んだ時、その最初の\(1\)は読み飛ばす
- 次以降、今読もうとしている\(1\)以降の数が\(0\)の数と同じかguessし、まだ\(1\)の方が多ければ読み飛ばし、同じなら記号をポップする
これで問題ない。
\(1\)の後に\(0\)が来るパターンを見ていないが、その時はすでにスタックの中身が空になっているので、どのみち先に進むことができなくなる。
では、これで問題ないかを軽く説明してみよう。
まず列\(x \in L\)が受理されることの確認。
\(i\)を自然数、\(j\)を0以上の整数として、\(x = 0^i0^j1^j\)としてみる。
このとき、最初のguessは\(i + j = n > m = j\)なので、前半に説明した処理に入る。
ここから\(0^i\)の部分を読んでいる間はまだ\(0\)が多いというguess、\(0^j\)の先頭を読む段階で\(0\)と\(1\)の個数が一致するというguessをすることで、問題なく最後にはスタックが空になることが分かる。
また、その時点でスタックが空なので、その後に\(0\)が出てきた瞬間、そこからは何も遷移できない。
次に、\(x = 0^j1^i1^j\)について。
こちらは、最初のguessは\(j = n < m = i + j\)なので、後半に説明した処理。
まず\(j\)個の記号をスタックにプッシュするところまでは一本道だ。
次に、\(i\)を残り\(j\)個になるまで読み飛ばし、残り\(j\)個になった段階でguessによりポップするモードに変えてあげればこちらもスタックが空になる。
もちろん、もしその後に\(0\)が来ていればそれ以上遷移できないので受理されなくなる。
ここまでで、意図した列が受理されることが分かった。
あとは、意図しない列が受理されないこと。
上の説明の中で\(0^n1^m\)以外の形は受理されないことが分かっているので、残っているのは\(0^i1^i\)のパターン。
これは、まず\(0\)の方が多いとguessすると、操作内で\(0\)を一つ読み飛ばすことにより、そこからの\(0\)の個数は\(1\)の個数未満となる。
つまり、操作で出てきている\(0\)と\(1\)の個数が一致するというguessができず、そこから次の操作に進むことができない。
スタックからのポップはその次の操作でしかやっていないので、スタックが空になることはなく、受理されない。
次に\(1\)の方が多いとguessすると、\(0\)を読んでいる部分はそのままスタックに追加しながら進む。
…のだが、\(1\)の先頭を読み飛ばした時点で、こちらも次の操作に進むようなguessができなくなる。
よって、スタックが空になることがなく、こちらでも受理されないことが分かった。
以上で、意図した列のみがしっかり受理されるよう設計できた。
ここまでが参考書の説明。
…ここから実際にpdaを作ってみたのだが、参考書の説明では足りないように思っている。
というのも、pdaの作り方が悪かったのか分からないが、\(0^n\)や\(1^m\)の時の動作が別で必要なのではないか、という点が気になった。
pdaではそれも入れて組んでいるので、見てもらえればどんな説明になるかは分かると思う。
では、その具体的なpdaを見てみよう。
まずpdaを\(M = (K, \Sigma, \Gamma, \delta, s_0, Z_0)\)とし、前半三つを以下のようにする。
- \(K = \{s_0, s_1, s_2, s_3, s_4, s_5, s_6, s_7, s_8\}\)
- \(\Sigma = \{0, 1\}\)
- \(\Gamma = \{A, Z_0\}\)
で、状態遷移関数を…細かく作る様子をお見せすると記事が長くなってしまうので、結果だけ載せて、代わりにこれでいいことを証明してみよう。
- \(\delta(s_0, 0, Z_0) = \{(s_1, Z_0), (s_4, A), (s_7, Z_0)\}\)
- \(\delta(s_0, 1, Z_0) = \{(s_8, Z_0)\}\)
- \(\delta(s_1, 0, Z_0) = \{(s_1, Z_0), (s_2, A)\}\)
- \(\delta(s_2, 0, A) = \{(s_2, AA)\}\)
- \(\delta(s_2, 1, A) = \{(s_3, \varepsilon)\}\)
- \(\delta(s_3, 1, A) = \{(s_3, \varepsilon)\}\)
- \(\delta(s_4, 0, A) = \{(s_4, AA)\}\)
- \(\delta(s_4, 1, A) = \{(s_5, A)\}\)
- \(\delta(s_5, 1, A) = \{(s_5, A), (s_6, \varepsilon)\}\)
- \(\delta(s_6, 1, A) = \{(s_6, \varepsilon)\}\)
- \(\delta(s_7, \varepsilon, Z_0) = \{(s_7, \varepsilon)\}\)
- \(\delta(s_7, 0, Z_0) = \{(s_7, Z_0), (s_7, \varepsilon)\}\)
- \(\delta(s_8, \varepsilon, Z_0) = \{(s_8, \varepsilon)\}\)
- \(\delta(s_8, 1, Z_0) = \{(s_8, Z_0), (s_8, \varepsilon)\}\)
これで言語\(L\)を認識することを証明するために、入力列を以下9つのパターンに分ける。
- \(x = 0^i0^j1^j\) ※OK
- \(x = 0^i0^j1^j0y\) ※NG
- \(x = 0^j1^i1^j\) ※OK
- \(x = 0^j1^i1^j0y\) ※NG
- \(x = 0^j1^j\) ※NG
- \(x = 0^j1^j0y\) ※NG
- \(x = 0^j\) ※OK
- \(x = 1^j\) ※OK
- \(x = 1^j0y\) ※NG
ただし、全てにおいて\(i\)と\(j\)は自然数、\(y \in \Sigma^*\)とする。
では順番に見ていこう。
パターン1、\(x = 0^i0^j1^j\)から。
これは単に以下のステップが存在するのでOKだ。
$$\begin{eqnarray}
(s_0, 0^i0^j1^j, Z_0) & \Rightarrow & (s_1, 0^{i-1}0^j1^j, Z_0) \\
& \overset{*}{\Rightarrow} & (s_1, 0^j1^j, Z_0) \\
& \Rightarrow & (s_2, 0^{j-1}1^j, A) \\
& \overset{*}{\Rightarrow} & (s_2, 1^j, A^j) \\
& \Rightarrow & (s_3, 1^{j-1}, A^{j-1}) \\
& \overset{*}{\Rightarrow} & (s_3, \varepsilon, \varepsilon)
\end{eqnarray}$$
パターン2、\(x = 0^i0^j1^j0y\)でこれは受理されたくない。
で、本来であれば全てのパターンを試していきたい…のだが、とんでもないことになるのは想像に難しくない。
そこで、それぞれどうなるか、感覚的な説明に留めさせてもらおう。
まず初期状態\(s_0\)、これは遷移先には一切登場していないので、最初の分岐だけ考えればいい。
最初に使う状態遷移は一番上しかあり得ず、ここで三つに分岐する。
一つ目、状態の遷移先が\(s_1\)に入ったとすると、上のステップと同じような流れを行うことになる。
この\(s_1\)からも二つに分岐し、そのまま読み飛ばすか状態を変え\(A\)をプッシュするかの2択。
ここで\(s_1\)のままの選択をし続けると\(Z_0\)が残ったままになるので不適。
途中で\(A\)をプッシュし、\(s_2\)に移る。
ここは\(0\)が続く限り\(A\)をプッシュし続け、\(1\)が出たら状態を変えてポップモードの\(s_3\)へ。
\(s_3\)は\(1\)を読むごとに\(A\)をポップするだけだ。
この流れを見ると、そもそも\(1\)が出てくると状態は必ず\(s_3\)にいるが、その後に\(0\)が出てきた時の遷移がない。
ということで、このパターンでは受理様相に到達できない。
では、最初の分岐を\(s_4\)への遷移で変化したとしよう。
この時は、いきなり\(0\)を読むごとに\(A\)をプッシュしていく。
ここで最初の\(0^i0^j\)を読むと、スタックには\(A^{i + j}\)が入っている。
その後は、一回\(1\)を読んで状態だけ\(s_5\)に変化、その後そのまま読み飛ばすか状態を\(s_6\)に変えて\(A\)をポップする、という動作のみ可能。
で、ここでポップできる個数を見ると、最大でも\(j – 1\)個だ。
それよりもスタック内の記号の方が多いので、入力列よりも先にスタックが空になってしまう。
今度は、最初の分岐を\(s_7\)にしてみよう。
ここでは何も読まずにスタックから\(Z_0\)をポップするか、\(0\)を読み飛ばすか、\(0\)を読んで\(Z_0\)をポップするかの3択。
一つ目は明らかに入力列が残り、それ以外では\(1\)を読んで進むことができない。
以上から、このパターンは受理できないということが分かった…だろうか。
不安なら、具体的な列で実際にステップを試してみるといいだろう。
では3つ目のパターン、\(x = 0^j1^i1^j\)に進もう。
これは受理されればOKで、実際以下のような受理様相までのステップが存在する。
$$\begin{eqnarray}
(s_0, 0^j1^i1^j, Z_0) & \Rightarrow & (s_4, 0^{j-1}1^i1^j, A) \\
& \overset{*}{\Rightarrow} & (s_4, 1^i1^j, A^j) \\
& \Rightarrow & (s_5, 1^{i-1}1^j, A^j) \\
& \overset{*}{\Rightarrow} & (s_5, 1^j, A^j) \\
& \Rightarrow & (s_6, 1^{j-1}, A^{j-1}) \\
& \overset{*}{\Rightarrow} & (s_6, \varepsilon, \varepsilon)
\end{eqnarray}$$
4つ目、\(x = 0^j1^i1^j0y\)。
二つ目の時と同じように分岐するのだが…最初の三つの分かれ道のうち、一つ目と二つ目は逆のことが起こり、三つ目は先ほどと同じ。
ということで受理できないことが分かるので省略してしまおう。
5つ目、\(x = 0^j1^j\)。
これまた最初の分岐三つを見ていくが、やはり三つ目は\(0\)の後に\(1\)が出てきたらNGなのは変わらないのでいいだろう。
一つ目に入った時、流れを追ってもらえれば分かるが、最大でも\(A\)をプッシュできるのは\(j-1\)回。
ポップは必ず\(j\)回行われるので、入力列が残った状態でスタックが空になってしまう。
二つ目に入った時、今度はプッシュは\(j\)回行われる。
しかし、ポップの方が最大\(j-1\)回なので、先ほどとは逆にスタックがある状態で入力列が空列に。
ということで、これも受理されなかった。
6つ目、\(x = 0^j1^j0y\)。
5つ目の後ろに0から始まる列がくっついているパターンで、これも受理してほしくない。
とはいえ、5つ目の説明から\(0^j1^j\)の部分ですでにそれ以上遷移できない状態になってしまっているので、これも受理されないのは明らかだろう。
7つ目、\(x = 0^j\)はOKのパターン。
受理様相までのステップを作ろう。
$$\begin{eqnarray}
(s_0, 0^j, Z_0) & \Rightarrow & (s_7, 0^{j-1}, Z_0) \\
& \overset{*}{\Rightarrow} & (s_7, 0, Z_0) \\
& \Rightarrow & (s_7, \varepsilon, \varepsilon)
\end{eqnarray}$$
これでOK…なのだが、実は\(x = 0\)の時だけステップが異なる。
$$\begin{eqnarray}
(s_0, 0, Z_0) & \Rightarrow & (s_7, \varepsilon, Z_0) \\
& \Rightarrow & (s_7, \varepsilon, \varepsilon)
\end{eqnarray}$$
いずれにしろ受理状態まで遷移できたのでOKだ。
8つ目、\(x = 1^j\)、これも受理されてほしい。
ここも7つ目と同じく\(j\)が1か2以上かで分岐する。
$$\begin{eqnarray}
(s_0, 1, Z_0) & \Rightarrow & (s_8, \varepsilon, Z_0) \\
& \Rightarrow & (s_8, \varepsilon, \varepsilon)
\end{eqnarray}$$
$$\begin{eqnarray}
(s_0, 1^j, Z_0) & \Rightarrow & (s_8, 1^{j-1}, Z_0) \\
& \overset{*}{\Rightarrow} & (s_8, 1, Z_0) \\
& \Rightarrow & (s_8, \varepsilon, \varepsilon)
\end{eqnarray}$$
両方とも問題なし。
ラストの\(x = 1^j0y\)、これは8つ目のパターンを見ればほぼ明らかだろう。
そもそも先頭が\(1\)の場合は状態\(s_8\)に遷移する。
ここからは記号を読まずにスタックを取り除くか、\(1\)を読み飛ばすか、\(1\)を読んでスタックを取り除くか。
最初\(1\)を読み飛ばしたとしても\(0\)を読み込むことができないので、これも受理されない。
長くなってしまったが、以上で意図した列のみを受理できることが証明できた。
やはり不安なら、具体的な列でステップを作ってみて欲しい。
おわりに
今回は、pdaをどうやって作るか…というより、その動き方を設計するようなことをしてみた。
最悪、guessを使った議論がどうなっているかだけ見てもらえればOKだ。
参考書にも書かれているが、これは経験を積むしかない。
特にguessは慣れないとなかなかに曲者で、実際にそこからpdaを組む際には要注意だろう。
私自身まだまだ経験不足なこともあり、今後もいくつか設計しつつ感覚を掴んでいくことにする。
可能ならパスしたかったが、次回以降の内容にもguessが出てきそうだったので解説した、というわけだ。
さて、次回はちょっと面白いことをしてみよう。
なんと、どんなpdaに対しても、状態数が1つで同じ言語を認識するpdaが存在するのだ。
言い換えると、スタックの出し入れだけを使って状態まで表現することができてしまう。
そんな内容に進んでいくこととしよう。
コメント