チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書換えることができるのはなぜですか？

Question

koujirou

76

68もっと見る

60pt

コンピュータ学習・教育

チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書換えることができるのはなぜですか？

できれば、いくつかの文脈自由文法を用いて説明してください。

http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E6%A8%99%E6%BA%96%E5%BD%A2

回答の条件

1人2回まで

登録：2009/02/04 16:15:08
終了：2009/02/06 14:06:35

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

コメントはまだありません

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

リクエスト送信済

回答リクエストを送信したユーザーはいません

yo-kun · Accepted Answer · 2009-02-06T05:15:09+09:00

まず定義の確認です。

文脈自由文法とは、形式文法の置き換え規則が全て

$A \to v$

という形で表されるものです。

ただし、ここで $A$ は1つの非終端記号であり、 $v$ は非終端記号と終端記号からなる長さ0以上の系列(文字列)です。

つまり、1つの非終端記号を別の何かに置き換える規則しかないものならばそれは文脈自由文法と呼びます。

一方チョムスキー標準形の定義は、形式文法の置き換え規則が

$A \to BC$

$A \to \alpha$

$S \to \epsilon$

の形からなるもののことです。

ただし $A,B,C$ は非終端記号で $\alpha$ は終端記号、 $S$ は開始記号、 $\epsilon$ は空系列です。

言い換えれば、形式文法の置き換え規則が

・1つの非終端記号を2つの非終端記号で置き換えるもの

・1つの非終端記号を1つの終端記号で置き換えるもの

・1つの開始記号を空系列に置き換えるもの

しかない場合、この形式文法をチョムスキーの標準形と呼びます。

つまりチョムスキー標準形の置き換え規則は全て1つの非終端記号を置き換えるものなので、文脈自由文法です。

(開始記号も非終端記号です)

よってご質問の前半である

「チョムスキー標準形で表される文法は全て文脈自由」

が言えるわけです。

さて、ご質問の後半部分である

「文脈自由文法はこれと等価なチョムスキー標準形の文法に書き換えることができる」

ことを示すにはやや長すぎるのでブログのほうに書きました。ご了承下さい。

以下、一般の文脈自由文法からチョムスキー標準系への変換の一例を書いておきます。

言語 $\left{ a^nb^n : n \ge 0 \right}$ を生成する文脈自由文法

$\left( \left{ S \right}, {a,b}, S, R \right)$

をチョムスキーの標準形に変換する。

ただし、置き換え規則 $R$ は

$S \to aSb$

$S \to \epsilon$

(1) 新しい開始記号の導入

新しい開始記号 $S'$ を導入して文法を次のように変換する。

$\left( \left{ S',S \right}, {a,b}, S', R_1 \right)$

ここで、置き換え規則 $R_1$ は

$S' \to S$

$S \to aSb$

$S \to \epsilon$

(2) ε規則の除去

開始記号以外からのε規則 $S \to \epsilon$ があるので、これを除去し文法を次のように変換する。

$\left( \left{ S',S \right}, {a,b}, S', R_2 \right)$

ここで、置き換え規則 $R_2$ は

$S' \to S$

$S \to aSb$

$S \to ab$

(3) 書き換え規則の除去

書き換え規則はないので除去の必要はない

(4) 長文規則の除去

長文規則 $S \to aSb$ があるので、これを除去し文法を次のように変換する。

$\left( \left{ S',S,U_1,U_2 \right}, {a,b}, S', R_3 \right)$

ここで、置き換え規則 $R_3$ は

$S' \to S$

$S \to aU_1$

$U_1 \to SU_2$

$U_2 \to b$

$S \to ab$

(5) 最終処理

終端処理を含む2文字への置き換え $S \to aU_1$ の代わりに

$S \to U_3U_1$

$U_3 \to a$

を導入し、終端処理2文字への置き換え $S \to ab$ の代わりに

$S \to U_4U_5$

$U_4 \to a$

$U_5 \to b$

を導入する。

以上によりチョムスキー標準形の形式文法

$\left( \left{ S',S,U_1,U_2,U_3,U_4,U_5 \right}, {a,b}, S', R_4 \right)$

ここで、置き換え規則 $R_4$ は

$S' \to S$

$S \to U_3U_1$

$U_3 \to a$

$U_1 \to SU_2$

$U_2 \to b$

$S \to U_4U_5$

$U_4 \to a$

$U_5 \to b$

を得る。

チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書換えることができるのはなぜですか？

ベストアンサー

yo-kun220302009/02/06 05:15:09

コメント（0件)

この質問への反応（ブックマークコメント）