很显然助教sama知道这个repo的存在，把这里存在的试题上传到的网络学堂作为样题。

本学期《自动寄》考试前半部分（判断题，选择题，操作题）和前面的样卷风格和考点基本类似。

设计题和证明题比较新。

## 设计题

+ 为 $\{w|w=a^*b^*\}$ 不包含字串 $aabbbb$ 和 $aaabb$ 设计有限自动机，状态数不超过 8
+ 同上，设计正则表达式
+ 为 $a^nb^m, m\le 2n \le 4m$​ 设计 CFG，非终结符个数不超过 $1$​​，并证明你写的是对的
  + 注意 $S\rightarrow aSb$，证明用归纳法，从 $m=k-1$ 和 $m=k$ 推出 $m=k+1$​ 也成立
+ 实现 $\Sigma^* - \{a^nb^n\}$​ ​的PDA
+ 图灵机，实现排序，即给定一个0/1串，对这个序列排序，把 0 都放到 1 的前面，状态数不超过 7.
  + 交换逆序对就行

## 证明题

第一题忘了。第二题是正规语言的 Pumping Lemma，需要刚开始转化几步看出来在考这个。第三题是证明CFL和RE的交还是CFL，每年好像都要考一个课本定理的证明。



附加题两道题，二选一。一道考了什么最右推导与什么什么Prefix，当时没选这道写；另一道是自底向上的归约自动机，做了 25min 不会。考试题量还是比较大的，最后全部考场延时了 15min。