形式语言与自动机2023春季期末试题回忆版
捏 今天刚考完，趁着记忆清晰，先放上来
题只能说大概一致，仅供参考
- Design a DFA on $\Sigma=\{a,b,c\}$, which accepts the string that there is at least one $b$ between any two $a$s
- Design an NFA equivalent to $a^*b^*c^+$ with 3 states
- Design regular expressions on $\Sigma =\{a,b\}$
- strings that substring $aa$ occurs at most two times
- strings starts with $bb$ and the length of string is divisible by 4
- Prove that $\{w| w\ \mathrm{which}\ 0\ \mathrm{occurs\ more\ than} 1 $}$ is not regular with pumping lemma
- 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$
- $L=\{a^nb^n | n\geq 0\}$, design a context free grammer for $\overline{L}$, $\overline{L}$ means the complement of $L$ to $\Sigma^*$
- Design a DPDA for $\{a^ib^j |i\geq 1,\ j\geq i+3\}$
- Give a grammer $G_0$:$$ S \rightarrow aAA|aBB$$ $$A\rightarrow aaA|\epsilon$$$$B\rightarrow bBB|bbC$$$$C\rightarrow B$$
- Eliminate ε-productions.
- Eliminate any unit productions in resulting grammar.
- Put the resulting grammar into Chomsky Normal Form.
- G: $$S\rightarrow AB|aaB$$$$A\rightarrow aA|a$$$$B\rightarrow b$$
- Show that this grammar is ambiguous
- Find a grammar for the same language that is unambiguous
- Design a Turing Machine that turn $0^m$ to $0^{m \mod 5}$ such as $f(0^7) = 00$ and $f(0^5) = \epsilon$
如果你在期末考试前读到了这个文章，那祝你考试顺利
