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

标签：

• Tokyo-University
• Nondeterministic-Finite-Automaton
• Deterministic-Finite-Automaton
• Regular-Language-Closure-Properties

Author

kainoj

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_2}$ for some $k \geq 0$ and $1 \leq i_i < \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) Suppost 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) Supposet 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

(2)

Write

$$L_2 = \{w \in \Sigma^* | v \preceq w \text{ for some } v \in L \}$$

where $v \preceq w$ indicates that $v$ is subsequence of $w$. In other words, to in order to get a word from $L_2$, we first fix a word $v \in L$ and then intertwine its letters with some "garbage" from $\Sigma^*$.

Let's fix $v\in L$. Let $p_1, p_2, \cdots p_{|v|}$ be sequence of states that $\mathcal{A}$ visits when reading $v$. Label transitions between $p_i$'s with next letters of $v$. Moreover, for each $p_i$, add a loop to itself labeled with $\Sigma$. Make $p_1$ the start state.

(3)

First,

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

is kinda quirky. We already supposed that $L \subseteq \Sigma^*$, so why do we need $v\in \Sigma^*$ above?

Let's start with constructing a NFA $\mathcal{N}$ which accepts $L'$. Let $\mathcal{N}$ be a copy of $\mathcal{A}$, where we additionally put $\Sigma$-labeled loops on every state. Intuitively, while traversing $\mathcal{A}$, in every state, we can have a "detour", i.e. accept some garbage.

Having constructed NFA $\mathcal{N}$, move to constructing equivalent DFA $\mathcal{D}$. It is feasible, and subset construction tells us how to it. Formally, define automaton $\mathcal{A}$ accepting $L$ as $\mathcal{A} = (Q, \Sigma, \delta, q_o, F)$. NFA $\mathcal{N}$ such that $\mathcal{L}(\mathcal{N}) = L'$ is defined as:

$$\begin{aligned} \mathcal{N} &= (Q, \Sigma, \delta_N, q_0, F) \end{aligned}$$

where

$$\delta_N(q, a) = \{q\} \cup \{\delta(q,a)\}$$

is a "loop" on every state. Now, equivalent DFA $\mathcal{D}$ is obtained by subset construction:

$$\begin{aligned} \mathcal{D} &= (Q_D, \Sigma, \delta_D, {q_0}, F_D) \\ Q_D &= \mathcal{P}(Q) \\ F_D &= \{ X\in Q_D | X\cap F \neq \emptyset\} \\ \delta_D(X,a) &= \bigcup_{q \in X} \delta_N(q,a) \end{aligned}$$

(4)

Since every DFA has equivalent NFA and vice versa, I'll prove (Q3) for NFA $\mathcal{N}$.

Two steps:

• $w \in L' \Rightarrow \mathcal{N} \text{ accepts } w$.Since $w\in L'$, then there must exits $v\in L$ such that $v\preceq w$.$v$ is accepted both in $\mathcal{A}$ and $\mathcal{N}$, since $\mathcal{N}$ has exactly the same states as $\mathcal{A}$.Then, $w$ must be accepted by $\mathcal{N}$ by following the loops on letters of $w$ which do not contribute to $v$.
• $\mathcal{N} \text{ accepts } w \Rightarrow w \in L'$. To get $v$ such that $v\preceq w$, simulate $\mathcal{N}$ on $w$, skip the loops. Obviously $v\in L$, because states of $\mathcal{N}$ and $\mathcal{A}$ are the same and $v$ and $w$ will end up in the same final state of $\mathcal{N}$.