東京大学 情報理工学系研究科 コンピュータ科学専攻 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)

Use seven states $q_0,E_a,O_a,E_b,O_b,E_c,O_c$. The initial state is $q_0$ and the accepting states are $q_0,E_a,E_b,E_c$. The complete transition table is:

State	$a$	$b$	$c$
$q_0$	$\{O_a,E_b,E_c\}$	$\{E_a,O_b,E_c\}$	$\{E_a,E_b,O_c\}$
$E_a$	$\{O_a\}$	$\{E_a\}$	$\{E_a\}$
$O_a$	$\{E_a\}$	$\{O_a\}$	$\{O_a\}$
$E_b$	$\{E_b\}$	$\{O_b\}$	$\{E_b\}$
$O_b$	$\{O_b\}$	$\{E_b\}$	$\{O_b\}$
$E_c$	$\{E_c\}$	$\{E_c\}$	$\{O_c\}$
$O_c$	$\{O_c\}$	$\{O_c\}$	$\{E_c\}$

After the first symbol, the automaton nondeterministically chooses which letter's parity to track. $E_l$ and $O_l$ record an even and odd number of occurrences of $l$, respectively. A word is accepted exactly when at least one tracked count is even. The initial state accepts the empty word, for which every count is zero. Every transition consumes one symbol, so no $\epsilon$-transition is used.

(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.