形式语言与自动机

DFA / NFA

1. e-NFA 转 NFA
2. NFA 转 DFA
3. 正则表达式 转 NFA
4. 泵引理 - 证明语言是 或者 不是正则语言。正则语言一定满足泵引理，不满足泵引理一定不是正则语言
   1. 相比于CFG 只需要分割成 xyz 3个部分
   2. 其中 | xy | <= N
   3. 讨论 y^k
5. 自动机的最小化 - 判断依据就 - 两个状态是否是一个拒绝，一个接受。或者两个状态能否分别推导出拒绝和接受。找到需要合并的状态之后，将他们划分为组/块，找到块于块之间的关系，然后重新绘制状态转移图。

CFG / PDA

1. 二义性和消歧义 - 二义性表示对于通过一个语言，同一个语法可以产生两个或者两个以上的Parse tree. 消歧义一般是直接重构语言。提供一个对于含有不同优先级的操作符的语法做消歧义的思路。

   1. 把不同优先级的操作符划分给不同的变量，一个变量只对应一个操作符
   2. 把两个操作符分成左递归和右递归
   3. 举例对于语法： S -> S + S | A ; A -> (S) | A * A | a，注意到会产生歧义的位置有两处，S -> S + S 和 A -> A * A。我们将他分别修改成左递归和右递归，并将除了自生变量的其他派生带入修改后的形式。所以就把他修改成 S -> S + A 和 A -> a * A | (S) * A。这样就完成了该语法的消歧义。

2. CFG的化简 - 得到一个适合机器读取的语法

   1. 总顺序是
      1. 消除 ε 产生式
      2. 消除 单元产生式
      3. 消除 非产生的 产生式
      4. 消除 非可达的 产生式
   2. 删除含有非“产生的”的变量的产生式，既无法推出terminal的变量。然后删除含有非“可达的”的变量的产生式，既无法从开始变量S推出的变量。需要严格保持这个顺序。
   3. 举例：S -> AB | a ; A -> b
      1. 先删除无法推出terminal的产生式 ，既S -> AB。此时剩余 S -> a ; A -> b
      2. 然后删除不可达的变量的产生式 ，既A -> b。此时剩余 S -> a。
      3. 结果为 S -> a
   4. 删除空产生式 - 既 A -> ε 。如果一个变量 A 可以通过某种途径推出 ε 则称这个变量是可空的(nullable)，或者说如果 A -> x 且 x 中的所有变量都是可空的，则 A 也是可空的。如果一个语法中全部的空产生式被删除，则得到语言 L - { ε }。存在部分可空变量的产生式，则将可空变量的部分依次尽可能替换为 ε 然后得到新式。注意需要写出不为 ε 的所有可能产生式情况。注意检查只含有terminal的形式不要漏掉。原产生式同样保留。
   5. 最后删除单元产生式 - 单元产生式是形如 A -> B 这样的式子。删除时删除 A-> B 然后将 B 的产生式复制给 A。产生式中的变量全部保留。B 的产生式也保留，仅删除 A ->B 本身。

3. CFG 转 CNF形式

   1. CNF形式 - 语法的产生式集合中只包含 { A -> BC ；A -> a }这样两种形式。

   2. 操作方法 (注意这个方法只适用于不带 ε 的语法，如果语法带 ε ，需要先化简。仅支持 S 带 ε )：

      1. 将 A -> abcBCDE… 中的所有 Terminal 换成 Ca, Cb… 并在 语法中加入 Ca -> a ; Cb -> b …
      2. 现在所有的产生式中都只剩下变量，将长度超过 2 的所有产生式依次替换成多个 长度为2 的产生式。比如 A -> BCDE 替换成 A -> BX ; X -> CY ; Y -> DE

4. CYK算法 - 把要求是否属于语法的字符串写在二维数组最底端，对于第一轮，如果有变量能直接派生某一位的字符，则将变量写在对应的[1] [字符位置] 。 然后从第二层开始的每一层的单元，表示能够产生 从当前列开始长度为层数的字符串 的变量。从数组的 左上到右下的斜对角线存入时，往右上继续 ; 最终的答案在 [1] [字符串长度]。

5. CFG 转 PDA - 使用PDA模拟CFG的最左派生，再加上弹出终结符的转移函数

6. PDA 转 CFG

   1. 定义PDA的转移函数是 δ (状态 p, 读入字符 a, 出栈字符串 A) -> (状态 q, 入栈字符串 B)
   2. 对于一个 PDA P = {状态集 Q, 输入字母表 Σ, 栈内符号集合 Γ，转移函数 δ, 起始状态 p0, 栈底字符 Z0, 接收状态 qf ∈ Q};
      1. 他对应的 CFG 的变量集合 V = {ApXq, 其中 p, q属于Q, X属于栈字符集 Γ}。
      2. 他对应的起始变量 S = Ap0Z0qf。 当 PDA 不以终态为接收条件，而以空栈为接收条件时，qf 表示一个到达空栈的字符串在PDA中最后停留的位置。
      3. 对于一个 转移函数 δ (p, a, A) -> (q, ε) 我们可以把它转化为 CFG 中的语法 ApAq -> a.
      4. 对于一个 转移函数 δ (p, a, A) -> (q, B) 我们先把B 拆分成 Y1Y2Y3Y4…Yk。其中每一个Yi都对应PDA中一条能从栈弹出Yi的转移函数。假设 Y1 由 q 到 p1 的转移函数弹出栈；Y2 由 p1 到 p2 的转移函数弹出栈 … Yk 由 pk-1 到 pk的转移函数弹出栈。那么我们就可以写出变量 ApAq 的生成式, 也就是 ApAq -> a AqY1p1 Ap1Y2p2 … Apk-1Ykpk
      5. 当我们处理了全部的转移函数时，就得到了 PDA 对应的 CFG
   3. ![[Pasted image 20250801222059.png|300]]

7. 泵引理 -

   1. 假设这个语言是CFL，则它应该符合泵引理。
   2. 找到语言的一个长度大于 N 的 字符串
   3. 把他分割为 uvwxy 5个部分，其中v和x不同时为空集。讨论可能的 v 和 x 的情况
   4. 证明对于所有的 v 和 x的划分情况，找出 一个i，对应到 v^i 和 x^i 使得 字符串不属于原语言