CFG和封閉性

Question

我解決一個問題，我迫切需要一個提示來解決一個問題：在並

使用封閉表明以下語言是上下文無關的：

{一^米 b ^ñç^p d ^q：N = q或米< = p或M + N = p + q}

Answer 1

既然你沒有指定你的問題是什麼，我只會通過你需要知道的。

根據工會關閉 - 這是什麼意思？
如果我們有一種語言L和語言S，並且兩者都是上下文無關的，我們知道這些語言的聯合也是上下文無關的。

大號∪S =上下文無關語言

節能燈更封閉性見this，你可以在網上找到的這證明，如果你有興趣（或者你可以嘗試讓你自己的證據）。

你怎麼用這個來解決你的問題？
您有此語言規範（讓我們稱之爲L）：

L = {A^米 b ^ÑÇ^p d ^q：N = q或米< = p或M + N = p + q}

可以將此語言分成其他3種語言：

A = {A^米 b ^ÑÇ^p d ^q：n爲q}
B = {A^米 b ^ÑÇ^p d ^q：米< = p}
C = {A^米 b ^ñç^p d ^q：M + N = p + q}

很容易看到A ∪ B ∪ C = L。

如果您可以證明A，B和C是上下文無關的，您可以得出結論L也是上下文無關的。

解決方案
要確定一個語言是否是上下文，看this answer。引用答案：

首先，您應該嘗試構建構成主題中語言的context-free grammar。如果所有產品的左手邊只包含一個非終端符號，則語法無上下文。根據定義，如果存在，那麼語言是上下文無關的。

等效結構將是pushdown automaton。它與DFA相同，但有可用的堆棧。構建起來可能比語法更容易。

因此，如果您可以爲每種語言A，B和C構建CFG（或PDA），那麼您已經解決了您的問題。

讓我們的語言A： 我們需要生成表單a..b..c..d..的字符串，我們必須有b S和d秒的等量的語法。

S -> AE 
A -> Aa | ε 
E -> bEd | C 
C -> Cc | ε 

S是開始變量（或非末端），ε是空字符串（有些人用空符號^但我一直被告知使用ε）。該語法應該能夠生成語言A，因此A是上下文無關的。 （請讓我知道是否有人發現錯誤，我還沒有創建CFGs）。

由於這是一個練習，我會讓你解決其餘的部分，但你應該已經知道如何去做。