题目来源：

不保证正确性！

### T1

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

### T2

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

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

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

### T5

Convert the following NFA into DFA with subset construction.

### T6

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

### 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}\}$.

### T9

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

### 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$.