哈工大本部2023形式语言与自动机期末试题
学长正常情况下只能每科考一回试，希望学弟学妹们日后可以薪火相传。注：试卷本人只能记住大概意思，记不住具体是怎么描述的，故仅供参考。
有同学发布了老师原版的英文考试试题，有原版的英文试题还看我这个回忆版干啥233，链接：https://blog.csdn.net/weixin_44705388/article/details/126386915。这位同学发布的文章遵循CC4.0BY-SA协议，该协议允许对原作进行修改、分享，故本人将其中的内容合并到了本回忆题中，方便大家参考。同时，本文章亦遵循CC4.0BY-SA协议。
2022年05月08日星期天下午13:00~15:00，本人经历了形式语言与自动机考试，现将回忆版试题呈现如下，供大家参考。
先聊聊考试感受：题比2019，2020的要难一些，难的来源在于考了一些“以为”可能不会或是可能很少考察的点，上课时还是要认真听老师讲，老师会很明确的说哪里常考哪里会考哪里不考（凡是没明确说不考的，可能都会考，但也不要担心，其实内容不多的）以及不同的题目要遵循怎样的答题规范。
PDF版本将于近期上传至Github：HITSZ-OpenCS项目中，敬请关注~
2022.05.19Update：成绩出来了，有问题可以问老师，老师会把你扣分的点说的明明白白，让你心服口服。本人考试时写的什么，现在也很难一模一样地复现了，答案就不提供了：），个人认为一些较坑的点，会放在文末。
1.请为以下语言设计DFA：L={w∈{0,1}∗∣w既包含00，又包含11}L=left{winleft{0,1 ight}^*|w ext{既包含}00 ext{，又包含}11 ight}L={w∈{0,1}∗∣w既包含00，又包含11}
[10points]DesignaDFAforL={w∈{0,1}∗∣wL=left{win{0,1}^*midw ight.L={w∈{0,1}∗∣wcontainsboth00and11assubstrings}}}.
2.请为以下语言设计NFA：L={w∈{0,1}∗∣w中子串01、10出现的次数相等}L=left{winleft{0,1 ight}^*|w ext{中子串}01 ext{、}10 ext{出现的次数相等} ight}L={w∈{0,1}∗∣w中子串01、10出现的次数相等}
[10points]DesignanNFAforL={w∈{0,1}∗∣wL=left{win{0,1}^*midw ight.L={w∈{0,1}∗∣wcontainsancqualnumberofoccurrencesofthesubstrings01and10}}}.
3.请为以下语言设计正则表达式：(1)L={w∈{a,b}∗∣w中子串aa至少出现两次}L=left{winleft{a,b ight}^*|w ext{中子串}aa ext{至少出现两次} ight}L={w∈{a,b}∗∣w中子串aa至少出现两次}（之前手抖将此处题目打错，感谢同学帮助指出错误！）
(2)L={w∈{a,b}∗∣w不以aa或bb结尾}L=left{winleft{a,b ight}^*|w ext{不以}aa ext{或}bb ext{结尾} ight}L={w∈{a,b}∗∣w不以aa或bb结尾}
[10points]DesignregularexpressionsforlanguagesoverΣ={a,b}Sigma={a,b}Σ={a,b}:(1)Allstringshavingatleasttwooccurrencesofthesubstringaaaaaa.(2)Allstringsthatdonotendwithsubstringsaaaaaaorbbbbbb.
4.请用泵引理证明L不是正则：L={w∈{0,1}∗∣w中子串00和11出现的次数相等}L=left{winleft{0,1 ight}^*|w ext{中子串}00 ext{和}11 ext{出现的次数相等} ight}L={w∈{0,1}∗∣w中子串00和11出现的次数相等}
[10points]ProvethatthelanguageLLLisnotregularwithpumpinglemmaL={w∈{0,1}∗∣wL=left{win{0,1}^*midw ight.L={w∈{0,1}∗∣whasthesamenumberofsubstrings00and11}}}.
5.请从任一正则语言L⊆Σ∗LsubseteqSigma^*L⊆Σ∗的DFA出发，用正式的符号语言构造h(L)的DFA。其中h:Σ→Σ∗,∀a∈Σ,h(a)=aah:Sigma ightarrowSigma^*,forallainSigma,hleft(a ight)=aah:Σ→Σ∗,∀a∈Σ,h(a)=aa
[10points]Leth:Σ→Σ∗h:Sigma ightarrowSigma^*h:Σ→Σ∗beahomomorphism:∀a∈Σ,h(a)=aaforallainSigma,h(a)=aa∀a∈Σ,h(a)=aa.PleasegiveaformalconstructionoftheDFAforh(L)h(L)h(L)fromtheDFAthatacceptstheregularlanguageLLLoverΣSigmaΣ.
6.请为以下语言构造文法：{w∈{0,1}∗∣w有着两块(block)0，每块0的个数相等}left{winleft{0,1 ight}^*|w ext{有着两块}left(block ight)0 ext{，每块}0 ext{的个数相等} ight}{w∈{0,1}∗∣w有着两块(block)0，每块0的个数相等}【注：原题目为“恰有”（just）两块，后来考试中老师把just删掉了】
[10points]Designacontext-freegrammarforthelanguageL={x∈{0,1}∗∣xL=left{xin{0,1}^*midx ight.L={x∈{0,1}∗∣xhasjusttwononemptyblocksof0softhesamelength}}}.
7.请为以下语言构造deterministicPDA：{w=anb2n+1∣n⩾1}left{w=a^nb^{2n+1}|ngeqslant1 ight}{w=anb2n+1∣n⩾1}
[10points]DesignadeterministicPDAforL={anb2n+1∣n≥1}L=left{a^nb^{2n+1}midngeq1 ight}L={anb2n+1∣n≥1}.
8.给定如下CFG：S→ASA∣A∣εA→00∣εS ightarrowASA|A|varepsilon\A ightarrow00|varepsilonS→ASA∣A∣εA→00∣ε
(1)消除空产生式(2)消除单元产生式(3)化为乔姆斯基文法
[10points]Beginwiththegrammar:S→ASA∣A∣εA→00∣εegin{aligned}&S ightarrowASA|A|varepsilon\&A ightarrow00midvarepsilonend{aligned}S→ASA∣A∣εA→00∣ε(1)Eliminateanyεvarepsilonε-productions.(2)Eliminateanyunitproductionsintheresultinggrammar.(3)PuttheresultinggrammarintoChomskyNormalForm.
9.PDA->CFG的一道题目，具体的题目记不得了，书上有，老师也会举例子，就是套公式，方法会了就行
[10points]ConsideraPDAPPPwithstartstateqqq,startsymbolZZZinthestackandthefollowingtransitionrules.PleaseconvertPPPtoanequivalentCFG.(1)δ(q,0,Z)={(q,X)}delta(q,0,Z)={(q,X)}δ(q,0,Z)={(q,X)}(2)δ(q,0,X)={(q,XX)}delta(q,0,X)={(q,XX)}δ(q,0,X)={(q,XX)}(3)δ(q,1,X)={(r,X)}delta(q,1,X)={(r,X)}δ(q,1,X)={(r,X)}(4)δ(r,0,X)={(r,ε)}delta(r,0,X)={(r,varepsilon)}δ(r,0,X)={(r,ε)}
10.请为以下语言设计图灵机：{aibjck∣k=i×j,k>0}left{a^ib^jc^k|k=i imesj,k>0 ight}{aibjck∣k=i×j,k>0}
[10points]DesignaTuringmachineforL={aibjck∣k=i×jL=left{a^ib^jc^kmidk=i imesj ight.L={aibjck∣k=i×jandk>0}left.k>0 ight}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条件的限定，不要接受空串哈工大《大数据计算基础》期末考试
哈工大《大数据计算基础》期末考试留给学弟学妹们参考
题型：判断、简答、综合题
判断：10x2分非常简单，记不住了
简答：4x5分
SparkRDD是什么及特点？
大数据算法中采样技术在哪些算法中有应用（AMS、水库采样）及如何分析？
HDFS写文件流程？
NoSQL中CAP理论是什么，能否全部实现？
综合题：60分
亚线性时间算法计算连通分量数的分析，3问15分（算法）亚线性空间算法不重复元素数算法设计，FM算法的思想，MapReduce编程实现，以及MapReduce流程，6问30分（算法+系统）高并发环境下大数据计算与管理系统的设计，4问15分（系统）算法部分复习看课件就足够了，一般不会出太难的题。系统部分不需要完全清楚每个框架的细节，理解基本原理即可，重点在理解如何实现可扩展性、容错性、可靠性、一致性、数据如何划分、发生数据偏斜如何处理、NoSQL和NewSQL的基本理论等内容。