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

标签：

• Tokyo-University
• Epsilon-Nondeterministic-Finite-Automaton
• Regular-Expression
• Regular-Language-Closure-Properties

Author

kainoj

Description

Let us consider nondeterministic finite automata with $\varepsilon$-transitions ($\varepsilon$-NFAs) over the alphabet $\Sigma = \{a, b\}$. An $\varepsilon$-NFA is an NFA that can additionally have "silent" transitions labeled with a fresh symbol $\varepsilon$. A word $w \in \Sigma^*$ is accepted by an $\varepsilon$-NFA $M$ if there exists a word $w' \in (\Sigma \cup \{\varepsilon\})^*$ such that:

1. $w'$ is accepted by $M$ (when $M$ is considered an NFA over the alphabet $\Sigma \cup \{\varepsilon\}$); and
2. removing all the occurrences of $\varepsilon$ in $w'$ gives rise to $w$.

The language $L(M) \subseteq \Sigma^*$ of an $\varepsilon$-NFA $M$ is the set of words accepted by $M$.

An example of an $\varepsilon$-NFA is given below; it is referred to as $M_1$. Here $q_0$ is an initial state and $q_2$ is an accepting state.

Answer the following questions:

(1) Give a regular expression that designates the language $L(M_1)$ of the above $\varepsilon$-NFA $M_1$.

(2) Give an NFA $M_2$ over $\Sigma$ such that: $L(M_2) = L(M_1)$; and $M_2$ is $\varepsilon$-free, that is, there are no transitions labeled with \varepsilon in $M_2$.

(3) Give an $\varepsilon$-NFA $M_3$ such that

$$L(M_3) = \{ w \in \Sigma^* \mid w \text{ contains } aa \text{ as a subword, that is, } w = w_1 aa w_2 \text{ for some } w_1, w_2 \in \Sigma^* \}.$$

Your answer may be $\varepsilon$-free.

(4) Give an $\varepsilon$-NFA $M_4$ such that $L(M_4) = L(M_1) \cup L(M_3)$, where $M_3$ is from Question (3). Your answer may be $\varepsilon$-free.

(5) Give an $\varepsilon$-NFA $M_5$ such that $L(M_5) = L(M_1) \cap L(M_3)$, where $M_3$ is from Question (3). Your answer may be $\varepsilon$-free.

题目描述

在字母表 $\Sigma=\{a,b\}$ 上考虑带 $\varepsilon$ 转移的非确定性有限自动机（$\varepsilon$-NFA）。$\varepsilon$-NFA 除普通 NFA 的转移外，还允许标记为新符号 $\varepsilon$ 的“无声”转移。若存在 $w'\in(\Sigma\cup\{\varepsilon\})^*$，使得 $w'$ 被把 $M$ 视为字母表 $\Sigma\cup\{\varepsilon\}$ 上的 NFA 时接受，并且删除 $w'$ 中全部 $\varepsilon$ 后得到 $w$，则称 $w\in\Sigma^*$ 被 $M$ 接受。$L(M)$ 表示 $M$ 接受的所有字符串构成的语言。

题图给出了一个 $\varepsilon$-NFA $M_1$，其中 $q_0$ 是初始状态，$q_2$ 是接受状态。回答下列问题。

（1）给出描述 $L(M_1)$ 的正则表达式。

（2）给出字母表 $\Sigma$ 上不含任何 $\varepsilon$ 转移的 NFA $M_2$，使得 $L(M_2)=L(M_1)$。

（3）构造一个 $\varepsilon$-NFA $M_3$，使得

$$L(M_3)=\{w\in\Sigma^*\mid w\text{ 含有子串 }aa，即存在 w_1,w_2\in\Sigma^*\text{ 使 }w=w_1aaw_2\}.$$

答案也可以不含 $\varepsilon$ 转移。

（4）构造 $\varepsilon$-NFA $M_4$，使 $L(M_4)=L(M_1)\cup L(M_3)$。答案也可以不含 $\varepsilon$ 转移。

（5）构造 $\varepsilon$-NFA $M_5$，使 $L(M_5)=L(M_1)\cap L(M_3)$。答案也可以不含 $\varepsilon$ 转移。

Kai

(1)

$a^*b^*a^*$

(2)

(3)

(4)

(5)

$L(M_5)$ contains $aa$ and is of form of $aaa^*b^*a^* + a^*b^*aaa^*$.