CS 3800在线W. Schnyder
2024年春季3/6/2024
课业7（3月15日星期五到期）
说明：此课业应在到期日之前11:59 pm之前以一年级的PDF（不零件）提交。 您可以在文字处理器中键入解决方案，然后将其打印到PDF，或者手工编写并提交扫描副本。 写下并提交答案，就像他们是专业报告一样。 如果提交不整洁（无序，难以阅读，颠倒扫描等等……），将会扣除点。
首先查看您的课堂笔记，幻灯片和教科书。 然后进行以下练习。 展示你的工作。 一个不合理的答案可能几乎没有或根本没有信用。
阅读：2.3（周二）和3.1（周五）
- [8分]下降。 对于字母{a，b}上的以下每种语言，绘制接受此语言的下降自动机的状态图。 为了获得全部信贷，您的自动机应该拥有尽可能少的状态。 （在下面，假设M，N≥0）。
（a）{anbm | n≤m}。 （b）{anbm | n≥m}。 - [6分]下降。 构造一个下降自动机P，使得（假设M，N≥0）：l（p）= {ambn | n = 2m}
指定自动机的组件并绘制状态二元格。 为了获得全部信贷，您的自动机应该拥有尽可能少的状态。 - [6分]下降。 构建一个下降自动机P，使得（假设M，n≥0）：l（p）= {ambn |m≤n≤2m}
指定自动机的组件并绘制状态二元格。 为了获得全部信贷，您的自动机应该拥有尽可能少的状态。 - [15分]交叉点。 考虑语言（n和m是自然数≥0）l = {anbm | n> mandniseven}
显然l = lcf l∩lreg
lcfl = {anbm | n> m} andlreg = {w∈{a，b} ∗ | whasanevennumberofa}（a）为LREG绘制DFA的状态图。 为了获得全部信贷，您的自动机应该拥有尽可能少的状态。 第1页，共3页
CS 3800在线HW 7春季2024（b）为LCFL绘制PDA的状态图。 为了获得全部信用，您的自动机应该尽可能少。（c）将算法（讲座15d）应用于L。绘制自动机的状态图。 （请勿删除无用的状态，此问题只要求您证明您对算法的理解。） - [8分]闭合属性。 在此问题中，您不允许您构建革兰氏阴性或自动机。 可以使用闭合属性显示一切。 在整个过程中，参考字母为σ= {a，b}，n表示自然数（包括0）； 和n，m∈N。
（a）在问题1中，您表明了语言
{anbm |n≤m}和{anbm |n≥m}
无上下文。 用这个事实给出非常简单的证据，证明{anbm | n <m}和{anbm | n> m}
无上下文。
（b）证明语言 - [6分]闭合属性。 假设L是不含上下文的，R是常规的。
（a）l-r一定是无上下文的吗？ 证明您的答案是合理的。 （b）r -l一定是免费的吗？ 证明您的答案是合理的。 - [5分]抽引理。 证明泵送引理的以下变体：
对于每种无上下文语言l都存在泵送长度p≥0，以使每个单词
Ww∈L和| w | ≥p可以写为w = uvxyz
这样
我。 | vxy |≤pii。 v̸=ε
iii。 uvnxynz∈Lforalln≥0
您的证明应该简单明了。 教科书中对问题2.37的引用将不接受。无上下文。第2页，共3页
CS 3800在线HW 7春季2024 - [9分]泵送引理。 这个问题会导致您通过基于泵送引理的证明逐步逐步（下一个问题不会指示步骤）。 您将显示该语言
l = {anb2nck | n>k≥0}（a）假设（对于矛盾）L是免费的。 然后它具有抽水长度不是免费上下文。
p≥1。 何斯普≥1？（b）每个单词w∈L，长度| w | ≥p可以写为W = uvxyz具有三个特性。 这三个属性是什么？
选择w = apb2pcp -1单词（c）在情况v开头的情况下得出矛盾。dai 写CS 3800（d）在v v始于b的情况下，得出矛盾。 （e）在情况v开头的情况下得出矛盾。（f）使用问题7解释上述证据已完成。 - [8分]抽引理。 在这个问题中，您将显示该语言
l = {www | w∈{a，b，c} ∗}（a）使用抽水引理表明语言{anbanbanb | n≥1}不是
不是无上下文。 免费上下文。（b）使用CFL的闭合特性得出结论L不是上下文。 （不要直接证明。） - [0分]不要提交。 练习2.6（AC）第155页。解决方案在书160页中，仅用于实践。
- [0分]不要提交。 练习2.7（AD）第155页。解决方案在第160页中，仅用于实践。
- [0分]不要提交。 练习2.8 Page 155.解决方案是在书161页中，仅供实践。
- [0分]不要提交。 问题2.18第156页。解决方案在演讲中涵盖，也在书161页中，仅用于实践。