跳到主要内容

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

标签：

Author​

GPT-5

Description​

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

E→1∣EE+∣E−E \to 1 \mid EE+ \mid E-

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

  1. 文字列 ww に含まれる 11 の個数を #1(w)\#_1(w)、++ の個数を #+(w)\#_+(w) とし、#(w)=#1(w)−#+(w)\#(w)=\#_1(w)-\#_+(w) と定める。GG が生成する任意の文字列 ww について #(w)=1\#(w)=1 となることを示せ。
  2. GG が生成する言語が正規言語でないことを、正規言語の反復補題を用いて示せ。
  3. GG が生成するある文字列の空でない接頭辞全体を生成する文脈自由文法 G′G' を示せ。
  4. GG が生成する任意の文字列 ww と、空でない文字列 w′w' に対して、w′ww'w は GG が生成する文字列ではないことを示せ。

题目描述​

考虑开始符号为 EE 的上下文无关文法 GG：

E→1∣EE+∣E−.E\to1\mid EE+\mid E-.

例如，111++111++ 与 11+−11+- 都是 GG 生成的字符串。回答：

  1. 对字符串 ww，分别以 #1(w)\#_1(w)、#+(w)\#_+(w) 表示其中字符 11、++ 的个数，并定义

    #(w)=#1(w)−#+(w).\#(w)=\#_1(w)-\#_+(w).

    证明 GG 生成的每个字符串 ww 都满足 #(w)=1\#(w)=1。

  2. 使用正则语言的抽引引理，证明 GG 生成的语言不是正则语言。

  3. 给出一个上下文无关文法 G′G'，它生成“某个由 GG 生成的字符串的所有非空前缀”所组成的语言。

  4. 证明：对任意由 GG 生成的字符串 ww 和任意非空字符串 w′w'，拼接串 w′ww'w 都不可能由 GG 生成。

考点​

  • 上下文无关文法的结构归纳：沿产生式递归证明字符计数不变量，并刻画合法串的前缀性质。
  • 正则语言抽引引理：选择具有受控后缀表达式结构的字符串，证明任何允许的抽引都会破坏语言条件。
  • 文法构造：为推导过程中尚未完成的表达式设置非终结符，生成全部非空合法前缀。

Kai​

(1)​

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

  • E⇒1E\Rightarrow 1 のとき、#(1)=1\#(1)=1 である。

  • E⇒E−E\Rightarrow E- のとき、−- は #1\#_1 と #+\#_+ のどちらにも影響しないため、値は変わらない。

  • E⇒EE+E\Rightarrow EE+ のとき、二つの部分式を u,vu,v とすれば、帰納法の仮定から

    #(uv+)=#(u)+#(v)−1=1+1−1=1.\#(uv+)=\#(u)+\#(v)-1=1+1-1=1.

したがって、GG が生成するすべての文字列 ww について #(w)=1\#(w)=1 である。

(2)​

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

s=1p+p−1s=1^p+^{p-1}

は、pp 個の式 11 を ++ で順に結合した後置記法の式なので s∈L(G)s\in L(G) である。

反復補題によって s=xyzs=xyz、∣xy∣≤p|xy|\le p、∣y∣>0|y|>0 と分解できる。このとき最初の pp 文字はすべて 11 なので、ある r≥1r\ge 1 に対して y=1ry=1^r である。yy を 0 回反復すると

#(xz)=(p−r)−(p−1)=1−r≠1.\#(xz)=(p-r)-(p-1)=1-r\ne 1.

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

(3)​

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

S→E∣ES,E→1∣EE+∣E−.\begin{aligned} S&\to E\mid ES,\\ E&\to 1\mid EE+\mid E-. \end{aligned}

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

後置記法を左から読んだとき、正しい式の空でない接頭辞を読み終えたスタックには、未結合の完全な式が d≥1d\ge 1 個残っている。したがって、その接頭辞は E1E2⋯EdE_1E_2\cdots E_d と表せる。逆に、このような文字列の末尾に +d−1+^{d-1} を付ければ一つの式に結合できるので、生成された文字列は必ず L(G)L(G) のある文字列の接頭辞である。

(4)​

w′w∈L(G)w'w\in L(G) と仮定する。w′w' は正しい後置式の空でない接頭辞なので、(3) の議論から

#(w′)≥1\#(w')\ge 1

である。一方、w∈L(G)w\in L(G) なので (1) より #(w)=1\#(w)=1 である。したがって

#(w′w)=#(w′)+#(w)≥2,\#(w'w)=\#(w')+\#(w)\ge 2,

となり、(1) の必要条件 #(w′w)=1\#(w'w)=1 に矛盾する。よって w′w∉L(G)w'w\notin L(G) である。

本页目录