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

标签：

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

Author

kainoj, 祭音Myyura

Description

For each $n \geq 1$, let $\Sigma_n$ be $\{a_1, \dots, a_n\}$, where $a_1, \dots, a_n$ are different from each other. For a word $w \in \Sigma_n^*$, we write $|w|_{a_i}$ for the number of occurrences of $a_i$ in $w$. We define the languages $L_{\forall, n}$ and $L_{\exists, n}$ over $\Sigma_n$ by:

$$L_{\forall, n} = \{w \in \Sigma_n^* \mid |w|_{a_i} \text{ is even for every } i \in \{1, \dots, n\}\},$$

and

$$L_{\exists, n} = \{w \in \Sigma_n^* \mid |w|_{a_i} \text{ is even for some } i \in \{1, \dots, n\}\}.$$

Answer the following questions.

(1) Give a deterministic finite state automaton with $4$ states that accepts $L_{\forall, 2}$.

(2) Give a non-deterministic finite state automaton with $7$ states (without $\epsilon$-transitions) that accepts $L_{\exists, 3}$.

(3) Prove that, for every $n \geq 1$, every deterministic finite state automaton that accepts $L_{\exists, n}$ has at least $2^n$ states.

(4) Prove that, for every $n \geq 1$, every non-deterministic finite state automaton (without $\epsilon$-transitions) that accepts $L_{\forall, n}$ has at least $2^n$ states.

题目描述

对每个 $n\ge1$，令 $\Sigma_n=\{a_1,\ldots,a_n\}$，其中各字符互不相同。对 $w\in\Sigma_n^*$，以 $|w|_{a_i}$ 表示字符 $a_i$ 在 $w$ 中出现的次数。定义

$$L_{\forall,n} =\{w\in\Sigma_n^*\mid \text{对每个 }i\in\{1,\ldots,n\},\ |w|_{a_i}\text{ 均为偶数}\},$$

以及

$$L_{\exists,n} =\{w\in\Sigma_n^*\mid \text{存在 }i\in\{1,\ldots,n\}\text{ 使 }|w|_{a_i}\text{ 为偶数}\}.$$

回答下列问题。

（1）给出一个具有 $4$ 个状态、识别 $L_{\forall,2}$ 的 DFA。

（2）给出一个具有 $7$ 个状态、不含 $\varepsilon$ 转移、识别 $L_{\exists,3}$ 的 NFA。

（3）证明对每个 $n\ge1$，任何识别 $L_{\exists,n}$ 的 DFA 都至少有 $2^n$ 个状态。

（4）证明对每个 $n\ge1$，任何不含 $\varepsilon$ 转移且识别 $L_{\forall,n}$ 的 NFA 都至少有 $2^n$ 个状态。

Kai

(1)

This one was also solved in Automata Theory, Languages and computation 3rd ed, 2.2.4, Example 2.4

Explanation:

• A: "number of $a$'s is even, number of $b$'s is even"
• B: "number of $a$'s is odd, number of $b$'s is even"
• C: "number of $a$'s is even, number of $b$'s is odd"
• D: "number of $a$'s is odd, number of $b$'s is odd"

(2)

Begin with an $\epsilon$-NFA as depiced in Fig. (2-a). It "guesses" which letter appears even number of times. To make it $\epsilon$-free, we either follow him: https://youtu.be/sq-dLKAd6bo?t=1714 or consider the followig: starting from start state, how far, i.e. which states can we reach on letter $a$? There are $3$ such states. We simply draw an edge to those states. Do the same for $b,c$. The final answer is on Fig. (2-b)

Fig. (2-a)

Fig. (2-b)

(3)

Prove that, for every $n\geq 1$, every deterministic finite state automaton that accepts $L_{\exists ,n}$ has at least $2^n$ states.

For each parity vector $u\in\{0,1\}^n$, choose a word $x_u$ whose parity vector is $u$. If $u\ne v$, append a word $z$ with parity vector $\boldsymbol1-u$. Then $x_uz$ has all counts odd and is rejected, whereas $x_vz$ still has at least one even count and is accepted. Thus the $2^n$ words $x_u$ are pairwise distinguishable, so every DFA needs at least $2^n$ states.

(4)

For each $S\subseteq\{1,\ldots,n\}$, let $x_S=y_S$ be the word containing one copy of $a_i$ for every $i\in S$. Then $x_Sy_S\in L_{\forall,n}$. For $S\ne T$, however, $x_Sy_T\notin L_{\forall,n}$ because every letter indexed by $S\triangle T$ occurs once.

Fix an accepting path for each $x_Sy_S$, and let $q_S$ be its state just after $x_S$. If $q_S=q_T$ for distinct $S,T$, the prefix of the path for $x_Sy_S$ and the suffix of the path for $x_Ty_T$ form an accepting path for $x_Sy_T$, a contradiction. Hence all $2^n$ states $q_S$ are distinct.