企业官网建设流程全解析

1. 为什么第五章的课后题总让人卡壳

形式语言与自动机这门课，前四章还能靠直觉和画图硬扛，到了第五章，绝大多数人都会经历一次认知上的“断崖”。这一章通常围绕上下文无关文法（CFG）、下推自动机（PDA）、文法化简与范式展开，题目从“给文法求语言”到“构造PDA”“消除左递归”“转Chomsky范式”，每一步都在考验你对“推导”这件事的理解深度。我见过太多同学，前四章作业接近满分，第五章直接卡到怀疑人生——不是不努力，是这一章的思维方式变了。

先说清楚这篇内容能给你什么。它不是简单地把答案抄一遍，而是把第五章课后题里最常出现的几类题型拆开，告诉你每道题背后的判定逻辑、构造思路和验证方法。适合正在学这门课、被课后题折磨的学生，也适合准备考试需要快速梳理题型的人。我会尽量用“人话”解释那些教材里写得云里雾里的定义，同时把每类题的标准解法流程和容易翻车的地方都标出来。

这一章的核心矛盾在于：文法是人写的，自动机是机器跑的，而题目要求你在两者之间来回翻译。给一个文法，你要能说出它生成什么语言；给一个语言描述，你要能写出文法；给一个文法，你要能构造出等价的PDA；给一个PDA，你又要能反推出文法。这种双向翻译能力，靠背答案没用，必须理解每一步“为什么可以这样转”。

我自己的经验是，第五章的课后题可以归为六大类：推导与语言识别、文法设计、文法化简（消除无用符号、ε产生式、单位产生式）、消除左递归、Chomsky范式与Greibach范式转换、PDA构造与等价性证明。下面我按这个分类，把每类题的解法逻辑和实操细节讲透。

2. 推导与语言识别：从文法反推语言的系统方法

2.1 先判断文法类型，再决定推导策略

拿到一道“求此文法生成的语言”的题，第一步不是急着推导，而是先看产生式长什么样。如果所有产生式都是 A → α 的形式，左边单一非终结符，右边任意串，那就是上下文无关文法。如果右边还依赖左边符号的上下文，那就是上下文有关，但第五章基本不涉及。确认是CFG之后，再看有没有ε产生式、单位产生式、左递归，这些特征直接决定你后面要不要先化简。

我习惯的做法是：先把文法的非终结符和终结符列出来，然后从开始符号出发，尝试生成几个最短的串。比如文法 S → aSb | ε，你生成几个串就会发现是 a^n b^n。但有些文法没那么直观，比如 S → aS | bS | a | b，这个生成的是所有以a或b结尾的非空串，其实就是 (a|b)* 去掉空串。推导几个短串之后，你就能感觉到模式。

注意：不要一上来就试图写出精确的集合表达式。先用具体串试探，找到规律后再形式化。很多同学卡住是因为想直接“看出来”，但人的直觉在复杂文法面前不可靠。

2.2 用推导树验证你的猜测

当你猜测语言是某个集合后，必须用推导树反向验证。具体做法是：从你猜测的语言中取几个有代表性的串，看能否从开始符号推导出来；再从文法能生成的串中取几个，看是否都在你猜测的集合里。这个双向验证能排除大部分错误。

举个例子，文法：

S → aB | bA A → a | aS | bAA B → b | bS | aBB

这个文法生成的是a和b数量相等的串。怎么验证？你推导几个串：ab、ba、aabb、abab、bbaa，发现a和b的数量始终相等。再想，能不能生成aab？不能，因为a比b多。能不能生成abb？不能，b比a多。所以猜测成立。这种题在课后题里非常典型，教材通常用它来引出“文法可以生成非正则语言”的概念。

2.3 处理含ε和单位产生式的文法

如果文法里有ε产生式，比如 A → ε，求语言时要特别小心。ε本身可能属于语言，也可能只是推导过程中的中间步骤。判断方法是：看开始符号能否经过若干步推导出ε。如果能，ε就在语言里；如果不能，ε就不在。

单位产生式 A → B 也很讨厌，它会让推导步骤变多但不增加串长。求语言时可以先忽略单位产生式，因为它们不改变最终生成的串，只改变推导路径。但如果你要构造等价PDA，单位产生式就必须先消除。

