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

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$

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

1. eg. every run of 0s has length at least 3有0时只能是000或更多连续0
2. eg. be interpreted as binary integer

感谢Doctor Z.制作的形式语言与自动机的英文单词对照，如果能帮到大家的话十分荣幸