Editing Chomsky hierarchy (section)

===Context-free (Type-2) grammars===
{{main|Context-free grammar}}

Type-2 grammars generate the [[context-free language]]s. These are defined by rules of the form <math>A \rightarrow \alpha</math> with <math>A</math> being a nonterminal and <math>\alpha</math> being a string of terminals and/or nonterminals. These languages are exactly all languages that can be recognized by a non-deterministic [[pushdown automaton]]. Context-free languages—or rather its subset of [[deterministic context-free language|deterministic context-free languages]]—are the theoretical basis for the phrase structure of most [[programming language]]s, though their syntax also includes context-sensitive [[Name resolution (programming languages)|name resolution]] due to declarations and [[Scope (computer science)|scope]]. Often a subset of grammars is used to make parsing easier, such as by an [[LL parser]].

For example, the context-free language  <math>L = \{a^nb^n \mid n > 0\}</math> is generated by the Type-2 grammar <math>G = (\{S\}, \{a, b\}, P, S)</math> with the productions <math>P</math> being the following.

:{{math|''S'' → ''aSb''}}
:{{math|''S'' → ''ab''}}

The language is context-free but not regular (by the [[pumping lemma for regular languages]]).