regular-language - 使用 Pumping Lemma 证明语言不规则

Question

我试图使用抽水引理证明以下语言不规则。

L = {a ^k b ^3l a ^l | k ≥ 1 , l ≥ 0}

我决定选择 w = ab ^3p a ^p，然后选择 |w| = 4p+1 ≥ p

有小费吗？

谢谢！

Answer 1

我不确定您正在使用的抽水引理的确切公式。无论如何，这是一个相当棘手的情况，因为像维基百科这样的标准公式只能让你以固定长度的前缀抽取某个位置。但是您的初始块 a 允许在任何地方抽水，并且可以任意长。因此，您必须使用一些额外的属性。我建议两个：

• 正则语言在反转下关闭。因此你不妨看看 $L^R = {a^lb^{3l} a^k}$。现在，在 a 的初始块中的任何抽水都会导致语言脱离。
• 常规语言在交集下关闭。如果你用 b+ a+ 进行交集，你会得到 ${ab^{3l} a^k}$，现在在 b 块中抽水会让你脱离语言。