Automata Theory 简明教程
Chomsky Classification of Grammars
根据诺姆·乔姆斯基，语法有四种类型——第 0 类、第 1 类、第 2 类和第 3 类。下表显示了它们彼此之间的差异 -
According to Noam Chomosky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other −
Grammar Type |
Grammar Accepted |
Language Accepted |
Automaton |
Type 0 |
Unrestricted grammar |
Recursively enumerable language |
Turing Machine |
Type 1 |
Context-sensitive grammar |
Context-sensitive language |
Linear-bounded automaton |
Type 2 |
Context-free grammar |
Context-free language |
Pushdown automaton |
Type 3 |
Regular grammar |
Regular language |
Finite state automaton |
看看以下插图。它显示了每种语法类型的范围 -
Take a look at the following illustration. It shows the scope of each type of grammar −
Type - 3 Grammar
q4 生成正则语言。Type-3 语法必须在左侧有一个非终结符，在右侧有一个终结符或一个终结符后跟一个非终结符。
Type-3 grammars generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.
产生式必须采用以下形式 Type-3 grammars
The productions must be in the form X → a or X → aY
其中 X → a or X → aY （非终结符）
where X, Y ∈ N (Non terminal)
和 X, Y ∈ N （终结符）
and a ∈ T (Terminal)
规则 a ∈ T 被允许，如果 S → ε 不出现在任何规则的右侧。
The rule S → ε is allowed if S does not appear on the right side of any rule.
Type - 2 Grammar
Type-2 grammars 生成上下文无关语言。
Type-2 grammars generate context-free languages.
产生式应为 A → γ 形式
The productions must be in the form A → γ
其中*A ∈ N*（非终结符）
where * A ∈ N* (Non terminal)
和 γ ∈ (T ∪ N) *（终结符和非终结符串）。
and γ ∈ (T ∪ N)* (String of terminals and non-terminals).
由这些语法生成的这些语言可被非确定性下推自动机识别。
These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.
Type - 1 Grammar
Type-1 grammars 生成上下文相关语言。产生式应为
Type-1 grammars generate context-sensitive languages. The productions must be in the form
α A β → α γ β
α A β → α γ β
其中 A ∈ N （非终结符）
where A ∈ N (Non-terminal)
和 α, β, γ ∈ (T ∪ N) *（终结符和非终结符串）。
and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals)
字符串 α 和 β 可为空，但 γ 必须非空。
The strings α and β may be empty, but γ must be non-empty.
如果 S 未出现在任何规则的右侧，则规则 S → ε 是允许的。由这些语法生成的语言被线性有界自动机所识别。
The rule S → ε is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.
Type - 0 Grammar
Type-0 grammars 递归生成可枚举的语言。产生式没有任何限制。它们是包括所有形式文法的任意相结构语法。
Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.
它们生成被图灵机识别的语言。
They generate the languages that are recognized by a Turing machine.
产生式可以 α → β 的形式出现，其中 α 是至少有一个非终结符的终结符和非终结符字符串，而 α 不能为 null。 β 是终结符和非终结符字符串。
The productions can be in the form of α → β where α is a string of terminals and nonterminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.