它是否是上下文無關的語言？

我有一個問題與鍛鍊：它是否是上下文無關的語言？

L = {A ^Ñ b^米Ç^p | 1 < = N < =米< = P}

是否有可能寫爲鍛鍊語法？

我不知道如何解決它:(請幫我

來源

2013-06-01 egos

（1）不，這不是** **上下文無關語言，它實際上是上下文敏感的語言，（2）是其可以寫上下文有關文法這一點。 –

這種語言的語法是什麼？ – egos

語言符合上下文泵引理的條件（在語言中的任何字符串，您可以選擇泵Ç的，並將得到的字符串中的語言仍然），但是這還不足以證明語言是上下文無關。

Ogden's lemma應該工作，但是，對於一個足夠長的輸入字符串，可以選擇「尊貴職位」全部爲的，這迫使一個的時的一個數目被泵送，並最終字符串將被‘泵出的語言的’‘S超過的b’的數量S或ç的。

來源

2013-06-01 18:45:27

你可以寫這個語言的語法，好嗎？ – egos

這聽起來太像真正的工作，目的是什麼？考慮可以被三整除的基數爲10的數字的語言。這是一個普通的一套，因此存在一個正則表達式識別它，但它是令人驚訝的複雜的寫下來，並且不會給你任何真正體會到語言的特性。語法是很好理解上下文無關語言，但是當你到上下文敏感及以上，在這種情況下的複雜程度，你可能會更好過嘗試構建一個適當的自動機，而不是語法。 –

它是否是上下文無關的語言？

回答

相關問題