這是什麼意思「最弱的正式語言」

Question

我正在研究Alex Aiken編譯器設計。在研究解析幻燈片時，Alex說：「正規語言是最弱的正式語言」。

From Youtube video

任何人都可以請澄清這個！提前致謝。

Answer 1

他可能意味着它位於Chomsky Heirarchy的底部。這意味着使用只能解決常規問題的設備（例如正則表達式匹配），您永遠不可能希望模擬更復雜的語言，或者運行一般的軟件，例如合適的計算機。最高級別（在圖表中）比「常規」功能強大得多，稱爲「遞歸枚舉」。描述可通過'圖靈機'或任何現代計算機處理器解決的問題類別。

編輯：剛纔看了視頻，這絕對是他暗指的，但是，如果他有一個更實用的角度。他不是在教你CS理論（雖然它有助於學習理論，我將它與上面相關）。

他的角度更實用，他只是告訴你Regular是編譯代碼的能力最小的那些。這裏是正規的語言他比較：

• 遞歸可枚舉
• 上下文無關
• 上下文敏感
• 定期

經常是最強大的，其他的是更加強大。他接着解釋了其他視頻中常規語言的侷限性。