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

标签：

• Tokyo-University
• Nondeterministic-Finite-Automaton
• Nondeterministic-Finite-Automaton-to-Deterministic-Finite-Automaton-Conversion
• Automata-State-Complexity

Author

kainoj, 祭音Myyura

Description

Let us consider nondeterministic finite automata (NFA) and deterministic finite automata (DFA) over the alphabet $\Sigma = \{a, b\}$. For example, the NFA $M_1$ shown below

recognizes the language

$$L_1 = \{ w \in \Sigma^* \mid \text{the last letter of } w \text{ is } a \}$$

Here $\Sigma^*$ denotes the set of words over $\Sigma$.

Answer the following questions.

(1) Present an NFA, with at most four states, that recognizes the language

$$L_3 = \{ w \in \Sigma^* \mid |w| \geq 3 \text{ and the third last letter of } w \text{ is } a \}$$

Here $|w|$ denotes the length of the word $w$.

(2) Present a DFA that recognizes the language $L_3$ in Question (1).

(3) A DFA that recognizes the language $L_3$ has no less than $2^3 = 8$ states. Prove this fact.

(4) Argue for the following statement:

• To recognize the same language, a DFA possibly needs the number of states that is exponentially bigger than an NFA does.

题目描述

在字母表 $\Sigma=\{a,b\}$ 上考虑非确定性有限自动机（NFA）和确定性有限自动机（DFA）。题图中的 NFA $M_1$ 识别语言

$$L_1=\{w\in\Sigma^*\mid w\text{ 的最后一个字符是 }a\},$$

其中 $\Sigma^*$ 表示 $\Sigma$ 上所有字符串的集合。回答下列问题。

（1）构造一个状态数不超过 $4$ 的 NFA，使其识别语言

$$L_3=\{w\in\Sigma^*\mid |w|\ge 3\text{，且 }w\text{ 的倒数第三个字符是 }a\},$$

其中 $|w|$ 表示字符串 $w$ 的长度。

（2）构造一个识别第（1）问中语言 $L_3$ 的 DFA。

（3）证明：任何识别 $L_3$ 的 DFA 都至少需要 $2^3=8$ 个状态。

（4）论证：为了识别同一种语言，DFA 所需的状态数有可能比 NFA 所需的状态数呈指数级增长。

Kai

(1)

(2)

(3) + (4)

Define

$$L_n = \{ w\in \Sigma^* \mid |w| \geq n \text{ and the $n$-th last letter of $w$ is $a$}\}.$$

Intuitively, a DFA needs to remember every possible length-$n$ suffix, of which there are $2^n$.

Suppose, for contradiction, that a DFA $D$ recognizing $L_n$ has fewer than $2^n$ states. By the pigeonhole principle, two distinct words $x=x_1\cdots x_n$ and $y=y_1\cdots y_n$ reach the same state. Choose a position $i$ with $x_i\ne y_i$; by symmetry assume $x_i=a$ and $y_i=b$.

Append $b^{i-1}$ to both words. Their $n$-th last letters are then $x_i=a$ and $y_i=b$, so $xb^{i-1}\in L_n$ while $yb^{i-1}\notin L_n$. But the two words started the suffix in the same DFA state, so the DFA must give them the same result, a contradiction.

Thus all $2^n$ length-$n$ words are pairwise distinguishable, and every DFA for $L_n$ has at least $2^n$ states.

• (3): Let $n = 3$. Then DFA recognizing $L_3$ has no less than $8$ states.
• (4): An NFA for $L_n$ uses $n+1$ states: it loops in the initial state and guesses the relevant $a$, then counts the remaining $n-1$ symbols. The lower bound above shows that an equivalent DFA needs at least $2^n$ states.