I. Definition

A context-free grammar is a notation for describing languages.

• Language: Context-free language
• Automata: Push-down Automata

It is more powerful than finite automata or RE’s, but still cannot define all possible languages.

Useful for nested structures, e.g., parentheses in programming languages.

<aside> 💡 Basic Idea: use “variables” to stand for sets of strings

• Variables are defined recursively, in terms of one another
• Recursive rules / “productions” involve only concatenation
• Alternative rules for a variable allow union </aside>

1. Formalism

$$ G = (V,T,P,S) $$

• Variables = nonterminals, V a finite set of other symbols, each of which represents a language.
• Terminals, T symbols of the alphabet of the language being defined.
• Productions, P variable (head) → string of variables and terminals (body)
• Start symbol, S the variable whose language is the one being defined.

Convention

• A, B, C,… and also S are variables.
• a, b, c,… are terminals.
• …, X, Y, Z are either terminals or variables.
• …, w, x, y, z are strings of terminals only.
• $\alpha$, $\beta$, $\gamma$,… are strings of terminals and/or variables.

II. Derivations

1. Derivations

We say $\alpha A\beta \Rightarrow \alpha \gamma \beta$, if $A \rightarrow \gamma$ is a production