正規語言？

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的數量）。