计算理论-CH00-学习目标

优先级	知识点	必须掌握	大阪大学常见考法	建议投入时间
⭐⭐⭐⭐⭐	计算理论-CH01-语言与字母表	✓	判断字符串是否属于语言	30 分钟
⭐⭐⭐⭐⭐	计算理论-CH02-自动机DFA	✓	状态转移、识别语言	2 小时
⭐⭐⭐⭐⭐	计算理论-CH03-自动机NFA	✓	多条路径、ε 转移	2 小时
⭐⭐⭐⭐⭐	计算理论-CH04-DFA与NFA等价	✓	NFA 转 DFA（Subset Construction）	2 小时
⭐⭐⭐⭐⭐	Regular Expression（正则表达式）	✓	自动机 ↔ 正则表达式 计算理论-CH02-自动机DFA	2 小时
⭐⭐⭐⭐☆	ε-closure	✓	NFA 转 DFA 必考步骤计算理论-CH04-DFA与NFA等价	1 小时
⭐⭐⭐⭐☆	Regular Language 闭包性质（并、连接、Kleene Star）	✓	构造新语言计算理论-CH05-正则表达式及其性质	1 小时
⭐⭐⭐⭐☆	计算理论-CH06-CFG上下文无关文法	✓	推导字符串、写产生式	3 小时
⭐⭐⭐⭐☆	Derivation（推导）与 Parse Tree（语法树）	✓	判断生成过程计算理论-CH06-CFG上下文无关文法	2 小时
⭐⭐⭐⭐☆	计算理论-CH09-PDA	✓	栈变化、识别括号匹配等	3 小时
⭐⭐⭐☆☆	CFG 与 PDA 对应关系	建议	根据 CFG 构造 PDA	2 小时
⭐⭐⭐☆☆	计算理论-CH07-CNF乔姆斯基范式	建议	化简文法	1 小时
⭐⭐⭐☆☆	计算理论-CH08-CYK-算法	建议	判断字符串是否属于 CFG	2 小时
⭐⭐☆☆☆	Mealy Machine	了解	个别年份出现	1 小时
⭐⭐☆☆☆	Moore Machine	了解	与 Mealy 比较	1 小时
⭐⭐☆☆☆	最小 DFA（Minimization）	了解	偶尔涉及	1 小时
⭐☆☆☆☆	Pumping Lemma	可不学	近几年未见重点	跳过
⭐☆☆☆☆	图灵机（Turing Machine）	可不学	基本未考	跳过
⭐☆☆☆☆	可判定性（Decidability）	可不学	基本未考	跳过
⭐☆☆☆☆	NP、NP-Complete	可不学	基本未考	跳过
⭐☆☆☆☆	Rice 定理等高级理论	可不学	跳过	跳过

Alphabet
    │
    ▼
Language
    │
    ▼
Regular Expression
    │
    ├─────────────┐
    ▼             ▼
   DFA  ⇄  NFA（ε-NFA）
    │
    ▼
Regular Language
────────────────────────
        │
        ▼
      CFG
        │
        ▼
 Parse Tree / Derivation
        │
        ▼
       PDA