提问人：李力扬 提问时间：11/4/2023 更新时间：11/5/2023 访问量：28
如何证明{（a^m）（b^n）（c^k）： m！=k and m，n，k ∈ N} 是非正则的？
how to prove {(a^m)(b^n)(c^k): m!=k and m,n,k ∈ N} is non-regular?
问：
这是计算机科学课程“计算理论”中的一个问题，关于正则或非常规语言的证明。
如何证明{（a^m）（b^n）（c^k）： m！=k and m，n，k ∈ N} 是非正则的？
我试图通过抽取定理来解决它，但没有成功。
答：
0赞
Frank Yellin
11/5/2023
#1
假设你有你的机器。有两个前缀和 i≠j，它们必须都进入相同的状态，因为你只有有限数量的状态。但是你的机器无法分辨 和 之间的区别，其中一个应该通过，一个不应该通过。a^ia^ja^ibc^ia^jbc^i
上一个：使用信息增益的决策表到决策树
评论