|
Chomsky categorized grammars by their ability to generate symbols
in a language. This hierarchy is shown below:
| Type of Grammar |
Constraints |
Automata (Language Model) |
|
Phrase Structure
|
A -> B
|
Turing Machine
(Unrestricted)
|
|
Context Sensitive
|
aAb -> aBb
|
Linear Bounded Automata
(N-grams, Unification)
|
|
Context Free
|
A -> B
Constraint:
A is a non-terminal.
Equivalent to:
A -> w
A -> BC
where "w" is a terminal;
B,C are non-terminals
(Chomsky normal form)
|
Push down automata
(JSGF, RTN, Chart Parsing)
|
|
Regular
|
A -> w
A -> wB
(Subset of CFG)
|
Finite-state automata
(Network decoding)
|
The grammars are listed from top to bottom in
order of descending generative power. For each grammar, the table
gives constraints on the complexity of language it can
represent and the automata (language model) that can recognize
symbols in that language. Language models used for speech recognition
include Network decoding, JSGF, and N-Grams. ISIP supports each of
these language models. Jump ahead to Section 6.2.1 to learn more about these.
|
