文法

文法由四部分组成(四元组(VN,VT,P,S))

  1. VN：非终结符，通常用大写字母表示
  2. VT：终结符，通常用小写字母表示
  3. P：产生式集合（规则集合）
  4. S：开始符号（识别符号）

0型文法（短语文法，图灵机）

  1. 设G=(VN,VT,PS)

  2. 产生式形式：α->β

  3. 其中α∈（VN∪VT）*且至少含有一个非终结符

  4. β∈（VN∪VT）*

  5. 则G是一个0型文法

  6. 0型文法的能力相当于图灵机，任何0型文法都是递归可枚举

1型文法（上下文有关文法，线性界限自动机）

  1. 在0型文法的基础上每一个α->β都有|β|>=|α|,其中||表示长度仅S->ε例外
  2. 这种文法意味着，对非终结符进行替换时务必考虑上下文，并且一般不允许替换为空串ε

2型文法（上下文无关文法，非确定下推自动机）

  1. 2型文法实在1型文法的基础上，再满足：每一个α->β都是α是一个非终结符。
  2. 产生式如下：A->β（左边部分必须为且仅为一个非终结符）

3型文法（正规文法，有限自动机）

  1. 在2型文法的基础上满足，A->α|αB（右线性）或A->α|Bα（右线性）
  2. 3型文法只能满足右线性或者做线性，不能两种同时都有