计算理论基础教学大纲内容摘要：
上下文无关文法 ： 上下文无关文法的相关定义：规则，非终结符，终结符，它生成的语言等。 还有其上的推导。 上下文无关语言与正则语言的关系。 语法分析树，推导之间的“ 先于 ”关系，最左，最右推导； 歧义性的定义。 *下推自动机的相关定义。 *下推自动机与上下无关语言的关系。 下推自动机和上下无关文法之间的互化。 （ 重点 ） *上下文无关语言与非上下文无关语言 上下文无关语言在并，连接和 Kleene运算下的封闭性，和它为什么 在补和交下不封闭。 但 上下文无关语言与正则语言在交下又是封闭的。 单文字的上下文无关语言必定是正则语言。 上下文无关语言的 泵定理 （ 重点 ）。 *关于上下文无关文法的算法 上下文无关文法－ 等价的下推自动机； 下推自动机－ 等价的上下文无关文法； 给定一上下文无关文法 G和一字符串 w,判定 wL(G). Chomsky 范式 ，将任一上下文无关文法化为等价的 Chomsky范式。 在 Chomsky范式基础上的动态规划算法以及其复杂度分析。 确定性与语法分析 下推自动机的确定型定义，字符串之间的相。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。