哈工大本部2022形式语言与自动机期末试题

学长正常情况下只能每科考一回试，希望学弟学妹们日后可以薪火相传。
注：试卷本人只能记住大概意思，记不住具体是怎么描述的，故仅供参考。

2022年05月08日星期天下午13:00~15:00，本人经历了形式语言与自动机考试，现将回忆版试题呈现如下，供大家参考。

先聊聊考试感受：题比2019，2020的要难一些，难的来源在于考了一些“以为”可能不会或是可能很少考察的点，上课时还是要认真听老师讲，老师会很明确的说哪里常考哪里会考哪里不考（凡是没明确说不考的，可能都会考，但也不要担心，其实内容不多的）以及不同的题目要遵循怎样的答题规范。

PDF版本将于近期上传至Github：HITSZ-OpenCS项目中，敬请关注~

2022.05.19 Update：成绩出来了，有问题可以问老师，老师会把你扣分的点说的明明白白，让你心服口服。本人考试时写的什么，现在也很难一模一样地复现了，答案就不提供了：），个人认为一些较坑的点，会放在文末。

1.请为以下语言设计DFA： $L={w∈{0,1}∗∣w既包含00，又包含11}L=\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{既包含}00\text{，又包含}11 \right\}$

2.请为以下语言设计NFA： $L={w∈{0,1}∗∣w中子串01、10出现的次数相等}L=\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{中子串}01\text{、}10\text{出现的次数相等} \right\}$

3.请为以下语言设计正则表达式：
(1) $L={w∈{a,b}∗∣w中子串aa至少出现两次}L=\left\{ w\in \left\{ a,b \right\} ^*|w\text{中子串}aa\text{至少出现两次} \right\}$ （之前手抖将此处题目打错，感谢同学帮助指出错误！）

(2) $L={w∈{a,b}∗∣w不以aa或bb结尾}L=\left\{ w\in \left\{ a,b \right\} ^*|w\text{不以}aa\text{或}bb\text{结尾} \right\}$

4.请用泵引理证明L不是正则： $L={w∈{0,1}∗∣w中子串00和11出现的次数相等}L=\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{中子串}00\text{和}11\text{出现的次数相等} \right\}$

5.请从任一正则语言 $L⊆Σ∗L\subseteq \Sigma ^*$ 的DFA出发，用正式的符号语言构造h(L)的DFA。其中 $h:Σ→Σ∗,∀a∈Σ,h(a)=aah:\Sigma \rightarrow \Sigma ^*,\forall a\in \Sigma ,h\left( a \right) =aa$

6.请为以下语言构造文法： ${w∈{0,1}∗∣w有着两块(block)0，每块0的个数相等}\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{有着两块}\left( block \right) 0\text{，每块}0\text{的个数相等} \right\}$
【注：原题目为“恰有”（just）两块，后来考试中老师把just删掉了】

7.请为以下语言构造deterministic PDA： ${w=anb2n+1∣n⩾1}\left\{ w=a^nb^{2n+1}|n\geqslant 1 \right\}$

8.给定如下CFG：
$S→ASA∣A∣εA→00∣εS\rightarrow ASA|A|\varepsilon \\A\rightarrow 00|\varepsilon$

(1) 消除空产生式
(2) 消除单元产生式
(3) 化为乔姆斯基文法

9.PDA->CFG的一道题目，具体的题目记不得了，书上有，老师也会举例子，就是套公式，方法会了就行

10.请为以下语言设计图灵机： ${aibjck∣k=i×j,k>0}\left\{ a^ib^jc^k|k=i\times j,k>0 \right\}$

后记，仅供参考，有疑问记得问老师，不保证下面说的绝对正确。

所有的设计题，记得画完后验一下空串、一个字符的、两个字符的
第2题，最好是能体现出你画的是NFA，即带有空转移，不同老师要求不一样。有的允许画DFA，有的不允许，一切按照老师要求，老师上课都会强调的，实在不行课后问老师也可以
第3题第一问，记得考虑aaa这种情况
第5题，一定要用数学语言完整的给出所设计DFA的 $(Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_{0},F)$ 才可以
第6题，所谓两块0，中间隔个1才能叫两块，譬如“000100”
第7题，一定要设计DPDA，如果哪一条不符合DPDA的规则，那就丸啦
第8题第一问，S需要派生出来S的，很多同学栽在这上面
第9题，过程也要记得写，最好化简换符号
第10题，注意 $k > 0$ 条件的限定，不要接受空串