形式语言与自动机学习笔记(6)：期末复习

按照往年题来看，题型较为固定，一般为 10 道大题。

1. 语言的封闭性问题

往年题中有出现。所以简单过一下。

1.1 上下文无关语言的封闭性

对并、积、闭包、置换封闭，对交和补不封闭。仅讲述并和积的构造方法。

1.1.1 并封闭

对于上下文无关语言 $L(G_1)$ 和 $L(G_2)$ 分别由文法 $G_1=(N_1,T_1,P_1,S_1)$ 和 $G_2=(N_2,T_2,P_2,S_2)$ （$N_1 \cap N_2 = \phi$）产生，$L(G)=L(G_1)\cup L(G_1)$ 也为 2 型语言。

只需构造 $G = (N,T,P,S)$ ，其中：

• $N=N_1\cup N_2\cup \{S\}$ ；
• $T = T_1\cup T_2$ ；
• $P = P_1 \cup P_2 \cup \{S \rightarrow S_1 | S_2\}$ ；
• $S = S$ ；

1.1.2 积运算封闭

对于上下文无关语言 $L(G_1)$ 和 $L(G_2)$ 分别由文法 $G_1=(N_1,T_1,P_1,S_1)$ 和 $G_2=(N_2,T_2,P_2,S_2)$ （$N_1 \cap N_2 = \phi$）产生，$L(G)=L(G_1)\cdot L(G_1)$ 也为 2 型语言。

只需构造 $G = (N,T,P,S)$ ，其中：

• $N=N_1\cup N_2\cup \{S\}$ ；
• $T = T_1\cup T_2$ ；
• $P = P_1 \cup P_2 \cup \{S \rightarrow S_1S_2\}$ ；
• $S = S$ ；

与上面的区别只有新加入的产生式。

1.2 右线性语言的封闭性

仅讲述并和积的构造。

1.2.1 并封闭

文法角度，对于右线性语言 $L(G_1)$ 和 $L(G_2)$ 分别由文法 $G_1=(N_1,T,P_1,S_1)$ 和 $G_2=(N_2,T,P_2,S_2)$ （$N_1 \cap N_2 = \phi$）产生，$L(G)=L(G_1)\cup L(G_1)$ 也为右线性语言。

只需构造 $G = (N,T,P,S)$ ，其中：

• $N=N_1\cup N_2\cup \{S\}$ ；
• $P = P_1 \cup P_2 \cup \{S \rightarrow S_1 | S_2\}$ ；

自动机角度，其实就是添加了一个新的初始状态然后连接。

1.2.2 积运算

文法角度，只需构造 $G = (N,T,P,S)$ ，其中：

• $N=N_1\cup N_2$ ；
• 如果 $A\rightarrow \alpha B\in P_1$ ，则 $A\rightarrow \alpha B\in P$ ；
• 如果 $A\rightarrow \alpha\in P_1$ ，则 $A\rightarrow \alpha S_2\in P$ ；
• $P_2\subseteq P_1$ ；

自动机角度，头尾连接。

2. Chomsky 文法体系

3. 右线性文法、正则式和有限自动机

4. 米兰机 and 摩尔机

5. Pumping 引理

6. 上下文无关文法的变换

7. 下推自动机与上下文无关文法的变换

8. 构造语言的图灵机

9. 一些问答题

1. 为什么要消除左递归？

以后的句法分析算法不适用于左递归,会引起死循环。如果在编写 E 的递归下降解析函数时，直接在函数的开头递归调用自己，输入字符串完全没有消耗，这种递归调用就会变成一种死循环。

2. 2 型语言有什么用？

可定义程序设计语言、进行语法分析、简化语言翻译。可以解析递归结构。

3. 正则语言有什么用？

编译器中使用正则表达式、正则语言和 DFA 等工具实现了词法分析，即将输入的字符串分解成一个个的单词流，也就是诸如编程语言中的关键字、标识符这样有特定意义的单词。

4. 上下文无关文法构造等价的下推自动机时，为什么这么构造？

由于对栈中非终结符的替换总是在栈顶进行，因此，PDA 实际上模拟的是文法的最右推导过程。