如何将语言分为常规语言、上下文无关语言和短语结构语言？
如果给你一种语言，你如何判断它是常规语言、CF 但不是常规语言，还是短语结构但不是 CF？有没有好的方法来解决这个问题？我可以随意尝试制作 FA 或 PDA，但我觉得有更好的方法来做到这一点。
经典例子：
L = { a^nb^nc^n | n >= 0 }
从哪里开始？ 谢谢。
If you're given a language, how do you figure out if it's regular, CF but not regular, or phrase-structure but not CF? Is there a good way to attack this problem? I could randomly try to make FAs or PDAs, but I feel like there's a better way to do it.
Classic example:
L = { a^n b^n c^n | n >= 0 }
Where would one start?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你对它们进行分类有了一定的感觉。我不知道有什么非常有条理的方法。由于语言通常是彼此的子集和超集，因此您可以估计它在该层次结构中的位置，并表明它不可能是常规语言，但它可能是 CFL。
You sort of get a feel for classifying them. I don't know of a very methodical approach. Since languages are usually subsets and supersets of each other, you estimate where it fits in that hierarchy and show that it can't be, say, a regular language, but it could be a CFL.