知识结构，都是很基础的东西，可以查漏补缺

T1-3 DFA/NFA/正则表达式 设计

• 多练习设计
  一个小小的总结：
  

T4 正则语言泵引理

如果语言 L 是正则的, 那么存在正整数 N, 它 只依赖于 L, 对$∀w∈L$∀w∈L, 只要|$w|≥N$w∣≥N, 就可以将 $w$w，分为三部分 $w=xyz$w=xyz 满足：

• 1. $y≠ε (|y|>0)$y​=ε(∣y∣>0)
• 2. $|xy|≤N$∣xy∣≤N
• 3. $∀k≥0, xy^kz∈L.$∀k≥0,xykz∈L.

T5&T6：

DFA转NFA

比较简单

NFA转DFA

子集构造法：

从开始状态{$q_0$q0​}开始，构造子集，并对产生的集合继续构造，知道无法产生出新的集合，然后用转移函数画DFA即可

DFA转移正则语言

状态消除法

正则语言转换NFA

比较简单，将正则语言拆开，利用空转移增加开始和结束节点即可

DFA 最小化

使用填表算法
递归寻找 DFA 中全部的可区分状态对:

1. 如果 $p∈F$p∈F 而 $q∉F$q∈/​F, 则 [p,q] 是可区分的;
2. ∃a∈Σ , 如果 [r= $δ$δ(p,a) , s=$δ$δ(q,a)]

是可区分的 , 则 [p,q] 是可区分的

• 1.直接标记终态和非终态之间的状态对
• 2.标记所有经过字符 0 到达终态和非终态的状态对
• 3.标记所有经过字符 1 到达终态和非终态的状态对
• 4.此时对于未标记的状态对, 只需逐个检查，确定是否经过很短的字符串后, 都会到达相同状态，如果是，则是等价的，否则是可区分的

案例：

封闭性证明题

PS：集合运算英语词汇表

并集：union
交集：intersection
补集：complement
差集：difference
反转：reversal
闭包：closure
连接：concatenation
同态：homomorphism
逆同态：inverse homomorphism
代换：substitute

T7 文法设计，转换，化简

CFG的设计

需要练习

CFG的化简

1. 消除 ε-产生式，首先 确定“可空变元”（能产生ε的变元），然后替换带有可空变元的产生式（替换后结果不能全为空）
2. 消除单元产生式，先确定“单元对” $A→B∈P$A→B∈P, 则 [A,B] 是单元对; 然后消除单元产生式， 删除全部形为 $A→B$A→B 的单元产生式;并将 B 的产生式添加到 A的产生式中。
3. 删除全部含有 ‘‘非产生的’’ 符号的产生式：如果 A→$α$α∈P 且 $α$α中符号都是产生的, 则 A 是产生的，否则A变不是产生的
4. 删除全部含有 ‘‘非可达的’’ 符号的产生式：如果从S出发不能到达A，那么A是非产生的

CNF文法转化

CFG转PDA

相对 PDA转CFG来说要简单，注意转换到的PDA都是空栈方式接受的

案例：

总结一下：产生空栈接受的PDA ，其中瞬时描述都为:

$(ε,每条产生式的左端变元/每条产生式的右端)$(ε,每条产生式的左端变元/每条产生式的右端)和 $(0,0/ε)$(0,0/ε)和$(1,1/ε)$(1,1/ε)

GNF转PDA

GNF的产生式都是 $S->aα$S−>aα的，其中a是终结符，α是由0个到n个的语法变元

总结一下规律，就是把之前的空转移换成GNF固定格式中的终结符，而右边的便是产生式的左端和产生的α（由0个到n个的语法变元组成）
总结一下，产生空栈接受的PDA，瞬时描述都为:

$(GNF产生式中的终结符,GNF产生式的左端变元/GNF产生式右端中的α)$(GNF产生式中的终结符,GNF产生式的左端变元/GNF产生式右端中的α)

PDA转CFG

这个比较复杂，但是仍有规律可循


看起来过程十分复杂，但是慢慢理解一下：利用PDA构造CFG，将CFG中每个文法变元视作为PDA的栈符号（因为都是中间产物），但是对于同一个栈符号，如果处于不同的状态，不能将其视作同一类，因此我们在前后加上之前之后的状态；例如对$qXp$qXp，在PDA中表示的意义是从状态q弹出栈符号X到底状态p，然后我们便可以将栈符号转换为语法变元，从栈中一个个地弹出栈符号，会在输入带上一部分一部分消耗输入串，我们可以看成抵消的作用：即为了完全的弹出栈符号，需要消耗掉一部分输入串。
如果看不懂上面说的这些的话，不妨拿来主义地找点规律吧



可能画的比较乱，慢慢看就行

T8 PDA设计

同样需要练习

T9 PDA 文法，转换，证明

泵引理：

封闭性：

特殊的一点：代换：
两个字母表 Σ 到 Γ 的函数 $s:Σ→2Γ^∗$s:Σ→2Γ∗ 称为代换 ($substitution$substitution). Σ 中的一个字符 a 在映射$s$s 的 作用下为 Γ 上的一个语言 $L_a$La​, 即
$s(a)=L_a$s(a)=La​
扩展 s 的定义到字符串,

$s(ε)=$s(ε)= {ε}

$s(xa)$s(xa)$=$=$s(x)$s(x)$s(a)$s(a)

再扩展 s 到语言, 对$∀L⊆Σ^∗$∀L⊆Σ∗,

之前提到的同态是把一个字符映射成另一个字符或字符串，而代换是把一个字符映射成一个语言

T10 图灵机设计 语言识别器 函数构造器

多练习构造
语言识别器：

函数构造器