考点：文法⇒推导树

解：（1）

（2）

（3）

考点：文法⇒最左/右推导

解：最左推导：$E{\Rightarrow }_{lm}E+T{\Rightarrow }_{lm}T+T{\Rightarrow }_{lm}F+T{\Rightarrow }_{lm}b+T{\Rightarrow }_{lm}b+T/F{\Rightarrow }_{lm}b+F/F{\Rightarrow }_{lm}b+b/F{\Rightarrow }_{lm}b+b/b$

最右推导：$E{\Rightarrow }_{rm}E+T{\Rightarrow }_{rm}E+T/F{\Rightarrow }_{rm}E+T/b{\Rightarrow }_{rm}E+F/b{\Rightarrow }_{rm}E+b/b{\Rightarrow }_{rm}T+b/b{\Rightarrow }_{rm}F+b/b{\Rightarrow }_{rm}b+b/b$

考点：文法二义性证明
解：画出语言 $aaaba$ 的2颗推导树如下：


同一文法可画出2个不同的推导树，因此该文法具有二义性。

考点：语言⇒上下文无关文法（设计上下文无关文法）

解：（1）考虑在产生相同数目的0,1后，再生成多余的1.
G=({S},{0,1},P,S)G=(\{S\},\{0,1\},P,S)G=({S},{0,1},P,S)，其中P为：$S\to 1S0|1S|10$

（2）考虑将0和1的部分拆开：G=({S,A},{0,1},P,S)G=(\{S,A\},\{0,1\},P,S)G=({S,A},{0,1},P,S)，其中P为：
$S\to 1A1|1S1$
$A\to 00A|00$（服务 $0^{2m}$）

（3）考虑将语言拆为2部分：G=({S,A,B},{0,1},P,S)G=(\{S,A,B\},\{0,1\},P,S)G=({S,A,B},{0,1},P,S)，其中P为：
$S\to AB$（拆为2部分）
$A\to 1A0|10$
$B\to 1B0|10$

考点：消除无用符号

解：（1）首先使用算法1，得到非生成符号C，删去C及其生成式有：
$$S\to ED$$

$$D\to a$$

$$E\to b$$

使用算法2，发现没有不可达符号，因此等价文法为：G=({S,D,E},{a,b},P,S)G=(\{S,D,E\},\{a,b\},P,S)G=({S,D,E},{a,b},P,S)，其中P：
$$S\to ED$$

$$D\to a$$

$$E\to b$$

（2）首先使用算法1，得到非生成符号C，删去C及其生成式有：
$$S\to D$$

$$D\to bS|b$$

$$E\to DS|b$$

使用算法2，发现不可达符号E，删去E及其生成式。因此等价文法为：G=({S,D}.{b},P,S)G=(\{S,D\}.\{b\},P,S)G=({S,D}.{b},P,S)，其中P：
$$S\to D$$

$$D\to bS|b$$

考点：消空产生式

解：根据算法得，可得致空符号有：$D、E、C、S$，$S$ 也为致空符号，因此加入 $S_1\to S|\epsilon$，对于 $S\to DCE$ 有：$S\to DCE|CE|DE|DC|D|C|E$。因此消空后的等价文法为：G1=({S1,S,C,D,E},{a,b},P,S1)G_1=(\{S_1,S,C,D,E\},\{a,b\},P,S_1)G1​=({S1​,S,C,D,E},{a,b},P,S1​)，其中 $P$：
$$S_1\to S|\epsilon$$

$$S\to DCE|CE|DE|DC|D|C|E$$

$$D\to CC|C$$

$$C\to EE|E|b$$

$$E\to DD|D|a$$

考点：简化CFG（消无用→消空→消单→消无用 ）

解：首先消无用符号，利用算法1发现没有非生成符号，再利用算法2也没有发现不可达符号。

再消致空符号，利用算法发现所有符号都为致空符号。$S$ 为致空符号，因此将 $S_1\to S|\epsilon$ 加入P，P变为：
$$S_1\to S|\epsilon$$

$$S\to A_1|A_2$$

$$A_1\to A_3|A_4$$

$$A_2\to A_4|A_5$$

$$A_3\to S|b$$

$$A_4\to S|a$$

$$A_5\to S|d$$

再消除单产生式，构造 $N_S,N_{A_i},i=1,2,3,4,5$，产生式的关系如下图：

因此P为：
$$S_1\to a|b|d|\epsilon$$

