nlp - (a^p )(b^q) 是常规语言吗

Question

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

让 y 成为 ab 。因此，x(y^n)z 不属于 L，因为对于 n>=1，在 a 之前会有一些 b。但是，表达式不允许这样做。因此，(a^p)(b^q) 不是 RL

Answer 1

不久前我使用了抽引引理，但是a ^p b ^q绝对是一种常规语言。为它写一个正则表达式甚至是微不足道的！a * b *

但是，看起来相似的a ^p b ^p并不规则，因为当开始消耗b符号时，您需要记住您消耗了多少a符号，而有限自动机无法“记住”任意数字。在您的情况下，这不是问题！

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 是正则的并试图达到一个矛盾。

如果您尝试假设您的语言不规则，您应该首先搜索表示语言不规则的字符串类型。让我们尝试在 n>=0 的情况下使用^p b ⁿ。

我们可以对这个字符串做一些假设：因为 |xy|<=p 我们知道 y 只由 a 组成。在这一点上，你可以随意抽它多次，但 xy ⁱ z 是你的语言的成员，因为每个 i>=0。

以类似的方式，如果您为 n>=0选择 a ⁿ b ^{p ，您将不会遇到矛盾。}

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

然而，当且仅当它可以用正则表达式表示时，语言才是正则的。在这种情况下，您可以这样做：a*b*。所以你可以断定这种语言是有规律的。

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