我踩过的一个坑是：有些文法里ε产生式只出现在非开始符号上，但通过单位产生式链，开始符号最终也能推出ε。比如 S → A, A → ε，这时候ε属于语言。很多同学只看开始符号有没有直接ε产生式，漏掉了这种间接情况。

3. 文法设计题：从语言描述到产生式的构造套路

3.1 先分解语言结构，再逐层写产生式

文法设计题通常给一个语言描述，比如“所有a和b数量相等的串”“所有回文串”“所有不含连续两个a的串”，要求你写出CFG。这类题的通用思路是：把语言的结构分解成几个部分，每个部分用一个非终结符表示，然后用产生式把它们组合起来。

以“所有a和b数量相等的串”为例。这个语言可以这样想：一个这样的串，要么是ε，要么可以写成 aXb 或 bXa 的形式，其中X也是a和b数量相等的串。所以文法就是：

S → ε | aSb | bSa

这个文法简洁且正确。但有些同学会写成 S → aSb | bSa | ε，其实是一样的。关键是理解“a和b数量相等”这个条件可以通过“在某个位置加一个a和一个b”来递归构造。

再比如“所有回文串”，字母表是{a,b}。回文串的结构是：ε、a、b、aPa、bPb，其中P是回文串。所以：

S → ε | a | b | aSa | bSb

这个文法生成所有回文串。注意这里a和b单独列出来是因为长度为1的回文串不能写成aSa的形式（那会变成长度3）。

3.2 用非终结符“记住”约束条件

有些语言的约束不是对称的，比如“a的数量是b的两倍”“a在b前面”“不含连续两个a”。这时候你需要用非终结符来“记住”当前的状态。比如“不含连续两个a”的串，可以这样设计：

S → ε | bS | aT T → ε | bS

这里S表示“当前没有刚输出a”，T表示“刚输出了一个a”。从T只能接b或者结束，不能接a，这样就避免了连续两个a。这种“状态记忆”的思路和自动机的状态设计是一脉相承的。

提示：文法设计题没有唯一答案，但好的答案通常产生式少、结构清晰。如果你写出来的文法有十几个产生式，大概率可以化简。先保证正确，再考虑简洁。

3.3 验证文法是否“恰好”生成目标语言

写完文法后，必须验证两件事：生成的串都在目标语言里（不超集），目标语言里的串都能生成（不子集）。超集的问题通常出在产生式太宽松，比如不小心允许了不该有的组合；子集的问题通常出在产生式太严格，漏掉了某些情况。

验证子集时，可以用归纳法：假设目标语言中长度为n的串都能生成，证明长度为n+1的串也能生成。验证超集时，可以对推导步数做归纳：假设k步推导出的串都在目标语言里，证明k+1步推导出的串也在。这个过程在课后题里经常要求写出，虽然繁琐但能帮你彻底理解文法。

我自己的习惯是，写完文法后至少手动推导5个目标语言中的串和5个不在目标语言中的串，看能否生成。这个“抽样测试”能发现大部分错误。

4. 文法化简：消除无用符号、ε产生式和单位产生式

4.1 消除无用符号：先找生成符号，再找可达符号

无用符号分两种：不能生成任何终结符串的符号（生成无用），和从开始符号不可达的符号（可达无用）。消除顺序很重要：先消除生成无用符号，再消除可达无用符号。反过来做会漏掉一些符号。

具体步骤：

1. 找出所有能生成终结符串的非终结符。初始时，所有右边全是终结符的产生式左边的非终结符入选。然后迭代：如果某个产生式右边全是终结符或已入选的非终结符，左边的非终结符也入选。直到集合不再增大。
2. 删除所有不在这个集合中的非终结符及其相关产生式。
3. 从开始符号出发，找出所有可达的非终结符。迭代：开始符号可达；如果A可达且A→α，则α中的所有非终结符可达。
4. 删除所有不可达的非终结符及其相关产生式。

举个例子：

S → aA | bB A → aA | a B → bB C → c

