学长正常情况下只能每科考一回试，希望学弟学妹们日后可以薪火相传。
注：试卷本人只能记住大概意思，记不住具体是怎么描述的，故仅供参考。
05月08日星期天下午13:00~15:00，本人经历了形式语言与自动机考试，现将回忆版试题呈现如下，供大家参考。
先聊聊考试感受：题比，的要难一些，难的来源在于考了一些“以为”可能不会或是可能很少考察的点，上课时还是要认真听老师讲，老师会很明确的说哪里常考哪里会考哪里不考（凡是没明确说不考的，可能都会考，但也不要担心，其实内容不多的）以及不同的题目要遵循怎样的答题规范。
PDF版本将于近期上传至Github：HITSZ-OpenCS项目中，敬请关注~
.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\}L={w∈{0,1}∗∣w既包含00，又包含11}
2.请为以下语言设计NFA：L={w∈{0,1}∗∣w中子串01、10出现的次数相等}L=\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{中子串}01\text{、}10\text{出现的次数相等} \right\}L={w∈{0,1}∗∣w中子串01、10出现的次数相等}
3.请为以下语言设计正则表达式：
(1)L={w∈{a,b}∗∣w中子串aa至少出现两次}L=\left\{ w\in \left\{ a,b \right\} ^*|w\text{中子串}aa\text{至少出现两次} \right\}L={w∈{a,b}∗∣w中子串aa至少出现两次} （之前手抖将此处题目打错，感谢同学帮助指出错误！）
(2)L={w∈{a,b}∗∣w不以aa或bb结尾}L=\left\{ w\in \left\{ a,b \right\} ^*|w\text{不以}aa\text{或}bb\text{结尾} \right\}L={w∈{a,b}∗∣w不以aa或bb结尾}
4.请用泵引理证明L不是正则：L={w∈{0,1}∗∣w中子串00和11出现的次数相等}L=\left\{ w\in \left\{ 0,1 \right\} ^*|w\text{中子串}00\text{和}11\text{出现的次数相等} \right\}L={w∈{0,1}∗∣w中子串00和11出现的次数相等}
5.请从任一正则语言L⊆Σ∗L\subseteq \Sigma ^*L⊆Σ∗ 的DFA出发，用正式的符号语言构造h(L)的DFA。其中h:Σ→Σ∗,∀a∈Σ,h(a)=aah:\Sigma \rightarrow \Sigma ^*,\forall a\in \Sigma ,h\left( a \right) =aah:Σ→Σ∗,∀a∈Σ,h(a)=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\}{w∈{0,1}∗∣w有着两块(block)0，每块0的个数相等}
【注：原题目为“恰有”（just）两块，后来考试中老师把just删掉了】
7.请为以下语言构造deterministic PDA：{w=anb2n+1∣n⩾1}\left\{ w=a^nb^{2n+1}|n\geqslant 1 \right\}{w=anb2n+1∣n⩾1}
8.给定如下CFG：
S→ASA∣A∣εA→00∣εS\rightarrow ASA|A|\varepsilon \\A\rightarrow 00|\varepsilonS→ASA∣A∣εA→00∣ε
(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\}{aibjck∣k=i×j,k>0}
后记，仅供参考，有疑问记得问老师，不保证下面说的绝对正确。
所有的设计题，记得画完后验一下空串、一个字符的、两个字符的第2题，最好是能体现出你画的是NFA，即带有空转移，不同老师要求不一样。有的允许画DFA，有的不允许，一切按照老师要求，老师上课都会强调的，实在不行课后问老师也可以第3题第一问，记得考虑aaa这种情况第5题，一定要用数学语言完整的给出所设计DFA的(Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_{0},F)(Q,Σ,δ,q0,F)才可以第6题，所谓两块0，中间隔个1才能叫两块，譬如“000100”第7题，一定要设计DPDA，如果哪一条不符合DPDA的规则，那就丸啦第8题第一问，S需要派生出来S的，很多同学栽在这上面第9题，过程也要记得写，最好化简换符号第10题，注意k>0k>0k>0条件的限定，不要接受空串
