首页 医学英语 考博全规划 特惠课程 历年真题

新东方在线 > 考博 > 考博复习资料 > 正文
医学英语全程班优惠 考博英语全程班特惠

南京理工大学博士研究生招生 形式语言与自动机考试大纲

2015-03-16 16:15:13来源：网络

南京理工大学博士研究生招生 形式语言与自动机考试大纲

　　1 计算机理论导引

　　1.1 三个基本概念

　　1.1.1 D语言

　　1.1.2 D文法

　　1.1.3 自动机

　　1.2 一些应用

　　2 有穷自动机

　　2.1 确定型有穷自动机

　　2.2 非确定型有穷自动机

　　2.3 D确定型有穷自动机与非确定型有穷自动机的等价性

　　2.4 有穷自动机的化简

　　3 正则语言和正则文法

　　3.1 D正则表达式

　　3.2正则表达式与正则语言间的联系

　　3.3 D正则文法

　　4 正则语言的性质

　　4.1 正则语言的封闭性

　　4.1.1 简单集合运算的封闭性

　　4.1.2 其它运算的封闭性

　　4.2 正则语言的基本问题

　　4.3 识别非正则语言

　　4.3.1 D使用鸽巢原理

　　4.3.2 D泵引理

　　5 上下文无关语言

　　5.1 上下文无关文法

　　5.1.1 D最左推导和最右推导

　　5.1.2 D推导树

　　5.1.3 句型与推导树的关系

　　5.2 分析与二义性

　　5.3 上下文无关文法和程序设计语言

　　6 上下文无关文法的化简与范式

　　6.1 文法变换方法

　　6.1.1 删除无用产生式

　　6.1.2 消除l产生式

　　6.1.3 消除单一产生式

　　6.2 两个重要的范式

　　6.2.1 D乔姆斯基范式

　　6.2.2 格里巴克范式

　　7 下推自动机

　　7.1 非确定型下推自动机

　　7.1.1 下推自动机的定义

　　7.1.2 D下推自动机接受的语言

　　7.2 下推自动机与上下文无关语言

　　7.2.1 上下文无关语言相应的下推自动机

　　7.2.2 下推自动机相应的上下文无关语言

　　7.3 确定型下推自动机和确定型上下文无关语言

　　8 上下文无关文法的性质

　　8.1 D泵引理

　　8.2 上下文无关语言的封闭性和判定算法

　　8.2.1 上下文无关语言的封闭性

　　8.2.2 D上下文无关语言的可判定性质

　　9 图灵机

　　9.1 标准图灵机

　　9.1.1 D图灵机的定义

　　9.1.2 D作为语言接受器的图灵机

　　9.1.3 作为转换器的图灵机

　　9.2 完成复杂任务的组合图灵机

　　9.3 图灵论题

　　10 算法计算的限制

　　10.1 图灵机所不能解决的问题

　　10.1.1D 可计算性和可判定性

　　10.1.2 图灵机停机问题

　　10.1.3 将一个不可判定问题简化成另一个问题

　　10.2 递归可枚举语言的不可判定问题

　　10.3 上下文无关语言的不可判定问题

　　10.3 D图灵机与复杂性

　　10.4 语言族和复杂性类

　　10.5 复杂性类P和NP

　　主要参考教材：蒋宗礼 姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003.1

2023考博精品好课，点击图片查看介绍！

本文关键字: 南京理工大学 博士 博士研究生

关注新东方在线服务号

回复【考博真题】领取备考必看真题集

更多资料

关注新东方在线服务号

关注新东方在线服务号，
免费获取考博必看干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.点击【关注公众号】，回复对应关键字领取学习资料。
更多>>
更多内容
更多>>
更多好课>>
更多>>
更多资料
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

京ICP证050421号 京ICP备05067669号-2 京公网安备11010802017616号 网络视听许可证0110531号 京网文(2016)1303-163号

Copyright © 2011-2018 新东方教育科技集团有限公司, All Rights Reserved

违法和不良信息举报电话: 010-81401500 举报邮箱: sec@xdfzx.com 网上有害信息举报专区