跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

整数定数 11、二項演算 ++、単項演算 −- からなる算術式の後置記法を定める、次の文脈自由文法 GG を考える。ただし、開始記号は EE である。

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

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

  1. アルファベット {1,+,−}\{1,+,-\} 上の文字列 ww に含まれる 11 の個数を #1(w)\#_1(w)、++ の個数を #+(w)\#_+(w) とし、#(w)=#1(w)−#+(w)\#(w)=\#_1(w)-\#_+(w) と定める。例えば、#1(111++)=3\#_1(111++)=3、#+(111++)=2\#_+(111++)=2、#(111++)=1\#(111++)=1 である。GG が生成する任意の文字列 ww について #(w)=1\#(w)=1 となることを示せ。
  2. GG が生成する言語が正規言語でないことを、正規言語の反復補題を用いて示せ。
  3. 言語 L(G′)={w′∣w′≠ε ∧ ∃w (w′w∈L(G))}L(G')=\{w'\mid w'\ne\varepsilon\ \land\ \exists w\,(w'w\in L(G))\} を生成する文脈自由文法 G′G' を示せ。ここで ε\varepsilon は空列である。
  4. GG が生成する任意の文字列 ww と、空でない文字列 w′w' に対して、w′ww'w は GG が生成する文字列ではないことを示せ。

注：ポンピング補題

言語 LL が正規言語であるとき、次のような数 pp（ポンピング長）が存在する。ss が ∣s∣≥p|s|\geq p を満たす LL の任意の文字列であるとき、ss は次の条件を満たすように三つの部分 s=xyzs=xyz に分割できる。

  1. 各々の i≥0i\geq0 に対して xyiz∈Lxy^iz\in L。
  2. ∣y∣>0|y|>0。
  3. ∣xy∣≤p|xy|\leq p。

ただし、∣s∣|s| は文字列 ss の長さを表し、yiy^i は yy を ii 個連結したものを表す。y0y^0 は空列となる。

题目描述​

考虑用整数常量 11、二元运算 ++ 和一元运算 −- 表示后缀算术表达式的上下文无关文法 GG，其开始符号为 EE：

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

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

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

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

    例如，#1(111++)=3\#_1(111++)=3、#+(111++)=2\#_+(111++)=2、#(111++)=1\#(111++)=1。证明 GG 生成的每个字符串 ww 都满足 #(w)=1\#(w)=1。

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

  3. 给出一个上下文无关文法 G′G'，其语言为 L(G′)={w′∣w′≠ε ∧ ∃w (w′w∈L(G))}L(G')=\{w'\mid w'\ne\varepsilon\ \land\ \exists w\,(w'w\in L(G))\}，即所有能扩展成 GG 所生成字符串的非空前缀组成的语言。这里 ε\varepsilon 表示空串。

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

注：抽引引理

若语言 LL 是正则语言，则存在一个数 pp（抽引长度），使任意满足 s∈Ls\in L 且 ∣s∣≥p|s|\geq p 的字符串都可以分解为 s=xyzs=xyz，并满足：

  1. 对每个 i≥0i\geq0，均有 xyiz∈Lxy^iz\in L。
  2. ∣y∣>0|y|>0。
  3. ∣xy∣≤p|xy|\leq p。

这里 ∣s∣|s| 表示字符串 ss 的长度，yiy^i 表示将 yy 连续拼接 ii 次，y0y^0 为空串。

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) である。

本页目录