(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^pb^q绝对是一种常规语言。甚至为它写一个正则表达式都是微不足道的! * b *

类似的a^pb^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是正则的，并试图得出一个矛盾。

如果你试图假设你的语言不是规则的，你应该首先搜索代表语言不规则性的字符串类型。让尝试用<一口> p b <一口> n n> = 0。

我们可以对这个字符串做一些假设:因为|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。