图灵机 图灵机（Turing Machine, TM）的组成： 一个有限状态控制器 可以读取符号 可以写入符号 可以左移或右移指针 一条纸带，由有限个单格（cell）组成。可以从上面读写数据。单格可以为空。 形式定义： $$ M = (Q,T,\Sigma, \delta, q_0, B,F) $$ $Q$: 有限状态集合 $T$：有限输入符号集合 $T \subseteq \Sigma$ $\Sigma$：有限带符号集合 $\delta$：转移函数 $q_0$：起始状态 $B$：空白符 $B\in \Sigma - T$ $F$：终态集合 两个性质： 每个过程有穷可描述 过程由离散、可机械执行的步骤组成 转移函数： $$ \delta:Q\times \Sigma \to Q \times \Sigma \times \{L,R\} $$ 1function trans(presentState, currentSymbol){ 2 return [nextState, outputSymbol, movement] 3} 例如 $\delta(q,a_i)\to(p,B,L)$，表示现态为 $q$，指针读到 $a_i$，则次态为 $p$，写入空，左移指针。 瞬时描述：$w_1qw_2$，表示正在读 $w_2$ 的第一个符号。$w_1w_2$ 是整个纸带的内容。 一旦进入终止状态，则认为串接受，并停机。 图灵机的停机问题：给定图灵机，是否存在判别程序，能判断该机器对串能否接受。此问题不可判定（无通用解）。 边的格式：$i/o,D$，$i$ 时输入 $o$ 是输出，$D$ 是移动方向。

7.1 CFG 的范式 为了得到 CNF 的 CFG，我们需要做一些简化操作。 顺序如下： 消空生成式 消单生成式 消无用符号 7.1.1 消无用符号（非生成、不可达） 如果存在 $S \stackrel{*}{\Rightarrow } \alpha X \beta \stackrel{*}{\Rightarrow } w$ 形式的推导，则 X 是有用的，称X是有用符号。（ $w$ 属于 $T^*$ ）。否则是 无用符号。 设有终结串 $w$，若 $X \stackrel{*}{\Rightarrow } w$ ，则 $X$ 是有生成能力的（generaing），或称 X 是 生成符号。 设有终结串 $\alpha , \beta $，如果 $S \stackrel{*}{\Rightarrow } \alpha X \beta $，则 $X$ 是 可抵达的（reachable），或称 X 是可达符号。 有用符号就是既有生成能力，又可以抵达的符号。 无用产生式就是所有与无用符号有连接的乘积。例如 $S \to a + abB$ ，而 $B$ 是无用符号，则 $abB$ 是无用产生式。 Read more...

题型 区分文法 乔姆斯基把方法分成四种类型，即0型、1型、2型和3型。 0：无任何限制。 1：再限制每个 $\alpha \to \beta$，都有 $|\alpha|\geq|\beta|$（上下文有关） 2：再限制每个$\alpha \to \beta$，$\alpha$ 都是非终结符。（上下文无关） 3：再限制 $A \to \alpha | \alpha B$ （右线性），或者 $A \to \alpha | B \alpha$（左线性）。（线性文法） 4： 构造文法识别简单语言 简单有序数量关系型 【例】构造右线性文法识别 $L = \{a^{3n+1} | n \geq 0\}$ 区分左线性文法和右线性文法 右线性文法，非终结符在右边，例如 $S\to aB$，迭代之后字符串从右边展开。 分析： 我们可以写出符合规定的字符串。 $$ \begin{align} w_1 &= a\\ w_2 &= aaaa\\ w_3 &= aaaaaaa \end{align} $$ 可以观察到： $$ \begin{align} w_1 &= a\\ w_2 &= aaa w_1\\ w_3 &= aaa w_2 \end{align} $$ 易知 $w_i = aaaw_{i-1}$ 对于 $i>1$ 总是成立。故递推规则如下： Read more...

