1 字符串

字符的有限集合$\Sigma$称为字符表，其中的元素相连组成的有限序列称为字符串。空串记为$\epsilon$

多个字符串相连称为连接运算。如字符串x=ab，字符串y=bc，则二者的连接xy=abbc。如果x和自己连接可以表示成幂的形式，如$x^2=abab$，$x^0=\epsilon$

给定字符串集合A,B，其乘积运算定义为元素级别的连接：$AB=\{xy|x\in A, y\in B\}$

给定字符串集合V，其闭包运算有2种：正闭包+和星闭包*，定义分别为$V^+=V^1 \cup V^2 \cup …$，$V^=V^0 \cup V^1 \cup …$。显然$V^=V^++\{\epsilon\}$

2 形式语法（文法）

形式语法（by乔姆斯基): 

$$G=(N,T,S,P)$$

• N是非终结符集
• T是终结符集，$N\cap T=\varnothing$，$N\cup T=V$称为单词表
• S是初始符,$S\in N$
• P是规则集，P中的重写规则r形如$\alpha \to \beta$，将$\alpha$替换成$\beta$。$\alpha$不是空串

根据文法产生的字符串集叫做语言，记作L(G)。根据P的细节，形式文法有下文4种形式

无约束文法（0型文法）

几乎没有约束，$\alpha$至少含有一个非终结符就行。$\alpha \in V^+$，$\beta \in V^*$。这种文法约束非常小，生成能力很强。产生的语言称为0型语言，能够被图灵机识别

上下文相关文法CSG（1型文法）

规则替换必须有上下文语境：$aAb \to a B b$，$a,b,B \in V^*$。a，b就是A的上下文语境。如果a，b同时为空，就变成了下面的上下文无关文法。上下文相关语言能够被线性界限自动机识别

上下文无关文法CFG（2型文法）

规则左边只能有一个非终结符：$A \to x$，$A \in N, x \in V^*$。上下文无关语言能够被下推自动机识别。上下文无关文法可以用推导树表示，也是短语结构语法PSG的基础

正则文法（3型文法）（有限状态文法FSG）

终结符只能在$\beta$最左边或最右边。对应左正则文法和右正则文法。用公式表示就是设A,B是于非终结符，x是终结符，则$A\to Bx$（右正则文法），$A\to xB$（右正则文法），$A\to x$（二者都有）。这种文法产生的语言能够被有限状态自动机FDA识别，所以又叫有限状态文法FSG

可以看到，从0型文法到3型文法，约束越来越多，并且$FSG\subset CFG\subset CSG\subset type0G$

2 短语结构语法

CFG产生句子的过程可以用推导树表示：

• 节点$\in V$
• 根节点=S
• 非叶节点一定是非终结符
• 从左向右排列的节点A1，A2，A3…是节点A的子节点，则必有A→A1A2A3…是P中的规则

支配关系和前于关系：父节点支配子节点，兄节点前于弟节点

3 依存语法

和短语结构语法不同的句子分析方式（by泰尼埃）

• 动词是句子的中心，支配着别的成分，本身不受其他任何成分的支配，主语和宾语都在动词支配之下，可以相互调位置，形成被动句
• 依存树中直接处于动词节点之下的，是名词词组和副词词组。名词词组形成行动元，副词词组形成状态元
  • 行动元的数目（即配价数目）不超过3：主语、直接宾语、间接宾语
  • 状态元可以是无限的（无限修饰）
  • 动词的行动元可以不饱和，即有些价可以空缺