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

标签：

• TITech
• Pumping-Lemma
• Context-Free-Grammar
• Deterministic-Finite-Automaton

Author

GPT-5

Description

Let

$$\Sigma=\left\{ \binom00,\binom01,\binom10,\binom11 \right\}.$$

(1) Let $A$ be the language of strings whose upper-row string is a palindrome; $\varepsilon\in A$. Show using the pumping lemma that $A$ is not regular.

(2) Give a context-free grammar generating $A$.

(3) Regard each row as a binary number whose leftmost position is the most significant bit, and let $B$ consist of strings whose lower row is three times the upper row; $\varepsilon\in B$. Let $B^R=\{w^R\mid w\in B\}$. Give a four-state deterministic finite automaton recognizing $B^R$.

题目描述

令字母表

$$\Sigma=\left\{ \binom00,\binom01,\binom10,\binom11 \right\}.$$

这里每个字符串可看成上下两行等长的二进制串。

1. 令 $A$ 为所有“上方一行是回文串”的字符串组成的语言，并约定空串 $\varepsilon\in A$。使用抽引引理证明 $A$ 不是正则语言。

2. 给出一个生成 $A$ 的上下文无关文法。

3. 把每一行都视为最高位在最左侧的二进制数，令 $B$ 为满足“下方一行表示的数是上方一行的三倍”的字符串集合，并约定 $\varepsilon\in B$。定义反转语言

   $$B^R=\{w^R\mid w\in B\}.$$

   给出一个恰有四个状态、能够识别 $B^R$ 的确定有限自动机。

考点

• 正则语言抽引引理：针对上行回文约束选取字符串并分析所有合法分解，从而推出抽引后的矛盾。
• 上下文无关文法：利用成对生成首尾符号的产生式刻画上行回文，同时允许下行符号自由取值。
• 确定有限自动机：从低位到高位读取反转后的两行二进制位，以乘以 $3$ 时的进位状态构造四状态转移。

Kai

以下では列記号 $\binom{x}{y}$ を単に $xy$ と書く。第 1 ビットが上段、第 2 ビットが下段である。

(1)

$A$ が正則で、ポンピング長が $p$ であると仮定する。文字列

$$w=(00)^p(10)(00)^p$$

を取る。これは上段が $0^p10^p$ なので $A$ に属する。任意の分解 $w=xyz$ で $|xy|\leq p$, $|y|>0$ を満たすものを考えると、$y=00^r$ $(r\geq1)$ である。

$i=0$ として $y$ を除くと、上段は $0^{p-r}10^p$ となり回文ではない。したがって $xy^0z\notin A$ であり、ポンピング補題に矛盾する。よって

$$\boxed{A\text{ は正則言語ではない}}.$$

(2)

非終端記号を $S,Z,O$、開始記号を $S$ とし、次の生成規則を取る。

$$\begin{aligned} S&\to\varepsilon\mid Z\mid O\mid ZSZ\mid OSO,\\ Z&\to00\mid01,\\ O&\to10\mid11. \end{aligned}$$

$Z$ は上段ビット 0、$O$ は上段ビット 1 の任意の列を生成する。$ZSZ$ と $OSO$ は同じ上段ビットを両端に付け、下段ビットは左右で独立に選べる。したがってこの文法は、上段が回文で下段が任意の文字列をちょうど生成する。

(3)

$B^R$ では最下位ビットから順に読むことになる。3 倍算の現在の桁への繰上がりを $c$、入力列を $xy$ とすると、遷移条件は

$$y\equiv3x+c\pmod2, \qquad c'=\left\lfloor\frac{3x+c}{2}\right\rfloor.$$

到達し得る繰上がりは $0,1,2$ であり、これらに不正入力用のデッド状態を加えれば 4 状態になる。$q_c$ を繰上がり $c$ の状態、$q_d$ をデッド状態とする。

初期状態かつ唯一の受理状態は $q_0$ である。入力を読み終えたとき繰上がりが 0 であることが、同じ桁数の下段が上段のちょうど 3 倍であることに対応する。$q_0$ を受理状態にすることで空文字列も受理される。