先找生成符号：A能生成a（A→a），所以A入选；S能生成aA，A入选，所以S入选。B只能生成bB，永远生成不了终结符串，所以B是生成无用。C能生成c，但C从S不可达，所以C是可达无用。最终化简后只剩S → aA, A → aA | a。

注意：消除无用符号后，文法生成的语言不变，但产生式数量减少。考试时如果题目要求“化简文法”，通常需要同时消除无用符号、ε产生式和单位产生式，顺序是：先消除ε产生式，再消除单位产生式，最后消除无用符号。这个顺序不能乱，因为消除ε和单位产生式可能会产生新的无用符号。

4.2 消除ε产生式：找出所有可空非终结符

ε产生式就是形如 A → ε 的产生式。消除方法是：找出所有可空非终结符（能推导出ε的非终结符），然后对于每个产生式，如果右边包含可空非终结符，就生成所有可能的“去掉这些可空符号”的新产生式。

具体步骤：

1. 找出所有可空非终结符。初始时，有A→ε的产生式的A入选。迭代：如果某个产生式右边全是可空非终结符，左边的非终结符也入选。
2. 对于每个产生式 A → X1X2...Xn，生成所有形式为 A → Y1Y2...Yn 的产生式，其中如果Xi可空，Yi可以是Xi或ε（即删掉Xi）；如果Xi不可空，Yi只能是Xi。但要注意，不能生成右边全为空的新产生式（即A→ε本身要删掉，除非A是开始符号且ε在语言中）。
3. 删除所有ε产生式，但如果开始符号可空且ε在语言中，保留S→ε或增加新的开始符号S'→S|ε。

举个例子：

S → aSb | ε

可空非终结符只有S。对于S→aSb，S可空，所以生成S→ab（删掉中间的S）和S→aSb（保留）。对于S→ε，删掉。最终：

S → aSb | ab | ε

但注意，如果ε在语言中（这里是的），保留S→ε。所以最终是 S → aSb | ab | ε。这个文法生成a^n b^n，n≥0，和原来等价。

4.3 消除单位产生式：用闭包替换

单位产生式是形如 A → B 的产生式，其中A和B都是非终结符。消除方法是：对于每个非终结符A，找出所有A能通过单位产生式链到达的非终结符集合（包括A自己），然后对于集合中每个非终结符B，把B的所有非单位产生式复制给A。

具体步骤：

1. 对于每个非终结符A，计算单位闭包：A能通过若干单位产生式到达的所有非终结符。
2. 对于闭包中的每个B，把B的所有非单位产生式（右边长度≥2或右边是终结符）添加到A的产生式中。
3. 删除所有单位产生式。

举个例子：

S → A | a A → B | b B → c

S的单位闭包是{S, A, B}。A的单位闭包是{A, B}。B的单位闭包是{B}。所以S的产生式加上A的非单位产生式（A→b）和B的非单位产生式（B→c），得到S → a | b | c。A的产生式加上B的非单位产生式，得到A → b | c。B不变。最终：

S → a | b | c A → b | c B → c

单位产生式全部消除。

提示：消除单位产生式后，文法可能变得“冗余”，但语言不变。如果题目只要求消除单位产生式，不需要再化简。如果要求“化简到最简”，继续消除无用符号。

5. 消除左递归：直接左递归和间接左递归的处理

5.1 直接左递归：用新非终结符改写

直接左递归是形如 A → Aα | β 的产生式。消除方法是引入新非终结符A'，改写为：

A → βA' A' → αA' | ε

这个改写保持语言不变。原理是：原来A生成的是β后面跟任意多个α，即βα*。改写后A生成βA'，A'生成α*，效果一样。

举个例子：

E → E + T | T T → T * F | F F → (E) | id

消除E的直接左递归：

E → T E' E' → + T E' | ε

消除T的直接左递归：

T → F T' T' → * F T' | ε

最终文法：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id

这个文法就是经典的算术表达式文法，没有左递归，可以直接用于递归下降分析。

5.2 间接左递归：先代入再消除

间接左递归是形如 A → Bα, B → Aβ 的情况。处理方法是：先通过代入把间接左递归变成直接左递归，再消除。

具体步骤：

