什麼是語言{0^m 1^m 2^n | n> = 0，m> n}

我想知道如何獲取語言{0^m 1^m 2^n | n> = 0，m> n}。什麼是語言{0^m 1^m 2^n | n> = 0，m> n}

這是我所知道的，我不確定它是否正確。請糾正我，如果我錯了：

S -> 01A | 0B1A | 00B11A 
A -> 2A | 2 | λ 
B -> 01

謝謝。

來源

2017-05-18 mina_mz

這顯然不正確：它不能產生'00001111'（m = 4，n = 0），但它可以產生'0122'（違反m> n約束）。第一個問題可以通過使B可重複來解決，也許'B - > 01 | 0B1'（注意這使得你最終選擇S冗餘）。我想不出有什麼方法可以強制m> n而不需要移動到更強大的東西，比如上下文敏感的語法。 – jasonharper

該語言不是上下文無關的。這可以使用上下文無關語言的抽象引理來顯示。你最終有五個案件;其中三個案例只抽取其中一個符號0,1或2;並且兩個箱體泵送相鄰符號。請注意，除了我們可以選擇字符串0 ^（p + 1）1 ^（p + 1）2^p以外，幾乎可以做到這一點，並且即使在跨越0和1s並均勻地抽取它們時，仍然會失敗m> n抽空時測試。

還有更強大的語法比上下文無關。我們可以爲這種語言生成一個通用語法。

S -> RT 
R -> 0R1X | 01 

X1 -> 1X 

XT -> T2 | T 
1T -> e

前兩個製作產生形式0^N（01）（1X）的字符串^ N T.

第三生產產生的形式0^N的串（01）1 n次方X^n T.它允許X在所有1之前「漂浮」到右邊。

最後兩個作品產生的形式爲0^n（01）1^n 2^m，m < = n的字符串。這些允許T在X之後「浮動」，將每個X轉換成2或者沒有。

來源

2017-05-22 14:58:58 Patrick87

什麼是語言{0^m 1^m 2^n | n> = 0，m> n}

回答

相關問題