文法介绍
乔姆斯基于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型
0型
短语文法，图灵机
- 产生式形如：
[alpha
ightarrow eta
]
- 其中：
[alpha in (V_T cup V_N)*且至少含有一个非终结符\eta in (V_T cup V_N)*
]
1型
上下文有关文法，线性界限自动机
- 产生式形如：
[alpha
ightarrow eta
]
- 其中：
[|alpha|le|eta|,仅S
ightarrow epsilon
]
1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符
2型
上下文无关文法，非确定下推自动机
- 产生式形如：
[A
ightarrow eta
]
- 其中：
[A in V_N; space eta in (V_T cup V_N)*
]
3型
正规文法，有限自动机
右线性文法
- 产生式形如：
[A
ightarrow alpha B space或 A
ightarrow alpha
]
- 其中：
[alpha in V_T*; space A,B in V_N
]
左线性文法
- 产生式形如：
[A
ightarrow B alpha space 或 A
ightarrow alpha
]
- 其中：
[alpha in V_T*; space A,B in V_N
]