1. 把非终结符排个序：A1, A2, ..., An。
2. 对于每个i从1到n，对于每个j从1到i-1，把Aj的产生式代入Ai的产生式中（即如果Ai → Ajγ，就把Aj的所有产生式替换进去）。
3. 消除Ai的直接左递归。
4. 最后消除无用符号。

举个例子：

S → Aa | b A → Ac | Sd | ε

排序：S, A。对于A，j=1（S），把S的产生式代入A → Sd，得到A → Aad | bd | Ac | ε。现在A有直接左递归（A → Aad | Ac），消除：

A → bdA' | A' A' → adA' | cA' | ε

S不变。最终文法：

S → Aa | b A → bdA' | A' A' → adA' | cA' | ε

注意这里A → A'是单位产生式，可以进一步消除，但题目如果只要求消除左递归，到这里就可以了。

注意：间接左递归的消除顺序会影响最终文法的形式，但语言不变。考试时按教材的排序方法做即可。我见过有些同学排序不同导致结果不同，只要语言等价就是对的。

6. Chomsky范式与Greibach范式：转换步骤与常见错误

6.1 Chomsky范式：所有产生式都是 A → BC 或 A → a

Chomsky范式（CNF）要求所有产生式形如 A → BC（B,C是非终结符）或 A → a（a是终结符）。转换步骤：

1. 消除ε产生式（除非ε在语言中，此时保留S→ε或增加新开始符号）。
2. 消除单位产生式。
3. 消除无用符号。
4. 对于右边长度≥3的产生式，引入新非终结符逐步拆分。比如 A → BCD，引入E，变成 A → BE, E → CD。
5. 对于右边含终结符且长度≥2的产生式，把终结符替换成新非终结符。比如 A → aB，引入C → a，变成 A → CB。

举个例子：

S → aSb | ε

先消除ε：S可空，生成S → ab | aSb，保留S → ε（因为ε在语言中）。消除单位产生式：没有。消除无用符号：没有。现在产生式有 S → aSb | ab | ε。处理S → aSb：右边长度3，引入新非终结符A和B，A → a，B → b，然后S → ASB。但ASB长度3，再拆：引入C，S → AC, C → SB。最终：

S → AC | AB | ε A → a B → b C → SB

但AB长度2，A和B都是非终结符，符合CNF。AC也符合。所以最终CNF是：

S → AC | AB | ε A → a B → b C → SB

注意这里S → ε是允许的，因为ε在语言中。

6.2 Greibach范式：所有产生式都是 A → aα

Greibach范式（GNF）要求所有产生式形如 A → aα，其中a是终结符，α是非终结符串（可以为空）。转换比CNF复杂得多，通常课后题不会要求完整转换，但会要求理解步骤：

1. 先转成CNF。
2. 把非终结符排序，通过代入消除左递归。
3. 逐步把产生式右边的第一个符号替换成终结符。

我自己的经验是，GNF的题如果出现在课后题里，通常只要求转换简单的文法，比如 S → aB | bC, B → bB | a, C → cC | a。这种直接看就能转。复杂的文法转换过程极其繁琐，考试时如果遇到，先检查是否必须转GNF，有时候题目只要求CNF。

提示：CNF和GNF的主要用途是理论证明，比如证明CFG和PDA等价、证明CYK算法正确性。实际写编译器时不会真的把文法转成CNF，因为转换后文法变得极其臃肿。但理解转换过程能帮你深入理解CFG的结构。

6.3 转换中的常见错误与检查方法

最常见的错误是拆分产生式时引入的新非终结符命名冲突，或者忘记处理ε产生式导致CNF不纯。检查方法是：转换完成后，逐条检查每个产生式是否符合范式要求。CNF要求右边要么是两个非终结符，要么是一个终结符。如果出现右边是三个符号、或者右边是终结符加非终结符、或者右边是单个非终结符（单位产生式），都不符合。

另一个常见错误是消除ε产生式时漏掉某些可空组合。比如 A → BCD，B和D可空，C不可空，那么需要生成 A → BCD, A → BC, A → CD, A → C 四种。很多同学只生成了 A → BC 和 A → CD，漏掉了 A → BCD 和 A → C。这个在课后题里经常出现，需要仔细。

