速通 形式语言与自动机

有啥要学的？

DFA/NFA 的记号：\((Q,\Sigma,\delta,q_0,F)\)。

NFA 到 DFA：子集构造（到 \(2^n\) 级别的构造：所有最后第 \(n\) 位为 \(1\) 的 01 串）。

\(\varepsilon-\)NFA 到 DFA：类似地进行子集构造，每次转移时考虑对应 \(\varepsilon-\)闭包。

文本搜索：trie 树（记得加上根到自身的 \(\Sigma\) 自环，因为是匹配部分文本），转 DFA 即 AC 自动机。

闭包有限的集合：\(\phi,\varepsilon\)。

DFA 到正则表达式：

• 路径迭代法：\(R_{i,j}^{(k)}\) 表示编号 \(\leqslant k\) 的路径对应的正则表达式。求法：从小到大枚举 \(k\)，每次令 \(R_{i,j}^{(k)}=R_{i,j}^{(k-1)}+R_{i,k}^{(k-1)}(R_{k,k}^{(k-1)})^*R_{k,j}^{(k-1)}\)。
• 消除状态法：每次选择一个点缩（记得自环）。

检验正则表达式是否为真：代入不同字母。

正则表达式到 \(\varepsilon-\)NFA：懂得抖动。

正则语言的泵引理：存在常数 \(n\) 使得对于 \(|w|\geqslant n\)，我们能将其分为 \(w=xyz\) 使得 \(y\ne \varepsilon,|xy|\leqslant n\)，且 \(\forall k\geqslant0,xy^kz\in L\)。

同态：将每个字符替换成字符串；逆同态：将每个字符替换成字符串后在给定语言里。

DFA 最小化 / DFA 等价判定：填表算法，不断通过 \(\hat\delta(p,w)\ne\hat\delta(q,w)\) 否定两个状态等价。

CFG：\((V,T,P,S)\)，变元集合，终结符集合，产生式集合，初始符号。

最左推导：每次替换最左侧变元。

递归推理：将某个字符串根据其所在非终结符形式阶段，递归各个子串检查。

语法分析树。

存在上下文无关语言使得任意描述其文法都是二义的：\(\{a^nb^mc^md^n\}\cup\{a^nb^nc^md^m\}\)。

可用最左推导不唯一证明文法的二义性。

PDA：\((Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)\)，状态集合，输入符号集合，堆栈字母表，转移函数 \(\delta(q,a,X)=\{(p,\varepsilon/X/YZ)\}\)，初始状态，初始符号，接受状态集合。

PDA 的瞬时描述：\((q,w,\gamma)\)（栈顶靠左）。

对于 \((q,x,\alpha)\vdash^*(q,y,\beta)\)，那么有 \((q,xw,\alpha\gamma)\vdash^*(p,yw,\beta\gamma)\)。

PDA 的接受方式：终结状态与空栈方式（此时 PDA 描述只有六项）。

• 空栈方式到终结状态：定义新的符号放置栈底表示栈空；
• 终结状态到空栈方式：终结状态连向一个弹栈状态。

上下文无关文法到空栈 PDA：尝试模拟文法的最左推导，用栈从上往下记录需要展开的非终结符/需要消去的终结符。

空栈 PDA 到上下文无关文法：定义符号 \([pXq]\) 表示从 \(p\) 走到 \(q\)，弹去了一个 \(X\)。接下来将转移边变化为：

• 起始状态：\(S\rightarrow[q_0Z_0q]\)，其中 \(q\) 为任意状态；
• \((p,\varepsilon)\in \delta(q,a,X)\)：\([qXp]\rightarrow a\)；
• \((p,X)\in\delta(q,a,X)\)：\([qXq_1]\rightarrow a[pXq_1]\)；
• \((p,Y_1Y_2\cdots Y_mZ)\in\delta(q,a,x)\)：\([qXq_m]\rightarrow a[pY_1q_1][q_1Y_2q_2]\cdots[q_{m-1}Y_mq_m]\)。

DPDA：要求转移边确定。

前缀性质：不存在两个接受串为前缀关系。

语言 \(L\) 能被某个 DPDA 空栈接受当且仅当其有前缀性质且存在 DPDA 以终结状态接受其。

DPDA 以空栈接受/终结状态接受的语言均无歧义。前者显然，后者我们将语言中添加未出现的“结束标记”，那么语言有前缀性质，存在 DPDA 空栈接受其，将该空栈 DPDA 的文法改写为原语言的文法即可，只需添加结束标记 \(\rightarrow\varepsilon\) 的转移。

范式：去除无用符号（非产生，不可达），去除 \(\varepsilon\) 产生式（\(A\rightarrow\epsilon\)），去除单位产生式（\(A\rightarrow B\)）。

• 寻找产生符号：从终结符开始往前拓扑排序，每次检查非终结符产生的符号是否均可产生；
• 寻找可达符号：从初始符号开始向后 bfs；
• 去除 \(\varepsilon\) 产生式：从 \(\varepsilon\) 往前拓扑排序，并将可空符号对应推导修改（注意这一步会让文法无法生成 \(\varepsilon\)）；
• 去除单位产生式：搜索出所有单位对（可用一系列单位产生式生成的）\((A,B)\)，并在新的语言中直接构建 \(A\) 到 \(B\) 非单位产生式的推导。

乔姆斯基范式（CNF）：多叉转二叉，即任意产生式都能写为 \(A\rightarrow AB\) 或 \(A\rightarrow a\)。

上下文无关语言的泵引理：存在常数 \(n\) 使得对于 \(|z|\geqslant n\)，我们能将其分为 \(w=uvwxy\) 使得 \(|vwx|\ne\varepsilon\) 且 \(\forall k\geqslant 0,uv^kwx^ky\in L\)。

上下文无关语言与正则语言的交仍是上下文无关语言（构造考虑同时模拟 PDA 与 DFA），但与上下文无关语言的交并不一定，如 \(\{0^n1^n2^i\}\cap\{0^i1^n2^n\}\)。

上下文无关语言的逆同态仍是上下文无关语言：Page 203，先鸽了。

CFL 空性测试：拓扑排序。

CFL 成员性测试（CYK 算法）：区间 dp，dp 值记录集合。

判定 CFG 是否歧义，判定 CFL 是否故有歧义，判定两个 CFL 交为空，判断两个 CFL 相同，判断某个 CFL 是否等于 \(\Sigma^*\)，这些问题都是不可判定的。

图灵机：\((Q,\Sigma,\Gamma,\delta,q_0,B,F)\)：状态集合，输入符号集合，带符号集合（且 \(\Sigma\subseteq\Gamma\)），转移函数，初始状态，空格符号，接受状态集合。

图灵机的瞬时描述：\(X_1X_2\cdots X_{i-1}qX_{i}X_{i+1}\cdots X_n\)，\(X\) 一般是最靠左/最靠右非空格位置中间的部分，若带头在这一区域外，则我们会将空格纳入描述。

图灵机的停机接受（即转移函数无定义）。

图灵机的“多道”只需将状态记录为 \(n\) 元 tuple。

非确定性图灵机不比确定性图灵机强。

半无穷带，不写空格图灵机不比图灵机弱（考虑双带构造）。

双堆栈 PDA 比图灵机强。

单计数器比 DPDA 强，双计数器比图灵机强（先用三计数器构造，再换为双计数器）。