字母表“a，b，c”中所有字符串的语言是否具有相同数量的子字符串“ab”和“ba”？
我相信答案是否定的，但很难对其进行正式的演示，即使是非正式的演示。
关于如何解决这个问题的任何想法？
问问题
835 次
2 回答
2
这显然不正常。FA 将如何识别 (abc)^nc (cba)^n。像这样的字符串是你的语言，对吧？该论点是一个简单的论点，它基于在不可区分关系 I_l 下存在无限多个等价类这一事实。
于 2011-08-13T19:16:27.690 回答
0
证明语言不规则的最常见方法是使用Pumping Lemmas。
使用引理有点棘手，因为它具有所有那些“存在”等等。要使用抽水引理证明语言 L 是不规则的，您必须证明
for any integer p,
there is a word w in L of length n, with n>=p, such that
for all possible ways to decompose w as xyz, with len(xy) <= p and y non empty
there exists an i such that x(y^i)z (repeating the y bit i times) is NOT in L
哇！
我将展示如何寻找“相同数量的 as 和 bs”语言的证明。转换为您的案例应该是直截了当的：
for any given p, we can make a word of length n = 2*p
a^p b^p (p a's followed by p b's)
any way you decompose this into xyz w/ |xy| <=p, y will only contain a's.
Thus, pumping the the y part will make the word have more as than bs,
thus NOT belonging to L.
如果您需要直觉知道为什么会这样，那么您需要如何计数到任意大的数字来验证单词是否属于其中一种语言。然而，正则语言是由有限自动机描述的，没有有限自动机可以表示表示所有数字所需的无限数量的状态。（维基百科的文章应该有正式的证明）。
编辑：看起来你不能直接在这种特殊情况下直接使用抽引引理：如果你总是让y一个字符长，你永远不能让一个词停止被接受（aba 变成 abbbba 没有区别等等）。
只需执行 Patrick87 建议的等价类方法 - 它可能会比您需要做的任何肮脏的黑客攻击更干净，以使抽水引理适用于此。
于 2011-08-13T18:01:52.217 回答