Context-free Grammars and Derivations
Learn about context-free grammar and look at some examples.
We'll cover the following
- Context-free grammar
- Examples of CFGs
Let’s formally define context-free grammar (CFG).
Context-free grammar
A context-free grammar is a formal grammar consisting of the following:
- A set of variables (i.e., a nonterminal alphabet), V V V , one of which is a start variable.
- An alphabet, Σ \Sigma Σ , of terminal symbols.
- A set of production rules of the form v → s v\rightarrow s v → s , where v ∈ V v\in V v ∈ V and s ∈ ( V ∪ Σ ) ∗ s\in (V\cup\Sigma)^* s ∈ ( V ∪ Σ ) ∗ , a string of terminals and/or variables.
Let’s look at some illustrations of CFGs for some of the languages.
Examples of CFGs
The following CFG generates the language < a n b n ∣ n >0 > \0\> < a n b n ∣ n >0 > :
