开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >正则语言可以有线性有界自动机吗

问正则语言可以有线性有界自动机吗
EN

Stack Overflow用户

提问于 2013-03-31 06:37:44

回答 1查看 198关注 0票数 1

正如问题所述：

我正在尝试理解自动机。每种正则语言都能有一个线性有界自动机吗？

automata-theory

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-04-12 02:40:43

是的，每种正规语言都有线性有界自动机是可能的。正则语言是上下文敏感语言的真子集。CSL是与线性有界自动机 (LBA)相关的语言。有关形式语法和语言的类的层次结构的更多信息，请阅读Chomsky Hierarchy。

http://en.wikipedia.org/wiki/Chomsky_hierarchy

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15724278

复制

相似问题