下推自动机能够对应 CFG。它是一个带有“栈”的 $\varepsilon-\text{NFA}$ 。 6.1 下推自动机的定义 6.1.1 通俗介绍 下推自动机与 $\varepsilon-\text{NFA}$ 类似，状态控制器可以在有限个状态之间转移（Finite Control）。但是它还有一个符号栈，可以推入（push）写入符号，或者弹出（pop）读取符号。栈的空间可以看作无限的。 6.1.2 形式定义 PDA 的定义如下： $$ M = (Q,T,\Gamma , \delta , q_0, z_0, F) $$ $Q$：有穷状态集。有限控制器的状态集合 $T$：有限输入字母表。 $\Gamma$：有限下推栈字母表。 $\delta$：转移函数。输入：当前状态，当前输入，当前栈顶。输出：新状态，栈顶替换的字符 $q_0$：初态， $q_0 \in Q$ $z_0$：下推栈的栈底最初符号，$z_0 \in \Gamma - T$ $F$：终态集合 如下图，当处于状态 q 时，输入一个字符 $a$ ，则将栈顶 $Z$ 替换为 $\beta_i$ 或者 $\beta _j$ 记作： $$ \begin{array}{l} \delta(q, a, Z)=\left\{\left(p_{1}, \beta_{1}\right),\left(p_{2}, \beta_{2}\right), \cdots,\left(p_{m}, \beta_{m}\right)\right\}, \quad \text { 或 } \\ \delta(q, \varepsilon, Z)=\left\{\left(p_{1}, \beta_{1}\right),\left(p_{2}, \beta_{2}\right), \cdots,\left(p_{m}, \beta_{m}\right)\right\} \end{array} $$ 例子：设计 PDA，识别 $L_{01} = \{0^n1^n | n \geq 1\}$ Read more...

5.1 上下文无关文法 5.1.1 回文语言 回文串就是正反一样的串，比如 abccba，010。我们无法用有限自动机、规则式来表达这种文法，但用生成式可以： $P \to \varepsilon $ $P \to 0$ $P \to 1$ $P \to 0P0$ $P \to 1P1$ 1~3 表明：回文串的构成包括： $\varepsilon $, $0$, $1$ 4~5 规定了回文串的生成规则 回文语言是一种典型的上下文无关语言。 5.1.2 上下文无关文法（CFG）的定义 定义： $T$ ：终结符（terminals） $N$，or $V$ ：变量（variables），也称非终结符（nonterminals） $S$ ：开始符号 $P$ ：产生式（productions），又叫规则（rules） 5.1.3 使用文法的推导 推导就是代入生成式的过程。 5.1.4 最左和最右推导 代入时总是替换最左边的变量，是最左推导（Leftmost derivation）。同理有最右推导 5.1.5 文法的语言 就是 CFG 所能推导出的所有终结串的集合。 5.1.6 句型 初始符号推出来的（不一定终结的）串，叫做句型（Sentential Forms）。通过最左推导产生的句型，是最左句型。同理有 最右句型。 5.2 语法分析树（Parse Tree） 语法分析树是推导的一种表示法。下图是 a*(a+b00) 的分析树： 5.3 文法与语言的歧义 5.3.1 歧义文法 若文法有两种推导，推出同一个句型，则称文法有歧义。 Read more...

4.1 泵引理 泵引理（pumping lemma）用于证明语言不是规则语言。它是一个重复不必要条件。 定理：$L$ 是规则语言。则存在 $n$ 满足：只要字符串 $w$ 的长度 $|w|\geq n$，就能将 $w$ 分为三段，$w = xyz$，使得： $y \ne \varepsilon$ $|xy|\leq n$ 对任意 $k \geq 0$，$xy^k z$ 属于 $L$ 我们可以通俗地理解：规则语言只能存放有限个状态，所以只要一个字符串足够长，肯定要耗尽所有状态，折回去使用已经用过的状态，从而，字符串的中间 $y$ 必可重复。 4.2 规则语言的封闭性 如果两个语言是规则的，则对二者执行特定运算之后得到的语言同样是规则的。 这些运算包括： 交并补差 反转、闭包(*)、连接 同态和逆同态 4.3 规则语言的判定性质 4.4 自动机的等价性和最小化 对于状态 $p,q$，如果对于任意输入串 $w$，$\hat{\delta}(p,w)$ 是接受状态和 $\hat{\delta}(q,w)$ 二者互为充要条件，说明 $p,q$ 状态等价。否则说 $p,q$ 状态可区分。 就是说，如果 $p,q$ 对于任意输入表现的行为完全一致（要么最终都接受，要么最终都不接受），那么 $p,q$ 等价。 4.4.1 填表算法 这是一种常见的递归算法，用于寻找 DFA 的可区分状态对。 例子： 有八个状态，可以形成 $7\times 8=56$ 个状态对。所以列表如下： 由于 C 是唯一的接受状态，所以涉及 C 的状态是可区分的： Read more...

