正则文法
维基百科，自由的百科全书
在计算机科学中，正规文法是产生式规则取下述形式的一种形式文法 (N, Σ, P, S) ：
- A -> a ，此处的 A 是 N 中的非终结符号，a 是 Σ 中的终结符号；
- A -> aB ，此处的 A 和 B 是 N 中的非终结符号，a 是 Σ 中的终结符号；
- C -> ε ，此处的 C 是 N 中的非终结符号。
下面给出一个正规文法的例子： 文法 G = (N, Σ, P, S)，其中 N = {S, A}，Σ = {a, b, c}，S 是起始符号，P 包含下述规则：
- S -> aS
- S -> bA
- A -> ε
- A -> cA
这个文法描述的语言也可以用正则表达式 a*bc* 来表达。
正规文法描述的语言构成了正规语言类，正规语言类中的语言也可以由有限状态自动机或正则表达式来表达。
[编辑] 相关条目
| 自动机理论: 形式语言和形式文法 | |||
|---|---|---|---|
| 乔姆斯基层级 | 文法 | 语言 | 极小自动机 |
| 类型 0 | 无限制 | 递归可枚举 | 图灵机 |
| n/a | (无公用名) | 递归 | 判定器 |
| 类型 1 | 上下文有关 | 上下文有关 | 线性有界 |
| n/a | 附标 | 附标 | 嵌套堆栈 |
| n/a | 树-邻接 | 适度上下文有关 | 嵌入下推 |
| 类型 2 | 上下文无关 | 上下文无关 | 非确定下推 |
| n/a | 确定上下文无关 | 确定上下文无关 | 确定下推 |
| 类型 3 | 正则 | 正则 | 有限 |
| 每个语言或文法范畴都是其直接上面的范畴的真子集。 | |||
