# 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-