我有一个编译器问题。
确定是否 {(ab)^n | n >= 0} 是常规语言吗？
但我可以画出它的 NFA。但是如果我使用抽引引理，我会得到一个矛盾的答案。
谁能帮我 ？
问问题
715 次
1 回答
2
我知道这个线程很旧，但以防万一这可以帮助处于相同情况的另一个学生，这里有一些讨论。这种语言是规则的，您不能使用抽水引理表明它是非常规的。
要查看它是正则的，只需生成一个正则表达式来生成它或生成一个 NFA 来识别它。正则表达式很简单：(ab)*。NFA 很简单：两个状态；初始状态接受，其他不接受；在 a 上从初始转换到其他；从其他到初始 b。完毕。
让我们看看为什么不能在此使用抽水引理。要使用抽水引理，您需要选择一个候选子串进行抽水。对于这种语言，无论你制作多大的字符串，你总是会在长度至少为 2 的符号范围内找到以下子字符串：ab。由于这可能始终是构成循环的子字符串，泵引理说存在，因此无法排除您有一个常规语言，其中某处有 (ab)*，仅使用泵引理。（注意：对于足够长的字符串，也不能排除子字符串 ba）。由于您无法选择抽出的子字符串（对可以取的位置有限制，但这些是引理，而不是您决定的东西），如果任何子字符串有效，
显示例如 L = {a^kb^k | k >= 0} 使用抽引引理是不规则的，您需要选择一个字符串，只要它满足 PL 的假设，您取哪个子字符串都无关紧要。这就是为什么，例如，采用 a^nb^n 是有效的（所有满足 PL 假设的子串都是 a+ 的形式，并且抽水会改变 a 的数量而不改变 b 的数量）。
于 2011-10-21T21:21:44.093 回答