形式语言期末复习提纲

《形式语言期末复习提纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章：绪论语言与形式语言字母表（正闭包、克林闭包）句子（前缀、后缀、公共子串、并置）语言第二章：文法文法的提出文法的形式定义文法的推导与归约句子与句型常用文法的构造文法的乔姆斯基体系短语结构文法上下文有关文法上下文无关文法正则文法有穷状态自动机语言的识别问题有穷状态自动机的物理模型有穷状态自动的形式定义状态转移图状态的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的方法其他上下文无关语言的泵引理上下文无关语言的封闭性图灵机的物理模型图灵机的形式定义图灵机与短语结构语言等价线性有界自动机形式定

3、义线性有界自动机与上下文有关文法等价