文脈自由言語とプッシュダウンオートマトン

スポンサーリンク

文脈自由言語

文脈自由言語とは主に以下のように定義されます。

ある文法\(g=[T,N,σ,P]\)において、\(P\)が含む全ての\(α → β\)が\(α \in N\)かつ\(β \in (N \cup T)^*\)を満たすとき、\(g\)は文脈自由文法(context-free)である。
ある言語\(L\)において、\(L = L(g)\)となるような文脈自由文法\(g\)が存在するならば、\(L\)は文脈自由 (context-free) 言語であると言う。

では、以前にご紹介した正規言語(regular)の生成規則と見比べてみましょう。

正規言語(regular)では\(β\)の条件が\(β \in T^* \cup T^*U\)となっていました。ここが\(β \in (N \cup T)^*\)に変わっています。

正規言語の場合、開始記号が\(σ\)、終端記号が\(\{a,b\}\)、非終端記号が\(\{σ\}\)とした場合に終端記号が続いた後に非終端記号を一つ入れるか入れないかしか選べませんでした。

例:\(P=\{σ→a,σ→b,σ→aσ,\}\)

これが文脈自由言語の場合だと、以下のようなものを定義できるようになります。

例:\(P=\{σ→aσb,σ→λ\}\)

ここで\(λ\)(ラムダ)空文字を意味し、何も文字を入力しないことを意味します。

正規表現では、終端文字か、終端文字→非終端文字しか選べなかったのに対し、文脈自由言語だとそれに加え、非終端文字の後に終端文字を定義することが可能となります。

では例を見てみましょう。

\(P=\{σ→ab,σ→aσb\}\)である文法\(g=[\{a,b\},\{σ\},σ,P]\)から生成できる\(L(g)\)をもとめる。

文法に従うと、開始記号は\(σ\)なので、まずは

\(L(g)=σ\)

となります。次に生成規則\(P=\{σ→ab,σ→aσb\}\)ですが、これは\(σ\)を\(ab\)または\(aσb\)に置き換えることを意味しています。よって、

\(L(g)=ab\)・・・(a)

または

\(L(g)=aσb\)・・・(b)

となります。
(a)については\(a,b\)ともに終端記号のため、ここで終わりです。

(b)についてみてみましょう。

(b)内にはまだ非終端記号の\(σ\)が含まれています。ですから再び生成規則\(P=\{σ→ab,σ→aσb\}\)を適用してみましょう。\(σ\)を\(ab\)または\(aσb\)に置き換えれば良いので、

\(L(g)=aabb\)・・・(c)

または

\(L(g)=aaσbb\)・・・(d)

となります。(c)はここで終わりですが、(d)はまだ続けることができそうです。このようにして\(\{σ→aσb\}\)を適用し続けると、

\(L(g)=aaa・・・aσb・・・bbb\)

と、中心から左に\(a\)を、右に\(b\)を展開することができ、最後に\(\{σ→ab\}\)を適用することで、

\(L(g)=aaa・・・ab・・・bbb\)

となることが予測できます。

これを一般式で表すと

\(L(g)=\{a^n b^n | n \geq 1\}\)

と表せ、これは文脈自由言語と言えます。

正規言語と文脈自由言語

正規言語と文脈自由言語の関係についてですが、\(P\)の定義を見てみると、文脈自由言語のほうが正規言語よりも表現できる幅が広いことが分かります。

例:\(L(g)=\{a^n b^n | n \geq 1\}\)は文脈自由言語であるが、正規言語ではない。

このことから、\(正規言語(Reg) \subset 文脈自由言語(cf)\)つまり、全ての正規言語は文脈自由言語であり、文脈自由言語の中の一部が正規言語であるといえます。

プッシュダウンオートマトン(PDA)

プッシュダウンオートマトン(PDA)とは、通常のオートマトンに加え、スタックを持つオートマトンの事を指します。

スタックに関してはこちらを参照して頂きたいのですが、所謂後入れ先出し法(Last In, First Out)と呼ばれるもので、後から入れたものが先に出される事をいい、積み上げられた本をイメージすると分かりやすいかと思います。

ではスタックを用いてどのような動きをするのか、直感的に見てみましょう。

図は先ほどの例の\(L(g)=\{a^n b^n | n \geq 1\}\)をプッシュダウンオートマトンで表したものです。

\(a\)を入力するたびにスタックに\(0\)をプッシュ(入れること)し、\(b\)を入力するたびにスタックから\(0\)をポップ(取り出すこと)します。

そして受理状態において、スタックが空の時のみ受理されます。

文脈自由言語とPDAの関係

文脈自由言語を特徴付けるものとしてオートマトンを拡張させたものがプッシュダウンオートマトンです。要するに、文脈自由言語の全てをプッシュダウンオートマトンで表現することができます

例えば\(L(g)=\{a^n b^{2n} | n \geq 1\}\)の場合、\(a\)一つの入力に対し、\(0\)を二つプッシュし、\(b\)一つの出力に対し\(0\)を一つポップする処理を行えば実装が可能です。

また、\(L(g)=\{ww^t|w \in \{0,1\}^*\}\)で定義されるような回文と呼ばれるもの(日本語だと”しんぶんし”や”やおや”のように上から読んでも下から読んでも同じになる言葉)の場合、スタックする文字の種類を増やし、入力記号の中間と思われるところでポップを行い、読み込まれた記号とポップ記号が対応しているか否かで動作確認をする方法をとることで、回文も文脈自由言語だという結果にたどり着きます。

言葉だけでは難しいので、\(\{a,b,a,a,b,a\}\)の受理過程を見てみましょう。

入力がない状態からまず\(♯\)をスタックにプッシュします。

次に文字が入力されるたびに対応する記号をスタックにプッシュします。(\(a\)ならば\(0\)、\(b\)ならば\(1\))

毎回、入力記号の中間に達したと仮定して分岐し、それ以降では入力が読み込まれる度に逆にポップし、読み込まれた記号とポップ記号が対応しているかを判定します。その際、入力は空(カラ)を意味するεを入力します。

以下にシミュレーション図を描きます。()内の左が状態、右がスタックの状態を指しています。

以上のようにして、回文も文脈自由言語であることが分かります。

スポンサーリンク

投稿者: TS

ゲームと数学のことを主に書いてます! アドバイスやご指摘があれば是非お願いします!!

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA