Slide 2.2: The Chomsky hierarchy
Slide 2.4: Context-free grammars vs regular grammars
Home

The Chomsky Hierarchy (Cont.)

Type-2 Grammars: Context-Free Grammars
Type-2 grammars correspond to the BNF grammars and play a major role in defining programming languages. They prescribe that the left side be a single nonterminal producing rules of the form “<A> ::= α”, such as 
   <S> ::= a <S> | a <S> b <S> | ε

Type-1 Grammars: Context-Sensitive Grammars
They have the restriction that the right side contains no fewer symbols than the left side—for example, a rule of the form 
   <thing> b ::= b <thing>
Equivalently, context-sensitive grammars can be built using only productions of the form “α <B> γ ::= αβγ”. These rules are called context-sensitive because the replacement of a nonterminal by its definition depends on the surrounding symbols.

The language generated by this grammar consists of strings having equal number a's, b's, and c's in that order—namely, the set { abc, aabbcc, aaabbbccc, ... }. 
<sentence> ::= abc | a<thing>bc
<thing>b   ::= b<thing>
<thing>c   ::= <other>bcc 
a<other>   ::= aa | aa<thing> 
b<other>   ::= <other>b

Notice that when replacing the nonterminal <thing>, the terminal symbol following the nonterminal determines which rule can be applied. This causes the grammar to be context-sensitive. In fact, a result in computation theory asserts that no context-free grammar produces this language.

Type-0 Grammars: Unrestricted Grammars
They are the most general grammars that require only that at least one nonterminal occur on the left side of a rule, “α ::= β”—for example, 
   a <thing> b ::= b <another thing>