我自己的检查方法是：转换完成后，用几个目标语言中的串手动推导一遍，看能否生成。如果生成不了，说明转换过程中丢了产生式。这个方法虽然笨，但很有效。

7. PDA构造：从文法到自动机的翻译逻辑

7.1 从CFG构造等价PDA的标准流程

给定CFG G = (V, T, P, S)，构造PDA M = (Q, Σ, Γ, δ, q0, Z0, F) 的标准方法：

• Q = {q0, q1, q2}，其中q0是初始状态，q2是接受状态。
• Σ = T（输入字母表）。
• Γ = V ∪ T ∪ {Z0}（栈字母表）。
• Z0是初始栈符号。
• δ定义：
  • δ(q0, ε, Z0) = {(q1, SZ0)}：初始化，把开始符号压栈。
  • 对于每个产生式 A → α，δ(q1, ε, A) = {(q1, α)}：非确定性替换。
  • 对于每个终结符 a，δ(q1, a, a) = {(q1, ε)}：匹配输入并弹栈。
  • δ(q1, ε, Z0) = {(q2, Z0)}：栈空且输入读完，接受。

这个构造的核心思想是：PDA用栈来模拟文法的推导过程。栈顶是非终结符时，非确定性地选择一个产生式替换；栈顶是终结符时，必须和输入匹配并弹出。当栈底只剩Z0且输入读完时，接受。

举个例子，文法 S → aSb | ε。构造PDA：

• δ(q0, ε, Z0) = {(q1, SZ0)}
• δ(q1, ε, S) = {(q1, aSb), (q1, ε)}
• δ(q1, a, a) = {(q1, ε)}
• δ(q1, b, b) = {(q1, ε)}
• δ(q1, ε, Z0) = {(q2, Z0)}

这个PDA接受a^n b^n。你可以手动模拟输入aabb：初始栈Z0，读ε压入S，栈变成SZ0。非确定性选择S→aSb，栈变成aSbZ0。读a，匹配a，弹栈，栈变成SbZ0。选择S→aSb，栈变成aSbZ0...等等。最终匹配完所有输入，栈只剩Z0，接受。

7.2 从PDA构造等价CFG：三元组方法

反过来，给定PDA构造CFG，标准方法是定义非终结符 [q, A, p]，表示“从状态q到状态p，栈顶符号A被弹出”。然后根据PDA的转移规则写产生式。这个方法在课后题里经常出现，但过程比较繁琐。

具体步骤：

1. 对于每个转移 δ(q, a, A) 包含 (r, B1B2...Bk)，对于任意状态序列 p1, p2, ..., pk，添加产生式 [q, A, pk] → a [r, B1, p1] [p1, B2, p2] ... [pk-1, Bk, pk]。
2. 对于每个状态q，添加产生式 [q, A, q] → ε。
3. 开始符号是 [q0, Z0, qf]，其中qf是接受状态。

这个方法的核心思想是：PDA的一次转移对应文法的一次推导。栈顶符号A被弹出，同时压入B1...Bk，然后从状态r经过一系列中间状态最终到达pk。这个构造在理论证明中很重要，但实际做题时如果PDA状态少，可以手动简化。

注意：从PDA构造CFG时，如果PDA有多个接受状态，需要引入新的开始符号和ε转移统一到单个接受状态。这个细节在课后题里经常被忽略，导致构造出的文法多出一些不必要的非终结符。

7.3 PDA构造中的非确定性处理

PDA的本质是非确定性的，同一个状态、同一个输入、同一个栈顶，可能有多个转移。这在构造时是允许的，但模拟时需要考虑所有可能路径。课后题里经常要求“给出接受某语言的PDA”，这时候你可以利用非确定性简化构造。

比如语言 {ww^R | w ∈ {a,b}*}，即所有回文串。构造PDA时，可以非确定性地猜测字符串的中点。在读到中点之前，把每个字符压栈；猜测到中点后，开始匹配并弹栈。具体：

