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

标签：

• 东京大学
• 非确定性有限自动机
• 确定性有限自动机
• 正则语言的封闭性质

Author

kainoj, 祭音Myyura

Description

Let $\Sigma$ be a finite alphabet (i.e., a finite set of letters). We say that a word $v \in \Sigma^*$ is a subsequence of a word $w = a_1 \cdots a_n \in \Sigma^*$ if $v = a_{i_1} \cdots a_{i_k}$ for some $k \geq 0$ and $1 \leq i_1 < \cdots < i_k \leq n$. For example, $aab$ is a subsequence of $acbabc$ (let $k=3, i_1=1, i_2=4$ and $i_3=5$). We write $v \preceq w$ if $v$ is a subsequence of $w$. Answer the following questions.

(1) Give a non-deterministic finite automaton with at most $4$ states that accepts the language:

$$\{w \in \{a,b,c\}^* \mid aab \preceq w\}$$

(2) Suppose that $L \subseteq \Sigma^*$ is the language accepted by a deterministic finite automaton $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ (where $Q$ is a finite set of states, $\delta \in Q \times \Sigma \rightarrow Q$ is the transition function, $q_0 \in Q$ is the initial state, and $F \subseteq Q$ is the set of final states). Give a non-deterministic finite automaton that accepts the language:

$$\{w \in \Sigma^* \mid v \preceq w \text{ for some } v \in L\}$$

(3) Suppose that $L \subseteq \Sigma^*$ is the language accepted by a deterministic finite automaton $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$. Assume that the transition function $\delta \in Q \times \Sigma \rightarrow Q$ is a total function. Give a deterministic finite automaton that accepts the language:

$$\{w \in \Sigma^* \mid v \in L \text{ for every } v \in \Sigma^* \text{ such that } v \preceq w\}$$

(4) Prove the correctness of your answer for question (3) above.

题目描述

设 $\Sigma$ 为有限字母表。若从字符串 $w=a_1\cdots a_n\in\Sigma^*$ 中按原顺序选取若干字符可以得到 $v$，即存在 $k\ge0$ 及 $1\le i_1<\cdots<i_k\le n$，使 $v=a_{i_1}\cdots a_{i_k}$，则称 $v$ 是 $w$ 的子序列，记作 $v\preceq w$。例如 $aab\preceq acbabc$。回答下列问题。

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

$$\{w\in\{a,b,c\}^*\mid aab\preceq w\}.$$

（2）设 DFA $\mathcal A=(Q,\Sigma,\delta,q_0,F)$ 识别语言 $L\subseteq\Sigma^*$。构造一个 NFA，识别语言

$$\{w\in\Sigma^*\mid \text{存在 }v\in L\text{ 使 }v\preceq w\}.$$

（3）设 DFA $\mathcal A=(Q,\Sigma,\delta,q_0,F)$ 识别 $L\subseteq\Sigma^*$，并假定 $\delta:Q\times\Sigma\to Q$ 为全函数。 构造一个 DFA，识别语言

$$\{w\in\Sigma^*\mid \text{对每个满足 }v\preceq w\text{ 的 }v\in\Sigma^*， \ v\in L\}.$$

（4）证明第（3）问构造的正确性。

Kai

(1)

--> o --a--> o --a--> o --b--> (o)
   / \      / \      / \       / \
   \ /      \ /      \ /       \ /
    E        E        E         E

Here each loop labeled E denotes one loop for every symbol in $\{a,b,c\}$.

(2)

Use the NFA $\mathcal N=(Q,\Sigma,\Delta,q_0,F)$, where

$$\Delta(q,a)=\{q,\delta(q,a)\}.$$

The transition to $q$ skips the current input symbol; the other transition selects it for the simulated subsequence. Hence $\mathcal N$ accepts $w$ iff some $v\preceq w$ is accepted by $\mathcal A$.

(3)

Define the DFA $\mathcal D$ by

$$\begin{aligned} Q_D&=\mathcal P(Q), & q_D&=\{q_0\},\\ \delta_D(X,a)&=X\cup\{\delta(q,a):q\in X\}, &F_D&=\{X\subseteq Q:X\subseteq F\}. \end{aligned}$$

(4)

For every $w$, induction on $|w|$ gives the invariant

$$\delta_D^*(\{q_0\},w) =\{\delta^*(q_0,v):v\preceq w\}.$$

Indeed, on reading the next symbol $a$, a subsequence either omits $a$ or appends it. Therefore the reached subset is accepting exactly when every state in it lies in $F$, which is equivalent to $v\in L$ for every $v\preceq w$.