Recall that a formal grammar consists of an alphabet , an alphabet of non-terminal symbols properly included in , a non-empty finite set of productions, and a symbol called the start symbol. The non-empty alphabet is the set of terminal symbols. Then 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 , where with , and , or , provided that does not occur on the right hand side of any productions in . As is surrounded by words , a type-1 grammar is also known as a context-sensitive grammar.
- Type-2 grammar
if the productions are of the form , where and . Type-2 grammars are also called context-free grammars, because the left hand side of any productions are “free” of contexts.
- Type-3 grammar
It is clear that every type- 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 and , where occurs in . Nevertheless, the relevance of the hierarchy has more to do with the languages generated by the grammars. Call a formal language a type- language if it is generated by a type- grammar, and denote the family of type- 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.
|Date of creation||2013-03-22 16:27:04|
|Last modified on||2013-03-22 16:27:04|
|Last modified by||CWoo (3771)|