顯示語言是上下文無關的

我被要求證明ABA^R形式的歌曲集是上下文無關的（其中A^R是A顛倒的）。我不知道如何顯示一種語言無上下文。顯示語言是上下文無關的

我們還沒有專門研究如何顯示一種語言是上下文無關的，所以它不能太複雜。我能想到的唯一的事情就是爲語言創建一個上下文無關的語法，但我不知道這足以證明它沒有上下文，或者我如何爲一組歌曲創建語法。

2014-09-26 Þór Óðinsson

這裏有一個答案︰http://stackoverflow.com/questions/3510109/how-can-i-determine-if-a-language-is-context-free- or-not另外請注意，創建上下文無關語法對於顯示語言無上下文是很好的。 – 2014-09-26 04:21:47

您不能使用抽象引理來顯示語言無上下文。它只能用來表明它不是。有滿足抽象引理的非上下文無關語言。 – 2014-09-26 04:23:13

A和B是一組字符串還是什麼？ – 2014-09-26 04:24:38

假設A和B是一組字符串，它們是上下文無關的，那麼語言A和B就有上下文無關語法，比如說G_A和G_B。您可以很容易地從G_A獲取語言A^R的上下文無關語法。只要顛倒語法規則的右邊，並且你有A^R的語法。

如果G_A的起始變量是S_A，G_B是S_B且G_A^R是S_A'，那麼最終語法將是這些語法的組合（三個語法的每個變量應該唯一地命名）與新的起始變量和新規則說明

S -> S_A S_B S_A'

來源

2014-09-26 04:35:01

在從你的S中獲得一個句子（「歌曲」）時，S_A'不會被限制爲派生一個與S_A派生出來的相反的短語，我認爲原始問題需要什麼。 – 2014-09-26 17:21:08

@MichaelDyck S_A從A派生字符串，S_A'從A^R派生字符串。這兩個字符串可能不是彼此相反，這是故意的。這是OP要求的。如果這些應該是彼此相反的（我認爲你是這樣想的），那麼問題應該被問爲L = {xyx^R | x \ in A和y \ in B} – 2014-09-26 19:48:55

顯示語言是上下文無關的

回答

相關問題