自動機：CFG用於下列語言

Question

請各位看看以下語言：

(a, b, c)* − {anbncn|n≥0}

我的問題是：我如何寫一個上下文無關文法呢？

一般來說，當某些東西被排除在外時（即具有「 - 」符號），我怎樣才能寫出語法？

Answer 1

沒有算法來確定一種語言是否是上下文無關的。因此，對您提出的問題沒有一般的解決方案也就不足爲奇了。

上下文無關的語言在互補，設置差異或交集下沒有關閉。 （但他們下級聯，並集，和克林星形態收市。）在任何情況下

{anbncn|n≥0}

不是上下文無關語言，但它的補（如你的問題）是上下文無關。這個事實的證明（通過構建補語的上下文無關文法）是補充下非CFGs的一個標準例子。過字母表{a,b,c}，其中字母是不是爲了

• 所有字符串：

  概括地說，你的語言L，可以從聯盟組成。換句話說，所有包含子字符串ba,cb或ca的字符串。

• {aibjck|i,j,k≥0∧i≠j}

• {aibjck|i,j,k≥0∧j≠k}

Answer 2

(a, b, c)* − {a^nb^nc^n|n≥0}

這是說，你可以選擇任何一個，b或c，並有其中的任何重複例如abccbaabaab或abca或bccc

對於a *，您使用A->aA |e或A->AA | a | e。

使用規則，你可以這樣做：

S -> A | B | C A->aA |e | AS B->bB |e | BS C->cC |e | CS

的S在每個A，B和C的包容是，如果整個事情上有(....)*一個Kleene星什麼可以用來，並允許您返回到開始處並添加另一個符號。

我不知道如何在排除符號的情況下製作語法，但邏輯上如果-不是可用的終端符號，那麼您已經排除了它。