3.1 规则式 规则式（RE，RegEx，Regular Expression，正则表达式）用于描述字符串的字符组织规则（也即语言）。例如 ：01*+10*，表示 0 开头，后面跟着任意个1；或者 1 开头，后面跟着任意多个 0. 如果有语言 L, M。则语言的并就是二者所能表示的串的集合的并。语言的连接是二者所能表示的串的连接的集合（“笛卡尔”连接，意会一下）。语言的闭包：语言自己和自己的任意次连接的集合。 例如 $L = \{0, 1\}$，则 L 的闭包 $L* = \{0,1\}*$ 是所有 0,1 构成的串，0, 00, 000, ..., 01, 10, 11, 100, 101 ...。 例如，所有 01 交替的串的规则式： $$ (01)* + (10)* + 0(10)* + 1(01)*\\ = (\varepsilon +1)(01)*(\varepsilon +0) $$ 3.2 DFA 和 RE 任何 DFA 都可以写成 RE 3.2.1 DFA 转 RE 例子：这个 DFA $A$，接受所有至少一个 0 的串。 假设状态 i 到 j 之间的路径可以用串 w 表示，串 w 的 RE 记作 $R_{ij}^(k)$，路径上没有大于 $k$ 的中间状态。 Read more...

2.1 确定有限自动机（Deterministic Finite Automata） 2.1.1 定义 一个 DFA 可以如此描述： 一个状态集合 $Q$ 一个输入符号集合 $T$ 一个转移函数 $d$。这个函数接受一个输入字符，返回一个新的状态。 一个初始状态 $q_0$ 一个终末状态集合 $F$ 下面 $q_F$ 表示 $F$ 中的元素。 2.1.2 处理串 如果一个输入序列（输入串）能够使得 DFA 从 $q_0$ 经过一系列状态转移到 $q_F$ ，则称 DFA 接受（Accept）此串。因此 $F$ 也称为接受状态。 DFA 所接受的所有串的集合称作 DFA的语言。 NFA 同理 2.1.3 DFA 的简记法 状态转移图： 状态转移表： $\rightarrow $ 表示初始状态。 $*$ 表示终末状态。 2.1.4 扩展转移函数（Extended T ransition F unction） 扩展转移函数把输入扩展到一个串，其实就是对各个输入，依次串行调用（依次在状态间跳转），返回值为 处理完这个串后到达的状态。 2.2 非确定有限自动机（Nondeterministic Finite Automata） NFA 能够同时处在几个状态。因此若是识别同样的语言，NFA 能够更加简练。 试看下面的 NFA： 对于 00101 输入，会产生不同的分支。例如输入 0 后，同时进入了 $q_0$ 和 $q_1$ 状态……最后，只要有一条路径能够通向 $q_F$，就认为此串被 NFA 接受了。 Read more...

自动机设计工具： [Graph / Finite State Machine Designer (markusfeng.com)](https://www.cs.unc.edu/~otternes/comp455/fsm_designer/) 模拟器： FSM Simulator (ivanzuzak.info) 1.1 为何学习自动机理论 1.2 形式证明介绍 1.2.1 演绎证明 介绍演绎推理的规则。 例如，证明：如果 $x$ 是四个正整数各自平方后求和，那么 $2^x > x^2$。 我们需要这样的命题序列： 已知：$x = a^2 + b^2 +c^2+d^2$ 已知：$a, b, c,d \geq 1$ 根据 2 和算数法则：$a^2, b^2,c^2,d^2\geq 1$ 根据 3 和算数法则：$x \geq 1+1+1+1 = 4$ 根据 命题 $x \geq 4 \to 2^x \geq x^2$ 和 4：$2^x > x^2$ 成立 1.2.2 还原定义 介绍一种证明的技巧，就是把描述还原为其定义 例如，证明：若 $S$ 是无穷集合 $U$ 的有穷子集，$T$ 是 $S$ 关于 $U$ 的补集，则 $T$ 是无穷的。 Read more...