語言A = {0^n 1^n 0^n}上下文是否免費？

Question

我只是將一些想法放入不同的語言中（正如我正在審查期末考試一樣），我不能想到一個有效的下推自動機來處理語言A = {0^n 1^n 0^n | n> = 0}。這不是一個上下文無關的語言，我是否正確？

Answer 1

我相信你是。它看起來非常類似於語言L = {a^i b^i c^i | i> 0}其中維基百科關於the pumping lemma的文章用作如何證明語言不是上下文的示例。

Answer 2

想一想第二秒的{0^n 1^n}部分。將0替換爲(和1並將其替換爲)，並且您已經使用簡單的嵌套括號語言，這是一種語言不規則的失敗現象。

添加最終的0^n使其對上下文敏感（即不含上下文）。請記住，CFG可以由具有單個堆棧的有限狀態計算機作爲其唯一數據結構來決定。看到一個0會導致一個角色被壓入堆棧，看到一個1會從堆棧彈出。這保證了0的數目與1一樣多，但是沒有辦法再匹配更多 0。