是字母表“a,b,c”上所有字符串的语言吗？具有相同数量的子串“ab” & “吧”常规的？

Question

是字母表“a,b,c”上具有相同数量的子串“ab”和“a,b,c”的所有字符串的语言“ba”常规吗？

我相信答案是否定的，但是很难对其进行正式的演示，甚至是非正式的演示。

关于如何解决这个问题有什么想法吗？

Answer 1

这显然不正常。 FA 如何识别 (abc)^nc (cba)^n。像这样的字符串是用你的语言写的，对吗？该论证是一个简单的论证，基于不可区分关系 I_l 下存在无限多个等价类这一事实。

Answer 2

证明语言不规则的最常见方法是使用抽引理。

使用引理有点棘手，因为它具有所有这些“存在”等等。要使用泵引理证明语言 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 建议的等价类方法即可 - 它可能会比您为使泵送引理适用于此处而需要执行的任何肮脏技巧更干净。