$$S\to a|b|d$$

$$A_1\to a|b|d$$

$$A_2\to a|b|d$$

$$A_3\to a|b|d$$

$$A_4\to a|b|d$$

$$A_5\to a|b|d$$

最后消去无用符号，利用算法1发现没有非生成符号；再用算法2发现只有 $S_1$ 为可达符号，删去其他符号及其产生式得到文法 G1=({S1},{a,b,d},P,S1)G_1=(\{S_1 \},\{a,b,d\},P,S_1)G1​=({S1​},{a,b,d},P,S1​)，其中P为 $S_1\to a|b|d|\epsilon$

考点：转换为CNF（Chomsky范式）

解：首先删除无用符号，利用算法1发现没有非生成符号，再利用算法2发现没有不可达符号；
再删除致空符号，利用算法发现S为致空符号，将 $S_1\to \epsilon |S$加入到P中，此时P为：
$$S_1\to \epsilon |S$$

$$S\to ASB|AB$$

$$A\to aAS|aA|a$$

$$B\to SBS|SB|BS|A|bb$$

再消单产生式，单产生式有：$S_1\to S,B\to A$，因此此时P变为：
$$S_1\to \epsilon |ASB|AB$$

$$S\to ASB|AB$$

$$A\to aAS|aA|a$$

$$B\to SBS|BS|SB|bb|aAS|aA|a$$

再消去无用符号，利用算法1、2发现没有无用符号。
最后转换为CNF：对 $S_1\to \epsilon |AB,S\to AB,A\to a,B\to BS|SB|a$ 为CNF，加入到P中。
将 $S_1\to ASB$ 变换为 $S_1\to AC,C\to SB$
将 $S\to ASB$ 变换为 $S\to AC$，
将 $A\to aAS|aA$ 变换为 $A\to ED，A\to EA，D\to AS，E\to a$
将 $B\to SBS|aAS|aA|bb$ 变换为 $B\to CS，B\to ED，B\to EA，B\to FF，F\to b$

由此得到文法 G1=({S1,S,A,B,C,D,E,F},{a,b},P1,S1)G1=(\{S_1,S,A,B,C,D,E,F\},\{a,b\},P_1,S_1)G1=({S1​,S,A,B,C,D,E,F},{a,b},P1​,S1​)，其中 $P_1$ 为：
$$S_1\to AB|\epsilon |AC$$

$$S\to AB|AC$$

$$A\to ED|EA|a$$

$$B\to BS|SB|a|CS|ED|EA|FF$$

$$C\to SB$$

$$D\to AS$$

$$E\to a$$

$$F\to b$$

考点：转换为CNF（Chomsky范式）

解：先消除无用符号，利用算法1、2发现没有无用符号；再消致空符号，利用算法发现致空符号为A,B，因此P变为：
$$S\to 0BB|0B|1AA|1A|0|1$$

$$B\to 0B0|00$$

$$A\to 11A|11$$

此时没有单产生式和无用符号，转换为CNF：$S\to 0|1$为CNF，加入到P中
将 $S\to 0BB$ 变换为 $S\to CB，C\to DB，D\to 0$
将 $S\to 0B$ 变换为 $S\to DB$
将 $S\to 1AA$ 变换为 $S\to EA$，$E\to FA$，$F\to 1$
将 $S\to 1A$ 变换为 $S\to FA$
将 $B\to 0B0$ 变换为 $B\to CD$
将 $B\to 00$ 变换为 $B\to DD$
将 $A\to 11A$ 变换为 $A\to FE$
将 $A\to 11$ 变换为 $A\to FF$

由此得到的文法为：G1=({S,A,B,C,D,E,F,G},{0,1},P1,S)G1=(\{S,A,B,C,D,E,F,G\},\{0,1\},P_1,S)G1=({S,A,B,C,D,E,F,G},{0,1},P1​,S)，其中 $P_1$ 如下：
$$S\to CB|DB|EA|FA|0|1$$

$$A\to FE|FF$$

$$B\to CD|DD$$

$$C\to DB$$

$$D\to 0$$

$$E\to FA$$

$$F\to 1$$

考点：转换为GNF（Greibach范式）

解：题给产生式为CNF，N排序为 $S,D$，其中D为高位，第2个式子右边首符序号＞左边的N，需要变换，将1式代入2式中有：$D\to DDS|aS|b$

