是（a^p）（b^q）常规语言

Question

我在某处读到{（a^p）（b^q）：p，Q属于N}是一种常规语言。但是，我不认为这是正确的。这可以用抽象引理证明。只是想验证我的解决方案是否正确

让y是ab。因此，x（y^n）z不属于L，因为当n> = 1时，在a之前会有一些b。但是，表达式不允许这样做。因此，（一^ P）（B^Q）是不是一个RL

Answer 1

这是前一段时间我用泵引理，但一个^p b ^q绝对是一个正规语言。为它写一个正则表达式甚至是微不足道的！ 一个 * b *

外观相似一个^p b ^p是不正规，但因为开始消耗b -symbols时，你需要记住多少一个你消耗的符号，有限自动机不能“记住”任意数字。这对你的情况不是问题！

Answer 2

抽吸引理说： 如果一个语言A是规则=>有一个数字p（抽长度），如果s是L中的任何字符串，使得| s | > = p，则S可以被分成三件S = XYZ，满足以下条件：

1. XY ^我 z为以L对于每个i> = 0
2. | Y |> = 0
3. p> = | xy |

表明某种语言L不规则的正确方法是假定L规则并尝试达成矛盾。

如果您试图假设您的语言不规则，您应该首先搜索代表该语言不规则性的字符串类型。 让我们试试^p b ⁿ n> = 0。

我们可以对这个字符串做一些假设：因为| xy | < = p我们知道y只由a组成。此时，您可以根据需要抽多次，但xy ⁱ z是每个i> = 0时您的语言的成员。

以类似的方式，如果您选择ⁿ b ^p n> = 0，您将不会达成矛盾。

L = {a ⁿ b ⁿ | n> = 0}是不规则的，但是你对p和q没有约束（我的意思是，不需要计算a和b的出现次数）。

但是，语言是规则的，当且仅当它可以用正则表达式表示。在这种情况下，你可以这样做：a * b *。所以你可以得出结论，这种语言是经常性的。

编辑： 对于p < = q语言不规则，但您正在考虑任何p和q。