计算机理论基础（期中）

语言

• 字符集，字符串的集合
• 运算：集合运算，交并补加

自动机：读，转移

• 状态集，初始状态，接受状态，字符集，转换关系
• DFA，NFA，互化
• 并，连接，星运算的自动机构造
• 广义NFA

正则语言：=DFA，NFA，正则表达式

• 封闭性：并，连接，星，自动机证明
• 正则表达式：定义，与NFA的互化
• 非正则语言判定：泵引理

CFG——上下文无关语言

• 变元，规则，终结符，初始变元
• 推导：树，最左——上下文无关语言：封闭性质及其证明
• 乔姆斯基范式：范式转换
• 下推自动机PDA：
• • 状态集，输入字母表，栈字母表，转换关系，起始状态，接受集
  • ==上下文无关语言：CFG和PDA的互化
• 非上下文无关语言判定：泵引理

图灵机：左移右移，读写，状态转移

• 状态集，输入字母表，带字母表，转移关系，start，accept，reject
• 语言识别和设计
• 判定问题——集合——语言：设计图灵机判定：
  • A，R，RQ
  • 正则语言
  • CFG