捏 今天刚考完，趁着记忆清晰，先放上来
题只能说大概一致，仅供参考

  1. Design a DFA on $\Sigma=\{a,b,c\}$, which accepts the string that there is at least one $b$ between any two $a$s
  2. Design an NFA equivalent to $a^*b^*c^+$ with 3 states
  3. Design regular expressions on $\Sigma =\{a,b\}$
    1. strings that substring $aa$ occurs at most two times
    2. strings starts with $bb$ and the length of string is divisible by 4
  4. Prove that $\{w| w\ \mathrm{which}\ 0\ \mathrm{occurs\ more\ than} 1 $}$ is not regular with pumping lemma
  5. Prove $L_1 \cup L_2$ is not regular if $L_1$ is regular $L_2$ is not regular and $L_1 \cap L_2 = \varnothing$
  6. $L=\{a^nb^n | n\geq 0\}$, design a context free grammer for $\overline{L}$, $\overline{L}$ means the complement of $L$ to $\Sigma^*$
  7. Design a DPDA for $\{a^ib^j |i\geq 1,\ j\geq i+3\}$
  8. Give a grammer $G_0$:$$ S \rightarrow aAA|aBB$$ $$A\rightarrow aaA|\epsilon$$$$B\rightarrow bBB|bbC$$$$C\rightarrow B$$
    1. Eliminate ε-productions.
    2. Eliminate any unit productions in resulting grammar.
    3. Put the resulting grammar into Chomsky Normal Form.
  9. G: $$S\rightarrow AB|aaB$$$$A\rightarrow aA|a$$$$B\rightarrow b$$
    1. Show that this grammar is ambiguous
    2. Find a grammar for the same language that is unambiguous
  10. Design a Turing Machine that turn $0^m$ to $0^{m \mod 5}$ such as $f(0^7) = 00$ and $f(0^5) = \epsilon$

如果你在期末考试前读到了这个文章，那祝你考试顺利