语言 A = {0^n 1^n 0^n} 上下文无关吗？
我只是对不同的语言进行了一些思考（因为我正在复习即将到来的期末考试），我想不出一个有效的下推自动机来处理语言 A = {0^n 1^n 0^n | n>=0}。这不是上下文无关的语言，我是对的吗？
I was just putting some thought into different languages (as I'm reviewing for final exams coming up) and I can not think of a valid pushdown automata to handle the language A = {0^n 1^n 0^n | n >= 0}. This is not a context-free language, am I correct?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我相信你是。它看起来与语言L = { a^ib^ic^i |我> 0 } 维基百科关于泵引理的文章使用了以下示例：如何证明一种语言不是上下文无关的。
I believe you are. It looks quite similar to the language L = { a^i b^i c^i | i > 0 } which the Wikipedia article on the pumping lemma uses as an example of how to prove that a language is not context-free.
想一想 {0^n 1^n} 部分。将
0替换为(，将1替换为)，您就得到了简单嵌套括号的语言，即这完全暴露了一种语言是不规则的。添加最后的 0^n 使其与上下文相关（即不是上下文无关）。请记住，CFG 可以由有限状态计算机决定，并将单个堆栈作为其唯一的数据结构。看到 0 会导致一个字符被压入堆栈，看到 1 则会从堆栈中弹出。这保证了 0 的数量与 1 的数量一样多，但是无法匹配更多 0。
Think of just the {0^n 1^n} part for a second. Replace
0with(and1with)and you've got the language of simple nested parentheses, which is a dead give-away that a language is not regular.Adding the final 0^n makes it context-sensitive (i.e. not context-free). Keep in mind that a CFG can be decided by a finite-state computer with a single stack as its only data structure. Seeing a 0 will cause a character to be pushed onto the stack, and seeing a 1 will pop from the stack. This guarantees that there are as many 0's as 1's, but there's no way to then match more 0's.