《形式语言期末复习提纲.doc》由会员分享，可在线阅读，更多相关《形式语言期末复习提纲.doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流形式语言期末复习提纲【精品文档】第 4 页第一章：绪论语言与形式语言字母表（正闭包、克林闭包）句子（前缀、后缀、公共子串、并置）语言第二章：文法文法的提出文法的形式定义文法的推导与归约句子与句型常用文法的构造文法的乔姆斯基体系短语结构文法上下文有关文法上下文无关文法正则文法有穷状态自动机语言的识别问题有穷状态自动机的物理模型有穷状态自动的形式定义状态转移图状态的set集合DFANFANFA转换为DFA的方法-NFA-NFA转换为NFA的方法构造与DFA等价的文法构造与文法等价的NFA正则表达式正则表达式的形式定义正则表达式转换为FA的方法将DFA转换为正
2、则表达式的方法正则语言等价模型及其转换正则语言的性质正则语言的泵引理应用泵引理证明一个语言不是RL正则语言在各种预算下的封闭性DFA的极小化方法上下文无关语言CFGCFG派生树二义性CFG的简化去无用符号去空产生式去单一产生式乔姆斯基范式（CNF）形式定义将CFG转换为CNF格雷巴赫范式（GNF）形式定义下推自动机下推自动机PDA的物理模型下推自动及的形式定义PDA两种接受语言的方式构造与CFG等价的PDA的方法构造与PDA等价的CFG的方法其他上下文无关语言的泵引理上下文无关语言的封闭性图灵机的物理模型图灵机的形式定义图灵机与短语结构语言等价线性有界自动机形式定义线性有界自动机与上下文有关文法等价