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

标签：

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

Author

kainoj

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)

Classic proof of Pumping Lemma (PL) for regular languages. Let $\mathcal{M}$ be an automaton with $k$ states. Let $w = a_1a_2\cdots a_k \in L(M)$ such that $|w| > k$. Now let's simulate run of $\mathcal{M}$ of word $w$. Define states $p_i = \hat\delta(q_0, w_1w_2\cdots w_i)$. That is, $p_i$ is a state in which $\mathcal{M}$ is after reading first $i$ inputs. From pigeonhole principle, at lest two of those state must be exactly the same state. Let $p_i = p_j$ be the state that is visited the second time for the first time (i.e. $i$ is the smallest among all such states).

I claim that: $w = xyz$, where

• $x = a_1a_2\cdots a_{i-1}$
• $y = a_ia_{i+1}\cdots a_{j-1}$
• $z = a_ja_{j+1}\cdots a_k$

Obviously, $|y| > 0$ because $i\neq j$ and $|xy| = j - 1 \leq n$. States $p_i, \dots, p_j$ create a loop in the automaton - it can be traversed any number of times, thus $xy^nz \in L(\mathcal{M})$. For $n=0$ we simply "skip" the loop, for $n\geq 1$ we traverse the loop $n$ times.

(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$ \textbf{for all} $n\in\mathbb{N}$. Notice that $xy$ consists of $a$'s only. Let's "pump up" $y$. For example, $xy^{42}z$ contains of significantly more $a$'s than $b$'s. This word does not belong to the language. 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.