参考教材：杨娟，石川，王柏.形式语言与自动机.北京：北京邮电大学出版社，2003.

语言与文法

$Def.$

1. 字母表$T$
2. 字符串$t,u,v,x,y,z$及其长度
3. 字符串的转置$\tilde{\omega }$
4. 包括$\epsilon$在内的字母表$T$上的所有字符串集合$T^{\ast }$
5. 不包括$\epsilon$在内的字母表$T$上的所有字符串集合$T^{+}$
6. 字母表$T$上的语言$L$是$T^{\ast }$的子集
7. 两个语言的积：$L_1$和$L_2$的积$L_1\cdot L_2$，是由$L_1$和$L_2$的字符串连接所构成的字符串的集合；
   语言的积不满足交换律
8. 语言的幂：
   $$\begin{gathered} L^0=\epsilon \\ {L}^n=L\cdot L^n-1 \end{gathered}$$
9. 语言的闭包与正闭包$$\begin{gathered} L^{\ast }=\bigcup _{n⩾0}{L}^n \\ {L}^{+}=\bigcup _{n⩾1}{L}^n \end{gathered}$$
10. 文法 定义语言的数学模型
11. 使用Chomsky文法体系定义语言：文法G是一个四元组，$G=(N,T,P,S)$
    （1）$N$ 非终结符的有限集合
    （2）$T$ 终结符的有限集合，且$N\bigcup T=\varnothing$
    （3）$P$ 形式为$\alpha \to \beta$的生成式有限集合，且$\alpha \in (N\bigcup T{)}^{+},\beta \in (N\bigcup T{)}^{\ast }$，$\alpha$至少含一个非终结符号，意味着$\alpha$不能为空串而且不能全由终结符组成
    （4）$S$ 起始符，$S\in N$
12. 推导：直接推导（长度为1）$\alpha \Rightarrow {\alpha }_0$，长度为0的推导$\alpha ={\alpha }_0$，长度大于0的推导$\alpha \underset{G}{\overset{\ast }{\Rightarrow }}{\alpha }_0$
13. 句型：字符串$\alpha$是文法$G$的句型当且仅当$S\underset{G}{\overset{\ast }{\Rightarrow }}\alpha$且$\alpha \in (N\bigcup T{)}^{\ast }$
14. 由文法产生的语言L(G)={ω∣ω∈T∗,S⇒G∗ω}L(G)=\lbrace\omega | \omega \in T^{*},S \xRightarrow [G] {*} \omega \rbraceL(G)={ω∣ω∈T∗,S∗G​ω}，即 $L(G)$ 中的一个字符必须由 $S$ 推导出，由终结符组成
15. 文法分类
    （1）0型：无限制 （但也有基础限制）对应无限制性语言
    （2）1型：上下文有关文法。生成式的形式为$\alpha \to \beta$，其中$|\alpha |⩽|\beta |$，且$\alpha ,\beta \in (N\bigcup T{)}^{+}$ 对应上下文有关语言
    典型特征：左边比右边短
    （3）2型：上下文无关文法。生成式的形式为$A\to \alpha ,A\in N,\alpha \in (N\bigcup T{)}^{\ast }$ 对应上下文无关语言
    典型特征：左边都是非终结符 注意2型的右边可以是$\epsilon$，而1型不可
    （4）3型：正则文法。生成式的形式为$A\to \omega B$或$A\to \omega ,A,B\in N,\omega \in T^{\ast }$称右线性文法，如果生成式的形式为$A\to B\omega$或$A\to \omega$称左线性文法 对应正则语言
    总结：当2型不包含 $A\to \epsilon$时， 3型 $\in$ 2型$\in$ 1型$\in$ 0型
16. 巴科斯范式（BNF, Backus Normal Form）：讨论某种程序设计语言语法的一种元语言。使用$::=$代替生成式中的$\to$，所有的非终结符号都用$<>$括起来，左端相同的生成式的右端使用$|$隔开后合并成一个生成式。
17. 语法图：方框表示非终结符号，圆框表示终结符号

能力要求

1. 字符串的运算和闭包计算
2. 由文法推导语言
3. 证明从文法推导出的语言正确，证明集合等价需要证明左边包含右边，右边包含左边
4. 判断文法分类
5. 构造文法