字母表：

    字母表是元素的非空有穷集合，字母表中的元素称为符号,因此字母表也称为符号集。

---

符号串：

    由字母表中的符号组成的任何有穷序列称为符号串。


    在符号串中，符号的顺序是非常重要的。


    如果某符号串x中有m个符号，则称其长度为m,表示为|x|=m。


    允许空符号串,即不包含任何符号的字符串，用ε表示，其长度为0，即|ε|=0。

---

1）有关符号的头尾，固有头和固有尾

    如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。

2）符号串的连接

    设x和y是字符串，他们的连接xy是把y的符号写在x的符号之后得到的字符串。


    由于ε的含义，显然有εx=xε=x。

3）符号串的方幂

    设x是符号串，把x自身连接n次得到字符串z，即z=xx···xx,称为符号串x的方幂，写作z=x²。


    xº=ε。

4）符号串集合

    指定字母表Σ之后，可用Σ*表示Σ上的所有有穷长的串的集合。


    例如：Σ={0,1}，则Σ*={ε，0,1,00,01,10,11,000,001,010，···}，也可表示为字母表的方幂形式：Σ*=Σº∪Σ¹∪Σ²···∪Σⁿ···


    A*：A的*闭包。


    A⁺：A的正闭包。(不含空串ε)。

---

文法：

    文法G定义为四元组（V_N,V_T,P,S）。




  其中V_N为非终结符（或语法实体，或变量）集；


  V_T为终结符集；


  P为规则（α→β）的集合；


  V_N,V_T和P是非空有穷集；


  S称作识别符或开始符，他是一个非终结符，至少要在一条规则中作为左部出现。




    V_N:非终结符集合，用尖括号括起来，大写字母表示。


    V_T:终结符集合，不用尖括号括起来，小写字母表示。