消除直接左递归，$D\to aS|b|as{D}^{\prime }|b{D}^{\prime },D^{\prime }\to DS|DS{D}^{\prime }$

进行回代，此时N排序为 $D^{\prime },S,D$，其中D为高位：
$D’$ 回代入$S$：$S\to aSD|bD|aS{D}^{\prime }D|b{D}^{\prime }D|a$
$D$ 回代入$D’$： $D^{\prime }\to aSS|bS|as{D}^{\prime }S|b{D}^{\prime }S|aSS{D}^{\prime }|bS{D}^{\prime }|as{D}^{\prime }S{D}^{\prime }|b{D}^{\prime }S{D}^{\prime }$

考点：2 型文法⇒PDA

解：（1）

（2）


考点：语言⇒文法（设计文法）；文法的二义性

解：G=({S,A,B,C,D},a,b,c,P,S)G=(\{S,A,B,C,D\},{a,b,c},P,S)G=({S,A,B,C,D},a,b,c,P,S)
$$S\to AD|BC$$

$$A\to aA|\epsilon$$

$$B\to aBb|\epsilon$$

$$C\to cC|\epsilon$$

$$D\to bDc|\epsilon$$
有二义性，当 $i=j=k$ 时，存在 2 颗推导树，如 $abc\in L$：


考点：泵浦引理

解：（1）假设是 CFL。利用泵浦引理，取常数 p，$\omega =0^{p^2}{1}^p，|\omega |=p^2+p\ge p$，将 ω 写为 ${\omega }_1{\omega }_2{\omega }_0{\omega }_3{\omega }_4$，其中 ${\omega }_2{\omega }_3\ne \epsilon$ 且 $|{\omega }_2{\omega }_0{\omega }_3|\le p$，下面考虑 ${\omega }_2{\omega }_0{\omega }_3$ 在 $\omega$ 中所处的位置：
①当 ${\omega }_2,{\omega }_3$ 都只包含 0 (1 同理) 时，${\omega }_1{\omega }_2^0{\omega }_0{\omega }_3^0{\omega }_4$ 的 0 部分长度减少，1 部分长度不变，明显不属于 L，与 CFL 的假设矛盾。
②当 ${\omega }_2,{\omega }_3$ 自身不能横跨 $0^{p^2}{1}^p$时，否则 01 顺序会乱，因此只能是 ${\omega }_2$ 在0 部分，${\omega }_3$在 1 部分。假设 |${\omega }_2|=k_1\ge 1,|{\omega }_3|=k_2\ge 1$，则取 ${\omega }_1{\omega }_2^0{\omega }_0{\omega }_3^0{\omega }_4，(p-k_2{)}^2\le (p-1{)}^2=p^2-2p+1<p^2-k_1$。因此 $\omega \notin L$，与 CFL 的假设矛盾。
综上所述，不是 CFL。

（5）假设是 CFL，利用泵浦引理。取常数 p，$\omega =xx$，取 $\omega =0^p{1}^p{0}^p{1}^p，|\omega |=4p\ge p$，将 $\omega$ 写为 ${\omega }_1{\omega }_2{\omega }_0{\omega }_3{\omega }_4$，其中 ${\omega }_2{\omega }_3\ne \epsilon$ 且 $|{\omega }_2{\omega }_0{\omega }_3|\le p$。下面考虑 ${\omega }_2{\omega }_0{\omega }_3$ 在 $\omega$ 中所处的位置：
①当 ${\omega }_2,{\omega }_3$ 位于同一 0（1 同理）时，${\omega }_1{\omega }_2^0{\omega }_0{\omega }_3^0{\omega }_4$ 的 ${\omega }_2,{\omega }_3$ 部分长度减少，明显不属于L，与 CFL 的假设矛盾；
②当 ${\omega }_2{\omega }_0{\omega }_3$ 横跨0和1时，${\omega }_1{\omega }_2^0{\omega }_0{\omega }_3^0{\omega }_4$ 的 ${\omega }_2,{\omega }_3$ 所在部分长度改变 $\ne p$，明显不属于L，与 CFL 的假设矛盾；
综上所述，不是 CFL。

考点：设计 PDA

解：（1）

（2）

（3）

（4）容易写出文法：$S\to 0S1|0S11|\epsilon$，将文法转换为 PDA：

（5）

$q_1$ 表示 1 的个数＞0 的个数，$q_2$ 表示 0 的个数＞1 的个数