复习重点
1、集合
序列
元组
函数
关系
图
串：字母表中符号的有穷序列
语言:是字符串的集合
2、DFA、NFA、NFA到DFA的转换，DFA、NFA的形式化五元组表达
3、正则表达式、正则表达式和NFA之间的转换、利用泵引理证明不是正则语言
字符串长度什么时候算0
4、上下文无关文法
下推自动机
乔姆斯基范式（基本概念）
CFG到下推自动机的转换
从右至左压入栈中
5、利用泵引理证明不是上下文无关语言
6、图灵机、
图灵可识别语言：接受、拒绝、循环
判定器：对所有输入都停机的图灵机，永不循环。
图灵可判定语言：能让图灵机停机的语言，接受或者拒绝
要求可以做简单的判定性证明（例如：ADFA、ACFG、HALT-TM、ETM）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。