• δ(q0, a, Z0) = {(q0, aZ0)}
• δ(q0, b, Z0) = {(q0, bZ0)}
• δ(q0, a, a) = {(q0, aa)}
• δ(q0, b, b) = {(q0, bb)}
• δ(q0, a, b) = {(q0, ab)}
• δ(q0, b, a) = {(q0, ba)}
• δ(q0, ε, Z0) = {(q1, Z0)}：猜测中点在开头（空串）
• δ(q0, ε, a) = {(q1, a)}：猜测中点在当前字符后
• δ(q0, ε, b) = {(q1, b)}：猜测中点在当前字符后
• δ(q1, a, a) = {(q1, ε)}
• δ(q1, b, b) = {(q1, ε)}
• δ(q1, ε, Z0) = {(q2, Z0)}

这个PDA的非确定性体现在“猜测中点”的ε转移上。对于奇数长度回文，中点是一个字符，可以跳过；对于偶数长度回文，中点在两个字符之间。这个构造在课后题里非常经典，几乎每本教材都会出现。

我自己的经验是，PDA构造题的关键是想清楚栈里存什么。栈通常用来存“还没匹配的前半部分”，或者“需要记住的状态”。一旦确定了栈的用途，转移函数就自然出来了。

8. 等价性证明与泵引理：第五章的“硬骨头”

8.1 证明两个文法等价：双向包含

证明两个文法G1和G2等价，需要证明L(G1) ⊆ L(G2) 且 L(G2) ⊆ L(G1)。通常用归纳法：证明G1的每个产生式在G2中都能模拟，反之亦然。或者证明两个文法生成相同的语言，通过构造中间自动机。

课后题里常见的等价性证明是：证明化简后的文法与原文法等价。这个相对简单，因为化简步骤（消除ε、单位、无用符号）都是保持语言不变的。你只需要说明每一步为什么保持语言不变即可。

更难的题是：给定两个看起来完全不同的文法，证明它们等价。这时候通常需要找到一个中间语言，证明两个文法都生成这个语言。比如文法1是 S → aSb | ε，文法2是 S → aA, A → Sb | ε，证明它们都生成a^n b^n。这种题需要你分别证明两个文法生成的语言都是a^n b^n。

8.2 用泵引理证明语言不是上下文无关的

泵引理是证明语言不是CFL的标准工具。CFL的泵引理说：如果L是CFL，则存在常数p，使得L中任何长度≥p的串s都可以写成s = uvxyz，满足：

1. |vxy| ≤ p
2. |vy| ≥ 1
3. 对于所有i ≥ 0，uv^i xy^i z ∈ L

用泵引理证明时，通常采用反证法：假设L是CFL，取一个特殊的串s，然后枚举vxy的所有可能位置，证明无论怎么分，都能找到一个i使得uv^i xy^i z不在L中。

举个例子，证明L = {a^n b^n c^n | n ≥ 0}不是CFL。假设L是CFL，取s = a^p b^p c^p。根据泵引理，s = uvxyz，|vxy| ≤ p。因为|vxy| ≤ p，所以vxy不可能同时包含a、b、c三种字符（因为a和c之间至少隔了p个b）。所以vxy最多包含两种字符。那么泵操作后，a、b、c的数量不可能同时保持相等。矛盾。所以L不是CFL。

这个证明的关键是选择正确的串和利用|vxy| ≤ p的限制。课后题里经常出现类似的语言，比如 {a^n b^n c^n}、{a^n b^m c^n d^m}、{ww | w ∈ {a,b}*}。每个都需要选择不同的串和不同的矛盾点。

提示：泵引理证明的难点在于“枚举所有情况”。通常vxy的位置可以按“在a段”“在b段”“跨a和b”“跨b和c”“在c段”等分类。每类都要证明泵操作后串不在L中。这个过程很繁琐，但套路固定，多练几道就能掌握。

8.3 泵引理证明中的常见错误

最常见的错误是没有覆盖所有可能的vxy位置。比如只考虑了vxy在a段的情况，忽略了vxy跨a和b的情况。另一个错误是泵操作后没有正确计算各字符数量。比如v和y分别包含不同数量的a和b，泵操作后a和b的数量变化不同，需要仔细计算。

我自己的做法是：画一个表格，列出vxy所有可能的位置组合，然后逐一分析。虽然费时间，但能保证不遗漏。考试时如果时间紧，至少要把主要情况覆盖到，比如vxy在单个字符段、跨两个字符段、跨三个字符段（但|vxy| ≤ p限制了跨三个字符段的可能性）。

