next up previous
Next: What is a context-free Up: Machines and their languages Previous: Applying the pumping lemma


Context free grammars

We will now introduce context free grammars (CFGs) as a formalism to define languages. CFGs are more general than regular expressions, i.e. there are more languages definable by CFGs (called type-2-languages). We will define the corresponding notion of automata, the push down automata (PDA) later.



Subsections

Thorsten Altenkirch 2001-05-08