正规语言？

Question

我有一个编译器问题。

确定是否{（ab）^ n | n> = 0}是常规语言吗？

但我可以画出它的NFA。 但是如果我使用抽象引理，我会得到一个矛盾的答案。

任何人都可以帮助我吗？

Answer 1

我知道这个帖子是旧的，但为了以防万一这可以帮助另一个学生在相同的情况下，这里有一些讨论。这种语言是常规的，你不能用抽象引理来表明它是非常规的。

要想看到它是正常的，只需生成一个正则表达式来生成它或通过NFA来识别它。正则表达式很简单：（ab）*。 NFA很容易：两个州;初始状态接受，其他不是;从一个初始过渡到另一个;从其他到最初的b。完成。

让我们来看看为什么抽水引理不能用于此。要使用抽吸引理，你需要选择一个候选子串来抽取。对于这种语言，不管字符串有多大，总会在长度至少为2的符号范围内找到以下子字符串：ab。由于这可能永远是构成循环的子串，抽形引理说存在，所以没有办法排除你有一个正常的语言（ab）*在里面的某个地方，单独使用抽象引理。 （注意：对于足够长的字符串，您不能排除子字符串ba）。既然你不能选择被抽取的子字符串（这里有限制它可以被采用的地方，但是这些被放置在引理中，而不是你决定的），如果任何子字符串工作，你会丢失和抽取引理没有证明任何东西。

为了显示例如那L = {a^k b^k | k> = 0}不是使用抽象引理的规则，只要满足PL的假设，就需要选择一个字符串，它对哪个子字符串不重要。这就是为什么例如采取^ n b^n工作（满足PL的假设的所有子串都是形式a +的形式，并且抽吸将改变a的数量而不改变b的数量）。