|
|
|
|
Chomsky hierarchy
|
(Definition)
|
|
|
The Chomsky hierarchy or Chomsky-Schützenberger hierarchy is a way of classifying formal grammars into four types, with the lower numbered types being more general.
Recall that a formal grammar $G=(\Sigma,N,P,\sigma)$ consists of an alphabet $\Sigma$ , an alphabet $N$ of non-terminal symbols properly included in $\Sigma$ , a non-empty finite set $P$ of productions, and a symbol $\sigma\in N$ called the start symbol. The non-empty alphabet $T:=\Sigma-N$ is the set of terminal symbols. Then $G$ is called a
- Type-0 grammar
- if there are no restrictions on the productions. Type-0 grammar is also known as an unrestricted grammar, or a phrase-structure grammar.
- Type-1 grammar
- if the productions are of the form $uAv \to uWv$ , where $u,v,W\in \Sigma^*$ with $W\ne \lambda$ , and $A\in N$ , or $\sigma\to \lambda$ , provided that $\sigma$ does not occur on the right hand side of any productions in $P$ . As $A$ is surrounded by words $u,v$ , a type-1 grammar is also known as a context-sensitive grammar.
- Type-2 grammar
- if the productions are of the form $A\to W$ , where $A\in N$ and $W\in \Sigma^*$ . Type-2 grammars are also called context-free grammars, because the left hand side of any productions are ``free'' of contexts.
- Type-3 grammar
- if the productions are of the form $A\to u$ or $A\to uB$ , where $A,B\in N$ and $u\in T^*$ . Owing to the fact that languages generated by type-3 grammars can be represented by regular expressions, type-3 grammars are also known as regular grammars.
It is clear that every type-$i$ grammar is type-0, and every type-3 grammar is type-2. A type-2 grammar is not necessarily type-1, because it may contain both $\sigma\to \lambda$ and $A\to W$ , where $\lambda$ occurs in $W$ . Nevertheless, the relevance of the hierarchy has more to do with the languages generated by the grammars. Call a formal language a type-$i$ language if it is generated by a type-$i$ grammar, and denote
the family of type-$i$ languages. Then it can be shown that
where each inclusion is strict.
Below is a table summarizing the four types of grammars, the languages they generate, and the equivalent computational devices accepting the languages.
|
"Chomsky hierarchy" is owned by CWoo. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
| Other names: |
Chomsky-Schützenberger hierarchy, Chomsky-Schutzenberger hierarchy, unrestricted grammar |
| Also defines: |
type-0 grammar, type-0 language |
|
|
Cross-references: finite, pushdown automaton, context-free, linear bounded automaton, context-sensitive, Turing machine, recursively enumerable, automaton, generate, strict, inclusion, formal language, occur ins, contain, clear, regular grammars, regular expressions, type-3 grammars, generated by, languages, left hand side, context-free grammars, type-2 grammars, context-sensitive grammar, type-1 grammar, right hand side, restrictions, productions, finite set, alphabet, types
There are 14 references to this entry.
This is version 10 of Chomsky hierarchy, born on 2006-12-08, modified 2009-07-25.
Object id is 8607, canonical name is ChomskyHierarchy.
Accessed 5002 times total.
Classification:
| AMS MSC: | 68Q15 (Computer science :: Theory of computing :: Complexity classes ) | | | 03D55 (Mathematical logic and foundations :: Computability and recursion theory :: Hierarchies) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|