東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問7

标签：

• TITech
• Context-Free-Grammar
• Pumping-Lemma

Author

GPT-5

Description

次の文脈自由文法 を考える。ただし、開始記号は である。

例えば、 および は が生成する文字列である。以下の問いに答えよ。

1. 文字列 に含まれる の個数を 、 の個数を とし、 と定める。 が生成する任意の文字列 について となることを示せ。
2. が生成する言語が正規言語でないことを、正規言語の反復補題を用いて示せ。
3. が生成するある文字列の空でない接頭辞全体を生成する文脈自由文法 を示せ。
4. が生成する任意の文字列 と、空でない文字列 に対して、 は が生成する文字列ではないことを示せ。

Kai

(1)

生成規則に関する構造帰納法で示す。

• のとき、 である。

• のとき、 は と のどちらにも影響しないため、値は変わらない。

• のとき、二つの部分式を とすれば、帰納法の仮定から

したがって、 が生成するすべての文字列 について である。

(2)

が正規言語であると仮定し、その反復長を とする。文字列

は、 個の式 を で順に結合した後置記法の式なので である。

反復補題によって 、、 と分解できる。このとき最初の 文字はすべて なので、ある に対して である。 を 0 回反復すると

(1) より であり、反復補題に矛盾する。ゆえに は正規言語ではない。

(3)

次の文法を用いればよい。開始記号は とする。

この文法は、一つ以上の完全な式を並べた文字列 を生成する。

後置記法を左から読んだとき、正しい式の空でない接頭辞を読み終えたスタックには、未結合の完全な式が 個残っている。したがって、その接頭辞は と表せる。逆に、このような文字列の末尾に を付ければ一つの式に結合できるので、生成された文字列は必ず のある文字列の接頭辞である。

(4)

と仮定する。 は正しい後置式の空でない接頭辞なので、(3) の議論から

である。一方、 なので (1) より である。したがって

となり、(1) の必要条件 に矛盾する。よって である。