context-free languages
(60 minutes to learn)
Summary
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.
Context
This concept has the prerequisites:
- context-free grammars (Context-free languages are those that can be defined by context-free grammars.)
- pushdown automata (Context-free languages can be recognized by pushdown automata.)
- regular languages (Context-free languages are a superclass of regular languages.)
Goals
- 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)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
Location:
Lecture "The pumping lemma for CFL's"
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 2.3, "Non-context-free languages," pages 123-128
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 7.2, "The Pumping Lemma for context-free languages," pages 279-287
See also
-No Additional Notes-