计算机理论基础（期中）

语言

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

自动机：读，转移

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

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

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

CFG——上下文无关语言

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

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

  • 状态集，输入字母表，带字母表，转移关系，start，accept，reject
  • 语言识别和设计
  • 判定问题——集合——语言：设计图灵机判定：
    • A，R，RQ
    • 正则语言
    • CFG
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容