Chomsky hierarchy
E644
concept in formal language theory
concept in theoretical computer science
formal language classification scheme
hierarchy of formal grammars
The Chomsky hierarchy is a classification of formal grammars into four types that correspond to increasing levels of generative power and computational complexity in formal language theory.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Chomsky–Schützenberger hierarchy | 1 |
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
concept in formal language theory
ⓘ
concept in theoretical computer science ⓘ formal language classification scheme ⓘ hierarchy of formal grammars ⓘ |
| alternativeName |
Chomsky hierarchy
ⓘ
surface form:
Chomsky–Schützenberger hierarchy
|
| assumes | grammars generate formal languages ⓘ |
| characterizes | constraints on grammar production rules ⓘ |
| correspondsToAutomatonModel |
Turing machine
ⓘ
finite automaton ⓘ linear bounded automaton ⓘ pushdown automaton ⓘ |
| correspondsToLanguageClass |
context-free languages
ⓘ
context-sensitive languages ⓘ recursively enumerable languages ⓘ regular languages ⓘ |
| definesOrderingOf | formal grammar types ⓘ |
| field |
automata theory
ⓘ
formal language theory ⓘ mathematical linguistics ⓘ theoretical computer science ⓘ |
| hasLevel |
Type-0 grammar
ⓘ
Type-1 grammar ⓘ Type-2 grammar ⓘ Type-3 grammar ⓘ |
| hasLevelCount | 4 ⓘ |
| hasTopLevel | Type-0 grammar ⓘ |
| hasTypeName |
Type-0
ⓘ
Type-1 ⓘ Type-2 ⓘ Type-3 ⓘ |
| impliesInclusion |
context-free languages are a subset of context-sensitive languages
ⓘ
context-sensitive languages are a subset of recursively enumerable languages ⓘ regular languages are a subset of context-free languages ⓘ |
| introducedBy | Noam Chomsky ⓘ |
| introducedInContext | generative grammar ⓘ |
| namedAfter | Noam Chomsky ⓘ |
| ordersBy |
computational complexity
ⓘ
generative power ⓘ |
| relatesConcept |
automaton
ⓘ
formal grammar ⓘ formal language ⓘ language recognition power ⓘ |
| usedIn |
analysis of natural language syntax
ⓘ
classification of programming language grammars ⓘ complexity analysis of language recognition ⓘ design of parsers ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Chomsky–Schützenberger hierarchy