形式语言2019期末题解

  题目来源:

哈尔滨工业大学2019年《形式语言与自动机》期末试题_GoodLuckWJP的博客-CSDN博客_哈工大 形式语言与自动机
哈尔滨工业大学2019年《形式语言与自动机》期末试题Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}.Design a NFA within four states for the language {a}*∪{ab}*.Design regular exp..._哈工大 形式语言与自动机

  不保证正确性!

T1

Design a DFA for the language $$L=\{w\in\{0,1\}^* \mid w \text{ contains both 01 and 10 as substrings} \} $$

解:如果字符串以 0 开头,那么它属于 $L$ 当且仅当出现一个 1、在 1 后面存在 0,也就是说,这个字符串形如 $0^+ 1 ^ + 0 (0+1) ^ *$. 若字符串以 1 开头,那么它属于 $L$ 当且仅当出现一个 0、在 0 后面存在 1,即 $1 ^ + 0 ^ + 1 (0+1) ^ *$. 设计 DFA 只需要分类讨论这两种情况,如下:

T2

Design a NFA within four states for the language $\{a\} ^ * \cup \{ ab \} ^ *$.

解:题目要求采用不超过 4 个状态设计 NFA 识别这个语言。也是分类讨论即可,需要注意不能从 $ab$ 的接受点往起点连线,否则会让 $ababaaaaa$ 这种串被接受。

T3

Design regular expressions for language over $\Sigma = \{0, 1\}$

  1. All strings contain the substring 001.
  2. All strings expect the string 001.

解:

  1. $(0+1) ^ * (001) (0+1) ^ *$
  2. 需要排除掉上述这种情况。我们枚举长度为1、2、3的串来排除掉 001,接受长度大于 3 的所有串。结果如下:$$\begin{aligned}\epsilon & + (0+1) + (0+1)(0+1)  \\ & + (0+1)(0+1)0 + 011+101+111 \\ & +(0+1)(0+1)(0+1)(0+1)(0+1) ^ *\end{aligned}$$

T4

Prove that $L = \{0 ^ m 1 ^ n \mid m/n\text{ is an integer}\}$ is not regular with pumping lemma.

证:假设 $L$ 是正则语言。那么我们取 $w = 0 ^ {2N} 1 ^ {2N} \in L$.

$w$ 可以被划分为 $xyz$ 且 $|y|>0, ~|xy| \leq N$.

那么一定有 $x=0 ^ a, ~ y=0^b$,其中 $a+b \leq N, b>0$.

于是 $x y ^0 z = 0 ^a 0 ^ {2N - a - b} 1 ^ {2N} \in L$,然而显然 $0< (2N-b)/(2N) < 1$ 不是整数,推翻假设。

T5

Convert the following NFA into DFA with subset construction.

解:子集构造法即可。$$\begin{array}{r|ll}
& 0 & 1 \\
\hline
\to p & \{p\} & \{p, q,r\} \\
q & \{r\} & \{r\} \\
r & \{s\} & \{s\} \\
s & \varnothing & \varnothing  \\
\hline
\to\{p\} & \{p\} & \{p,q,r\} \\
\{p,q,r\} & \{p,r,s\} & \{p,q,r,s\} \\
*\{p,r,s\} & \{p,s\} & \{p,q,r,s\} \\
*\{p,s\} & \{p\} & \{p,q,r\} \\
*\{p,q,r,s\} & \{p,r,s\} & \{p,q,r,s\} \\
\end{array}$$

T6

Give a context-free grammar for $L=\{a ^ i b ^ j c ^ {i+j}\mid i,j \geq 0\}$.

解:注意到接受的字符串可以写成 $a^i (b ^ j c ^ j) c ^ i$ 的形式。构造出括号里面那个东西,再套壳即可。$$\begin{aligned}S &\to  aSc \mid E \\
E &\to bEc \mid \varepsilon \end{aligned}$$

T7

Let L be the language generated by the grammar $G$ below

$$\begin{aligned}S & \to AB\mid BBB \\
A&\to Bb\mid \varepsilon \\
B&\to aB\mid A\end{aligned}$$

  1. 消除空产生式
  2. 消除单元产生式
  3. 转换到CNF

解:

  1. 注意到  $A,B,S$ 均可空。于是构造 $G ^ \prime$:$$\begin{aligned}S & \to A \mid AB \mid B \mid BB \mid BBB \\
    A&\to b \mid Bb\\
    B&\to a \mid aB\mid A\end{aligned}$$
  2. 上面的单元对有 $[B,A],[S,A],[S,B]$. 先抹掉所有单元产生式:$$\begin{aligned}S & \to AB \mid BB \mid BBB \\
    A&\to b \mid Bb\\
    B&\to a \mid aB\end{aligned}$$ 再复制子产生式到父亲,得到结果 $$\begin{aligned}S & \to AB \mid BB \mid BBB \mid  b \mid Bb \mid a \mid aB \\
    A&\to b \mid Bb\\
    B&\to a \mid aB \mid b \mid Bb\end{aligned}$$
  3. 要命。。。$$\begin{aligned}S&\to AB \mid BB \mid BD _ 1 \mid b \mid B C_b \mid a \mid C_a B \\
    D _ 1 &\to BB \\ C_a &\to a \\ C_b &\to b  \\ A &\to b \mid BC_b  \\ B &\to a \mid C_a B \mid b \mid BC_b\end{aligned}$$

T8

Design a PDA for $L=\{w\in \{a,b\} ^ * \mid w\text{ has more a's than b's}\}$.

解:往栈里面填字符。如果栈顶字符与自己互异,则弹掉栈顶;否则把自己压入栈顶。不难注意到栈里面的元素一定是同一种。当且仅当栈顶为 a 的时候,字符串可接受。

T9

Prove : for every context free language $L$, the language $$L^ \prime = \{ 0 ^ {|w|} \mid w \in L \}$$ is also context free.

证:考虑同态映射 $h(a)=0$. 则 $h(w) = 0 ^ {|w|}$.

注意到 $L$ 是上下文无关的,故 $h(L) = \{ 0 ^ {|w|} \mid w \in L \} = L ^ \prime$ 也是上下文无关的。

T10

Design a Turing Machine that computes the following function $f: 0 ^ n\mapsto \text{binary}(n)$
Where integer $n\geq 1$ and $\text{binary}(n)$ is the binary representation of n.
For example: $f(0^3) = 11, f(0 ^5) = 101$.

解:有点难的题。基本思路是维护一个二进制累加器,去数 $0$ 的个数。每次数 0,都删去最右边那个 0 ,然后跑去把二进制累加器增加一次。我把累加器放在了输入进来的纸带的左边,因为二进制累加器是向左扩展的。累加器与输入串之间用一个 B 做间隔。

最后设计出来的图灵机如下。懒得用 Latex 画了,偷懒手绘一下:

在图灵机停机之后,纸带上剩下的就是想要的二进制串。