context-free languages

(60 minutes to learn)


Context-free languages are languages definable in terms of a context-free grammar, or equivalently, recognizable by a (nondeterministic) pushdown automaton. All regular languages are also context-free. Languages can be shown to be non-context-free using the Pumping Lemma for context-free languages.


This concept has the prerequisites:


  • From the fact that pushdown automata can simulate finite state automata, conclude that all regular languages are context-free.
  • Know the statement of the Pumping Lemma for context-free languages.
  • Prove the Pumping Lemma.
  • Be able to use the Pumping Lemma to prove that languages are not context-free.

Core resources (read/watch one of the following)


Coursera: Automata
An introductory course on automata and the theory of computation.
Author: Jeffrey D. Ullman


See also

-No Additional Notes-