什么是概率上下文無關文法？

上下文無關文法能描述一個能被下推自動機識別的語言，即上下文無關語言；圖靈機可以識別遞歸可枚舉語言。X圖靈等價是指X能做圖靈機能做的所有事情， 圖靈機能做X能做的所有事情。X圖靈完備是指X能做圖靈機能做的所有事情。通常說X編程語言是上下文無關語言是指能通過X編程語言的語法分析的語言是上下文無關語言，也就是說識別通過X編程語言的語法分析的語言的文法是上下文無關文法。而實際上，能通過X編程語言的編譯的語言完全可能是遞歸可枚舉語言。舉個例子，通過C++的語法分析的語言是上下文無關語言（這里可能不是很嚴格，有可能通過語法分析的時候就已經不是上下文無關語言了），也就是說下面代碼可能就能通過C++的語法分析，然而它并不能通過編譯。

而由于C++強大的模板功能，所以實際上能通過C++的編譯的語言實際上應該是遞歸可枚舉語言。所以編譯C++的自動機是圖靈等價的（有趣的結論：我們可以寫一個C++程序，使得編譯器的編譯過程陷入死循環；當然，這里的圖靈等價不是嚴格的，畢竟我們的機器的存儲空間不是無限的）。對于編譯出來的文件，因為都是執行在圖靈等價的計算機上（這里的圖靈等價也不是嚴格的，理由跟之前一樣），所以編譯出來的文件最極限的就是能做所有圖靈機能做的事情，因此，如果編譯出來的文件是圖靈等價的，那么他就已經到達極限了。不過是否有一個自動機能做圖靈機做不了的事情現在還沒有定論，所以如果存在這樣的機器（比如假想的Oracle machine），就可以有不是圖靈等價并且是圖靈完備的編程語言了。因此：1.那如果文法就是圖靈等價的，寫出的程序會不一樣么？不會。2.還是說二者本來就沒關系，語言用哪類文法不過是設計者隨性而為。沒有關系。不是隨性的吧。3.或者說因為圖靈機定義了程序能力的上限，當然。不過可能有比圖靈機更厲害的自動機哦，如果在上面跑程序就突破圖靈機的上限了。4.所以反過來，語言文法越簡單越好，比如3型文法更好？都說了不是隨性的啦。