Our First Context Free Grammar

As was true of regular languages, which had both a machine model that recognized them and a grammar model that generated them, context free languages have grammars that generate them, too. They are called (surprise) context free grammars.

Context free grammars are the same sort of mathematical object as regular grammars: they have nonterminals, alphabet symbols (terminals), grammar rules, and a start symbol.  The difference between regular grammars and context free grammars lies in the forms that the grammar rules can take.

Regular grammar rules are restricted to one of the following forms

• A → aB
• A → a
• A → ε

for A, B ∈ N, a ∈ Σ, and ε the empty string.  That is, in a regular grammar, all rules must have a single nonterminal on the left while the right hand side can be only a single terminal followed by a single nonterminal, or a single terminal, or the empty string.

In a context free grammar, all grammar rules must have a nonterminal on the left but can have any mixture of nonterminals and terminals on the right.  Fromally, all context free grammar rules have the form

• A → α

for A ∈ N and α ∈ (N ∪ Σ)*

How much extra generating power does this give us?  Consider our old friend, the non-regular language

• L = {0ⁿ1ⁿ | n ≥  0}

We have seen that there is a PDA that recognizes this language, and we have already said the context free grammars produce the same class of languages as the PDA's, so there must be a context free grammar that generates L.  Indeed there is, and it is remarkably simple.  The following rules do the job.

S → 0 S 1
S → ε

Notice that there is a k+1 step derivation that produces any string 0^k1^k in this language:  apply rule 1 k times and rule 2 one time, at the end.

S $\stackrel{k}{\Rightarrow }$ 0^kS1^k ⇒ 0^k1^k

Pretty simple, huh?

Copyright © Rockford J. Ross 1991-2007