作业题相关：
自反, 对称, 传递. 不满足传递性: R={(a,b)||a-b|≤1}; 不满足对称性: R={(a,b)|a≤b}; 不满足自反性: R={(a,b)|a≠1且b≠1}或者R={(a,b)|ab>0}
有穷自动机 $(Q, \Sigma, \delta, q_0, F)$. NFA 转换到 DFA: Q’=P(Q), 列出 NFA 中输入对每个状态的变化, 注意 $\varepsilon$ 与起始状态, 跟随输入符号之后处理 $\varepsilon$ 箭头. 例子:
DFA 转换到正则表达式. GNFA 新起始状态到原起始状态有个 $\varepsilon$ 箭头, 从原接受状态到新接受状态有个 $\varepsilon$ 箭头, 多个标记替换为 $\cup$, 没有箭头的状态添加 $\empty$. 例子:
1:
2:
正则泵引理 A 为正则语言，则存在 p（泵长度）使得若 s 为任意长度不小于 p 的字符串，则 s=xyz，满足：1) 对每个 i ≥ 0, $xy^iz\in A$; 2) |y| > 0; 3) |xy| ≤ p
$\{0^n1^n|n\geq0\}$ 不是正则语言: 设 $0^p1^p$, 但是由于 $xy^iz$, y 不可能只含 0/1 或者都有. $\{0^n1^n2^n|n\geq0\}$ 不是正则语言: 设 $0^p1^p2^p$, 如果 y 只含 0/1/2, 那么 xyyz 不含等量 0 1 2; 如果不止一种，那么次序不定
上下文无关文法 CFG (V, $\Sigma$, R, S) V 变量 $\Sigma$ 终结 R 规则 S 起始; 下推自动机 PDA (Q, $\Sigma$, $\Gamma$, $\delta$, $q_0$, F). 派生例子: E ⇒ T ⇒ F+b ⇒ a+b
乔姆斯基范式 (A→BC, A→a, 允许 S→ $\varepsilon$) 转换: 1) 添加 S0→S 2) 删除 $\varepsilon$ 规则, R→uAv 替换为 R→uv 3) 删除单一规则 A→B, 对 B→u 添加 A→u 4) 转换, A→u1u2…uk 替换为 A→u1A1, A1→u2A2, … 例子:
