Chomsky hierarchy: различия между версиями

(0) '''[[Grammar of type 0|Type-0 grammars]]''' (or '''[[unrestricted grammar|unrestricted grammars]]''') include all formal ''[[grammar|grammars]]'' They generate exactly all languages that can be recognized by ''[[Turing machine]]'' These languages are also known as the ''[[recursively enumerable language|recursively enumerable languages]]''.

(1) '''Type-1 grammars''' ('''[[context-sensitive grammar|context-sensitive grammars]]''', or '''[[CS-Grammar|CS-grammars]]''') generate the '''[[context-sensitive language|context-sensitive languages]]''' (or '''[[CS-language|CS-languages]]'''). These grammars have rules of the form  <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>, where <math>A</math> is  a nonterminal and <math>\alpha,\beta,\gamma</math> are strings of terminals and nonterminals. The strings <math>\alpha</math> and <math>\beta</math> may be empty, but <math>\gamma</math> must be nonempty. The rule  <math>S\rightarrow e</math> is allowed if <math>S</math> does not appear in the right-hand side of any rule. The languages described by these grammars are exactly all languages that can be recognized by ''[[linear-bounded automation|linear bounded automata]]''.

(2)  '''Type-2 grammars''' ('''[[context-free grammar|context-free grammars]]''' or '''[[CF-grammar|CF-grammars]]''') generate the '''[[context-free language|context-free languages]]''' (or '''[[CF-Language|CF-languages]]'''). These grammars contain rules of the form <math>A \rightarrow \alpha</math>, where <math>A</math> is a nonterminal and <math>\alpha</math> is a string of terminals and nonterminals. These languages are exactly all languages that can be recognized by ''[[nondeterministic pushdown automaton|nondeterministic pushdown automata]]'' Context-free languages are the theoretical basis for the syntax of most programming languages.

(3) '''Type-3 grammars''' ('''[[regular grammar|regular grammars]]''') generate the '''[[regular language|regular languages]]'''. Such a grammar restricts its rules to a single nonterminal in the left-hand side and a right-hand side consisting of a single terminal, possibly followed (or preceded, but not both in the same grammar) by a single nonterminal. The rule  <math>S\rightarrow e</math> is also allowed here if <math>S</math> does not appear in the right-hand side of any rule. These are exactly all languages that can be recognized by ''[[finite state automata]]'' Additionally, this family of formal languages can be obtained by ''[[regular expressions]]'' Regular languages are commonly used to define the search patterns and lexical structure of programming languages.