让Nf和Np分别表示非确定性有限自动机和非确定性下推自动机所接受的语言类。让Df和Dp分别表示确定性有限自动机和确定性下推自动机所接受的语言类。以下哪一项是正确的？ （A） Df⊂ Nf和Dp⊂ NP （B） Df⊂ Nf和Dp=Np （C） Df=Nf，Dp=Np （D） Df=Nf和Dp⊂ NP 答复: （D） 说明： 确定性下推自动机可以识别所有确定性上下文无关语言，而非确定性下推自动机可以识别所有上下文无关语言。前者主要用于解析器设计（来源： http://en.wikipedia.org/wiki/Pushdown_automaton )确定性上下文无关语言（DCFL）是上下文无关语言的适当子集。
null
非确定性有限自动机和确定性有限自动机都接受相同的语言集，因为NFA可以使用子集构造算法转换为等价的DFA。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
