證明以下語言是上下文無關的：

這個問題是在一個樣本考試中，我們的教授懶得打出解決方案，而我被卡住了很糟糕。在此先感謝您的幫助！證明以下語言是上下文無關的：

證明下列語言上下文{x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}

來源

2012-04-05 Tarvaris Jackson

提示：DFA不能計數。 – cHao 2012-04-05 00:29:24

您可能會在Math.SE上獲得更好的響應。 – 2012-04-05 00:53:46

@KendallFrey我會建議[CSTheory]（http://cstheory.stackexchange.com/）:) – 2012-07-16 19:06:19

{x是的元素{A，B，C} * |在X A的數目大於B的數目或c的在X}

這可以解釋兩種方式的數目大：

的a的數量大於（的b數量的加c數量的）
（的a數的比的b數大的）或（的a數的比的c數量更大的「 S）。

提示1：PDA可以工作如下。如果堆棧爲空，並且在輸入上看到一個a，則將一個a添加到堆棧。如果堆棧爲空，並且在輸入上看到b或c，請將b添加到堆棧。如果最上面的堆棧符號是b，並且您在輸入上看到了a，請從堆棧中刪除b。如果最上面的堆棧符號是b，並且您在輸入上看到了b或c，請將另一個b添加到堆棧。如果最上面的堆棧符號是a，並且您在輸入上看到了a，請將另一個a添加到堆棧。如果最上面的堆棧符號是a，並且您在輸入上看到b或c，請從堆棧中刪除a。現在簡單地產生一個論點，即如果a的數目等於b和c的數目之和，則這樣的PDA將具有（1）空的堆棧; （2）a如果它看到更多的a的比它看到b的或c的（組合）; （3）在堆棧頂部的b，如果它看到的數量比b或c（組合）的數量少a。

提示2：首先，構造一個PDA接受的a的，b的，而且比b小號c '其具有多個a s' 的任意字符串的，忽略任何c的（上面描述的PDA在提示1中可以很容易地修改爲忽略c's）。然後，構建一個PDA，接受a的b和c的a的c的任意字符串，忽略任何b的（與您剛建立的類似）。最後，證明你試圖證明上下文無關的語言是這些自動機接受的語言的結合;一個簡單的論證就足夠了。由於上下文無關的語言在聯合下關閉，這就說明了這一說法，即您設置的用於證明上下文無關的語言的確是上下文無關的。

請隨時要求進一步澄清。另外，請查看新網站，以獲得如下問題：https://cs.stackexchange.com/。您可能會在該網站的未來問題上得到更好的答案。

來源

2012-04-05 13:47:57 Patrick87

-2

的任務是表明語言可以通過上下文無關文法產生。

一些提示：

A -> aabAc | B 
B -> B|epsilon

來源

2012-04-05 00:45:47 kasavbere

證明以下語言是上下文無關的：

回答

相關問題