我只是將一些想法放入不同的語言中(正如我正在審查期末考試一樣),我不能想到一個有效的下推自動機來處理語言A = {0^n 1^n 0^n | n> = 0}。這不是一個上下文無關的語言,我是否正確?語言A = {0^n 1^n 0^n}上下文是否免費?
4
A
回答
5
我相信你是。它看起來非常類似於語言L = {a^i b^i c^i | i> 0}其中維基百科關於the pumping lemma的文章用作如何證明語言不是上下文的示例。
+1
對於原始海報,我建議試圖按照上述提及的證明的相同步驟來使用您感興趣的語言。 – 2010-04-11 21:14:24
+0
該語言未能通過CFLS的抽象引理 – jfisk 2011-12-08 04:37:50
1
想一想第二秒的{0^n 1^n}部分。將0
替換爲(
和1
並將其替換爲)
,並且您已經使用簡單的嵌套括號語言,這是一種語言不規則的失敗現象。
添加最終的0^n使其對上下文敏感(即不含上下文)。請記住,CFG可以由具有單個堆棧的有限狀態計算機作爲其唯一數據結構來決定。看到一個0會導致一個角色被壓入堆棧,看到一個1會從堆棧彈出。這保證了0的數目與1一樣多,但是沒有辦法再匹配更多 0。
相關問題
- 1. 單點登錄0N,ASP.NET應用程序
- 2. 「線程被中止」0n大數據集
- 3. 1或2右側變量上下文免費語言
- 4. 上下文免費語法提示
- 5. 上下文免費語法分析樹
- 6. Yacc上下文免費語法
- 7. C++上下文免費語法庫
- 8. 下面的語言環境是免費的語法嗎?
- 9. 理論:給定的語言環境是否是免費的?
- 10. jquery遞增數字+1 0n頁面刷新
- 11. WW是W所屬的{a,b} *上下文無關語言嗎?
- 12. 是否有任何不是上下文無關語言的正規語言?
- 13. 將上下文免費語法轉換爲LL1語法
- 14. 是否有免費的大多數iso 639(語言)代碼的文檔?
- 15. 是否有免費的言論來JavaScript的文本API的?
- 16. 免費的語言標識符服務?
- 17. 它是否是上下文無關的語言?
- 18. 上下文免費語法求和符號
- 19. 解析樹的上下文免費語法
- 20. 從上下文免費語法中刪除循環遞歸
- 21. 刪除上下文免費語法中的左遞歸
- 22. 確定一種語言是否無上下文
- 23. 是否有免費提示?
- 24. A *算法檢查圖k3是否免費
- 25. 什麼是語境免費語法?
- 26. iPhone上的MPMoviePlayerController是否有替代品(免費或付費)?
- 27. Sitecore的上傳,使用項目的語言,而不是上下文語言
- 28. 這是語法{a^2n b^n | n> = 0}上下文是否空閒?
- 29. TI-BASIC是否有免費版本?
- 30. 決定是否給定的語言是普通/上下文無關/非上下文無關
http://stackoverflow.com/questions/2617675/theory-of-computation-using-the-pumping-lemma-for-context-free-languages – 2010-04-11 19:58:19
@Andrew這些是單獨的語言:) – Tony 2010-04-11 20:00:00
@安德魯:另外,「常規」和「上下文無關」是完全不同的*語言 – SamB 2010-04-11 20:12:05