電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2022年8月実施 選択問題 離散数学とオートマトン

标签：

• 电气通信大学
• 确定性有限自动机
• 泵引理
• 计数

Author

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

Description

$\Sigma=\{0,1\}$ 上で $w=xx$ と書ける文字列を square と呼び、長さが $n$ 以下の square 全体を $Sq^{\leq n}$ とする。$Sq^{\leq7}$ の列挙と一般の要素数を求め、$Sq^{\leq4}$ を受理する DFA を構成せよ。また、長さ制限のない square 言語が正規言語でないことを背理法で示せ。

题目描述

在二元字母表上把形如 $xx$ 的串称为 square。枚举长度不超过 7 的 square，求一般计数，构造识别长度不超过 4 的 DFA，并用状态重复（泵引理思想）证明无限制 square 语言非正则。

Kai

1.

$$\boxed{ \begin{aligned} Sq^{\leq7}=\{&\lambda,00,11,0000,0101,1010,1111,\\ &000000,001001,010010,011011,\\ &100100,101101,110110,111111\}. \end{aligned}}$$

2.

$xx$ の長さが $n$ 以下であるためには $|x|\leq\lfloor n/2\rfloor$ である。写像 $x\mapsto xx$ は単射なので、

$$\boxed{ |Sq^{\leq n}| =\sum_{j=0}^{\lfloor n/2\rfloor}2^j =2^{\lfloor n/2\rfloor+1}-1}.$$

3.

次の DFA で受理できる。二重円が受理状態、$D$ が死状態である。

ここで $r_0,r_1$ は次にそれぞれ $0,1$ を読めば square が完成する状態である。受理される文字列は

$$\{\lambda,00,11,0000,0101,1010,1111\}=Sq^{\leq4}$$

に限られる。

4.

square 全体を受理する DFA $B$ が存在すると仮定し、その状態数を $N$ とする。$k>N$ を取り、$0^k10^k1$ を入力する。

(1)

最初の $1$ を読む前の状態

$$\delta(s_0,0^i)\qquad(0\leq i\leq k)$$

は $k+1>N$ 個ある。鳩の巣原理より、ある $0\leq i<j\leq k$ について

$$\delta(s_0,0^i)=\delta(s_0,0^j)$$

となる。したがって最初の $1$ より前に同じ状態へ少なくとも 2 回到達する。

(2)

$d=j-i>0$ とする。区間 $0^d$ は状態を変えないループなので、$B$ が

$$w=0^k10^k1=(0^k1)^2$$

を受理するならば、このループを 1 回増やした

$$w'=0^{k+d}10^k1$$

も受理する。

$d$ が奇数なら $|w'|$ は奇数なので square ではない。$d$ が偶数の場合、$w'$ が square なら、末尾の第 2 の $1$ に対応する第 1 の $1$ は文字列の中央になければならない。しかし実際の第 1 の $1$ の位置は $k+d+1$、中央は

$$\frac{|w'|}{2}=k+\frac d2+1$$

であり、一致すれば $d=0$ となって矛盾する。よって $w'$ は square ではないのに $B$ に受理される。したがって、

$$\boxed{\text{square 全体を受理する有限オートマトンは存在しない}}.$$