9. 课后题实战中的经验与避坑清单

9.1 先化简再做题，能省一半时间

很多课后题给的文法包含ε产生式、单位产生式、无用符号，直接做题会非常繁琐。我的习惯是：拿到文法先花5分钟化简，消除ε、单位、无用符号，然后再做后续的推导、构造PDA、转范式。化简后的文法产生式少，推导路径短，出错概率大大降低。

但要注意：如果题目明确要求“不化简，直接构造PDA”，那就不能化简。有些题目考察的就是你在复杂文法上的构造能力。所以做题前先读清楚题目要求。

9.2 构造PDA时，栈符号的设计是关键

PDA构造题最容易卡住的地方是“栈里放什么”。我的经验是：栈通常用来存“还没匹配的输入”或者“需要记住的约束”。比如对于a^n b^n，栈里存a的数量；对于回文串，栈里存前半部分；对于括号匹配，栈里存左括号。一旦确定了栈的用途，转移函数就自然出来了。

如果实在想不出栈的用途，可以先用自然语言描述“机器应该怎么工作”，然后把每一步操作翻译成转移函数。比如“读a时压栈，读b时弹栈，栈空时接受”，翻译成转移就是 δ(q0, a, Z0) = {(q0, aZ0)}, δ(q0, a, a) = {(q0, aa)}, δ(q0, b, a) = {(q0, ε)}, δ(q0, ε, Z0) = {(qf, Z0)}。

9.3 范式转换后必须验证

CNF和GNF转换后，文法通常变得面目全非。这时候必须验证转换后的文法是否与原文法等价。验证方法是：从转换后的文法推导几个原语言中的串，看能否生成；再推导几个不在原语言中的串，看能否生成。如果都能正确区分，说明转换正确。

我见过很多同学转换完就直接交作业，结果因为漏了某个产生式导致语言变了。这个错误在考试中扣分很重，因为范式转换的步骤分很多，最后结果错了可能全扣。

9.4 等价性证明要写清楚每一步的依据

等价性证明题通常要求写出完整的证明过程。这时候不能只写“显然等价”，必须写出每一步的依据。比如“因为消除ε产生式保持语言不变（定理X），所以L(G1) = L(G2)”。课后题批改时，步骤分占很大比重，即使最终结论对了，步骤不完整也会扣分。

我自己的习惯是：证明时先写“要证L(G1) ⊆ L(G2)”，然后写“任取w ∈ L(G1)，则存在推导...”，再写“根据归纳假设...”，最后写“因此w ∈ L(G2)”。反向同理。这个格式虽然八股，但能保证逻辑清晰，批改时容易给分。

9.5 泵引理题先猜再证

泵引理题通常先给一个语言，让你证明它不是CFL。我的做法是：先凭直觉猜这个语言“看起来不像CFL”，然后找反例。如果猜错了，语言其实是CFL，那就需要构造CFG或PDA。所以做题前先花1分钟判断语言是否可能是CFL。

判断经验：如果语言需要“同时记住两个独立的数量”，比如a^n b^n c^n，通常不是CFL。如果语言只需要“记住一个数量”，比如a^n b^n，通常是CFL。如果语言涉及“复制”，比如ww，通常不是CFL。这个经验能帮你快速判断方向。

9.6 时间分配：先做构造题，后做证明题

考试时如果时间紧张，先做文法设计、PDA构造、范式转换这些“有明确步骤”的题，再做等价性证明和泵引理这些“需要灵感”的题。构造题只要步骤对就能拿分，证明题如果卡住可能一分不得。我自己的经验是，构造题占70%分数，证明题占30%，先把构造题的分拿稳，再攻证明题。

最后分享一个我自己的小技巧：做第五章课后题时，准备一张白纸，把每个题型的“标准步骤”写下来，做题时对照步骤走。比如“消除ε产生式：1.找可空非终结符 2.生成新产生式 3.删ε产生式”。这个清单能帮你避免遗漏步骤，也能在考试前快速复习。第五章的题虽然难，但题型固定，把每类题的步骤练熟，考试时就是默写步骤加计算，没有想象中那么可怕。