Context-Free Grammars (CFG)

Context: FIT2014_MOC · a generative device — build strings from a start symbol via rules · strictly more powerful than Regular Expressions, reaching the languages the pumping lemma ruled out

Quick Revision

• 🎯 Objective: a finite set of production rules rewrites nonterminals into strings of terminals/nonterminals ➔ the language generated is every terminal string derivable from the start symbol $S$.
• ⚡ Key Constraint: rules replace one nonterminal at a time regardless of context (hence “context-free”); a rule’s left side is always a single nonterminal.

📝 The three ingredients

A context-free grammar consists of:

1. An alphabet ➔ its letters are the terminals (the symbols of the final strings).
2. A set of nonterminals ➔ often upper-case letters; one is the start symbol (usually $S$).
3. A finite set of production rules of the form $\text{one nonterminal}⟶\text{finite string of terminals and/or nonterminals}$

• Language generated ➔ the set of strings producible from the start symbol using the rules.
• Context-Free Language (CFL) ➔ any language generated by some CFG.

✍️ Backus–Naur Form (BNF)

• Shorthand ➔ collapse rules with the same left side using $\mid$ for “or”: $S\to AA\to \text{integer}\mid A+A\mid A-A\mid A\ast A\mid A/A\mid (A)$
• Origin ➔ Backus & Naur used it to define ALGOL 60; it is still how programming-language syntax is specified.
• From an inductive definition ➔ “all integers are arithmetic expressions; if $A,B$ are, so are $A+B$, $A-B$, …” maps directly onto production rules — the standard way to invent a grammar.

🧩 Worked grammar — EQUAL (equal $\mathtt{a}$s and $\mathtt{b}$s)

Terminals $\{\mathtt{a},\mathtt{b}\}$; nonterminals $S,A,B$:

$$\begin{array}{rl}S& \to \epsilon \mid \mathtt{b}A\mid \mathtt{a}B\\ A& \to \mathtt{a}\mid \mathtt{a}S\mid \mathtt{b}AA\text{(A = an "a-type" string: one more a than b)}\\ B& \to \mathtt{b}\mid \mathtt{b}S\mid \mathtt{a}BB\text{(B = a "b-type" string: one more b than a)}\end{array}$$

• Design idea ➔ classify strings by their running imbalance ($\epsilon$, one-more-$\mathtt{a}$, one-more-$\mathtt{b}$) and give each class a nonterminal — the general trick for building grammars.
• Note ➔ EQUAL is non-regular (Proving a Language Non-Regular) yet context-free — the first concrete language separating the two classes.

🕰️ History

• Pāṇini (~5th c. BC) ➔ rule-based grammar of Sanskrit — the ancient ancestor.
• Chomsky ➔ formalised grammars for natural languages.
• Backus ➔ applied them to programming languages (ALGOL).

⚠️ Common Mistakes

• 💡 Left side is a single nonterminal ➔ that restriction is what makes a grammar context-free; a rule like $aA\to \dots$ (context on the left) is a different, more powerful class.
• 💡 $\epsilon$-rules are allowed ➔ $S\to \epsilon$ is a legitimate production and is how the empty word enters a language.
• 💡 Terminals vs nonterminals ➔ terminals appear in the final string; nonterminals are scaffolding that must all be rewritten away. A “derivation” isn’t finished while a nonterminal remains.
• 💡 A grammar generates, an automaton recognises ➔ CFGs build strings top-down; the matching machine is the PDA, which reads strings.

🧠 Active Recall

What are the three components of a CFG, and what does "context-free" refer to?

Answer

• Short answer: an alphabet of terminals, a set of nonterminals (one being the start symbol $S$), and a finite set of production rules each rewriting one nonterminal into a string of terminals and/or nonterminals.
• Why: Single-nonterminal left side ➔ “context-free” means a nonterminal may be replaced wherever it occurs, independent of surrounding symbols — the left-hand side is always exactly one nonterminal, never a nonterminal flanked by context.

Why does the existence of a CFG for EQUAL matter, given EQUAL is non-regular?

Answer

• Short answer: it demonstrates that the context-free languages strictly contain the regular languages — EQUAL cannot be described by any regex or finite automaton, yet a three-nonterminal CFG generates it.
• Why: Grammars have unbounded memory via recursion ➔ nonterminals like $A\to \mathtt{b}AA$ can track arbitrary counts that a finite automaton’s fixed states cannot, which is exactly the counting power the pumping lemma showed regular languages lack.