東京大学 情報理工学系研究科 コンピュータ科学専攻 2017年2月実施 問題2

标签：

• Tokyo-University
• Pumping-Lemma
• Nondeterministic-Finite-Automaton

Author

kainoj, 祭音Myyura

Description

For a non-deterministic finite automaton $M$ over an alphabet $\Sigma$, we write $\mathcal{L}(M) \subseteq \Sigma^*$ for the set of words accepted by $M$. We write $|w|$ for the length of the word $w$, and write $\mathbb{N}$ for the set of non-negative integers.

Answer the following questions:

(1) Consider the non-deterministic finite automaton $M_0$ depicted below, where $q_0$ is the start state, and $q_3$ is the only final state. Give $x, y, z \in \{a, b, c\}^*$ that satisfy all of the following conditions:

• (i) $xyz = abcc$
• (ii) $|y| > 0$
• (iii) $x y^n z \in \mathcal{L}(M)$ for every $n \in \mathbb{N}$.

(2) Prove that, for every non-deterministic finite automaton $M$ consisting of $k$ states and for every $w \in \mathcal{L}(M)$ such that $|w| \ge k$, there exist $x, y,$ and $z$ that satisfy all of the following conditions:

• (i) $xyz = w$
• (ii) $|y| > 0$
• (iii) $|xy| \le k$
• (iv) $x y^n z \in \mathcal{L}(M)$ for every $n \in \mathbb{N}$.

(3) Prove that there exists no non-deterministic finite automaton $M$ such that $\mathcal{L}(M) = \{ a^m b^n \mid m, n \in \mathbb{N}, 0 < m < n \}$. You may use the fact proved in question (2).

题目描述

对字母表 $\Sigma$ 上的 NFA $M$，用 $\mathcal{L}(M)\subseteq\Sigma^*$ 表示其接受的字符串集合，用 $|w|$ 表示字符串 $w$ 的长度，并以 $\mathbb{N}$ 表示非负整数集合。回答下列问题。

（1）考虑题图所示的 NFA $M_0$，其中 $q_0$ 为初始状态，$q_3$ 为唯一接受状态。给出 $x,y,z\in\{a,b,c\}^*$，使其同时满足：

• $xyz=abcc$；
• $|y|>0$；
• 对每个 $n\in\mathbb{N}$，都有 $xy^nz\in\mathcal{L}(M)$。

（2）证明：对任意含 $k$ 个状态的 NFA $M$，以及任意满足 $w\in\mathcal{L}(M)$ 且 $|w|\ge k$ 的字符串 $w$，都存在 $x,y,z$ 满足：

• $xyz=w$；
• $|y|>0$；
• $|xy|\le k$；
• 对每个 $n\in\mathbb{N}$，都有 $xy^nz\in\mathcal{L}(M)$。

（3）证明不存在 NFA $M$ 使

$$\mathcal{L}(M) =\{a^mb^n\mid m,n\in\mathbb{N},\ 0<m<n\}.$$

可以使用第（2）问证明的事实。

Kai

(1)

$x = a$, $y = bc$ and $z = c$

(2)

Fix an accepting run of $M$ on $w=a_1\cdots a_m$, where $m\geq k$. Among the states after reading $0,1,\ldots,k$ symbols, two are equal; write them as $p_i=p_j$ with $0\leq i<j\leq k$. Set

$$x=a_1\cdots a_i,\quad y=a_{i+1}\cdots a_j,\quad z=a_{j+1}\cdots a_m.$$

Then $|y|>0$, $|xy|=j\leq k$, and the run segment from $p_i$ back to $p_j=p_i$ may be repeated any number of times. Hence $xy^nz\in\mathcal L(M)$ for every $n\in\mathbb N$.

(3)

$L(M) = \{ a^m b^n | n,m \in \mathbb{N}, 0<m<n \}$ Assume that $L$ is regular language. Then pumping lemma must hold. Consider $w = a^k b^{k+1} \in L$, where $k$ is the pumping lemma constant. Because $|w| = 2k + 1 > k$, then there must exist a partitioning $xyz = w$ such that $|xy| < k$, $|y|>0$ and $xy^nz \in L$ for all $n\in\mathbb{N}$. Since $|xy|\leq k$, we have $y=a^r$ for some $r\geq1$. Then $xy^3z$ has $k+2r\geq k+2$ occurrences of $a$ but only $k+1$ occurrences of $b$, so it is not in $L$. Contradiction with statement that $x y^n z \in L$ for all $n\in N$. $L(M)$ is not regular, thus there exist no automaton recognizing it.