1 形式化定义 图灵机(Turing Machine)：TM是一个七元组$P=(Q,\,\Sigma,\,\Gamma,\,\delta,\,q_0,B,\,F)$，其中， $Q$ 是有限的状态集； $\Sigma$ 是有限的输入字符集； $\Gamma$ 是有限的纸带字符集； $\delta$ 是状态转移函数，是一个映射 $Q\times \Gamma \Righta...
上下文无关文法和下推自动机
1 上下文无关文法 (CFG) 1 形式化定义 上下文无关文法 (Context-Free Grammars)：CFG是一个四元组，如：$G=(V,T,S,P)$，其中 $V$：变元的集合，是一个有限集；（变量） $T$：终结符的集合，是一个有限集，且 $V \cap T = \phi$；（值） $S$：开始变元，$S \in V$； $P$：产生式的集合，是一个有穷...
正则表达式 (Regular Expression)
1 正则表达式 正则表达式的递归定义： $\varepsilon$ 是一个正则表达式，表示语言 ${\varepsilon}$ ; $\phi$ 是一个正则表达式，表示空语言 $\phi$ ; $\forall a \in \Sigma$，$a$ 是一个正则表达式, 表示语言 ${a}$ ; 如果 $E$ 和 $F$ 是正则表达式，表示的语言分别是 $L(E)$ 和 $...
有穷自动机 (Finite Automata)
1 确定的有穷自动机 (DFA) 1 形式化定义 确定的有穷自动机 (Deterministic Finite Automata)：DFA是一个五元组，如：$M=(Q,\; \Sigma,\; \delta,\;q_0,\; F)$ ，其中， $Q$ 是有限的状态集，包含DFA中所有的状态； $\Sigma$ 是有限的输入字符集，也就是DFA的字母表； $q_0$ 是初始...