Table of Contents
- From finite-state limits to recursion
- The arithmetic grammar
- The four parts of a CFG
- Shorthand, derivations, and zero steps
- The deck's Q/H membership problem
- CFLs and regular languages
- Generating E with S→aSb | epsilon
- Design with recursive plans and invariants
- Palindrome grammar
- Balanced-braces grammar
- Equal numbers of a and b
- Recursion needs an exit
- Derivations and parse structure
- Executable self-check
- Material limits
- Update log
- References
🌏 中文版
This is article 21 in the Stanford CS103 guide, corresponding to official Lecture 19, Spring 2026 (2026-05-13). The course team was Cynthia Bailey Lee and Alex Aiken. The public page does not name a speaker for each meeting, so this article does not guess. The lecture page and complete slides are public; recordings and transcripts require Canvas/Panopto access and were not used.
The official topic is Context-Free Languages. CS103 is not best read as a vocabulary list. For each topic, ask how the object is defined, which inputs are legal, what the claim demands, and what argument could support the conclusion. This article follows the definitions and examples visible in the deck and does not invent spoken material.
From finite-state limits to recursion
The deck moves from infinite distinguishing sets to arithmetic syntax. Legal expressions have unbounded length and nesting, so a fixed Mad Libs shape cannot describe them all. Recursive rules can: an expression is an integer, two expressions joined by an operator, or a parenthesized expression. A finite rule set can therefore generate arbitrary depth.
The arithmetic grammar
The rules are Expr → int | Expr Op Expr | (Expr) and Op → + | - | × | /. Expr and Op are nonterminals, placeholders still expandable. The other symbols are terminals retained in the final string. A derivation of int × (int + int) repeatedly replaces one nonterminal; expansion order may vary while the final terminal string remains the same.
The four parts of a CFG
A CFG consists of a nonterminal set, terminal alphabet Sigma, production rules, and a nonterminal start symbol. A production A→omega replaces one nonterminal with a finite string of terminals and nonterminals, possibly epsilon. “Context-free” means replacement does not depend on surrounding symbols. Separate occurrences of the same nonterminal expand independently.
Shorthand, derivations, and zero steps
Write alternatives with a vertical bar. One replacement is ⇒; zero or more is ⇒*, so alpha derives itself in zero steps. For start S,
L(G)={omega in Sigma-star | S ⇒* omega}.
Omega must contain terminals only. A sentential form still containing H is not a language element. Grammar and generated language are different types.
The deck's Q/H membership problem
For Q→Qa | dH and H→bHb | c, Q accumulates trailing a's, then becomes dH; H places matched b's around c. Thus L(G)={d b^n c b^n a^m | m,n natural}. dca and dc belong; bcb lacks d, cad has wrong order, and ddHaa still contains a nonterminal.
CFLs and regular languages
L is context-free if some CFG generates it. CFG syntax has no regex star or union: S→a*b literally generates the one string a*b. Repetition requires recursion.
Every regular language is context-free. The deck translates a(b∪epsilon)c to S→aXc, X→b|epsilon. It translates (a∪b)^2c* using S→XY, X→ZZ, Z→a|b, Y→cY|epsilon. Structural translation handles all regexes.
Generating E with S→aSb | epsilon
Every recursive step adds one a on the left and one b on the right; epsilon terminates. Four steps produce aaaabbbb. Therefore every generated word has form a^n b^n, and every n is generated by exactly n recursive steps followed by epsilon. Since the previous lecture proved this language nonregular, regular languages form a proper subset of CFLs. Unbounded derivation depth supplies the matching memory.
Design with recursive plans and invariants
Think recursively, choose a construction order, and let each nonterminal represent useful information. Correctness has two directions: soundness excludes strings outside the target; completeness generates every target string. Positive derivations alone establish neither equality nor completeness.
Palindrome grammar
Over {a,b}, use S→epsilon | a | b | aSa | bSb. Epsilon and one-letter strings are bases; recursive steps wrap a smaller palindrome in equal symbols. Epsilon ends even lengths and a or b ends odd lengths. Removing equal endpoints from any nontrivial palindrome proves completeness. For example, S⇒aSa⇒abSba⇒abba.
Balanced-braces grammar
Any nonempty balanced string begins with {; its matching } divides the string into balanced interior x and balanced remainder y. Therefore S→{S}S | epsilon. The first S generates nesting and the second concatenated groups. This directly supports induction for both soundness and completeness and handles {}{} as well as nested braces.
Equal numbers of a and b
The deck compares candidates. S→aSb|bSa|epsilon preserves equal counts but misses arrangements; S→abS|baS|epsilon requires adjacent pairs; S→abSba|baSab|epsilon is narrower still. S→SbaS|SabS|epsilon uses two independent balanced pieces around one a/b pair and supports a fuller recursive decomposition. An invariant proves only soundness; tests such as aabb, bbaa, and abba expose missing completeness.
Recursion needs an exit
S→aSb never removes S, so it derives no terminal string and its language is empty. Add epsilon as a base. Also, S→X≟X, X→aX|epsilon does not synchronize the two X occurrences; it generates a^m≟a^n for independent m,n. To match counts use one nested recursion such as S→aSa|≟.
Derivations and parse structure
Expanding left or right first can yield different derivation sequences for one tree; that alone is not ambiguity. The arithmetic rule Expr→Expr Op Expr does permit different groupings for int-int-int because it does not encode precedence or associativity. A parse tree places the start at the root, production symbols as children, and terminal output at the leaves. The lecture focuses on generation, but the tree exposes recursive structure.
Executable self-check
Derive int × (int + int) one nonterminal per step. Classify dca, dc, cad, bcb, and ddHaa using the Q/H invariant. Derive palindrome abba and balanced braces {{}{}}{}, then exclude aab and }{ by invariants. Repair S→aSb, test n=0, and explicitly derive a≟aaa from S→X≟X to confirm independent expansion.
Material limits
The public deck explicitly supports the sections on from finite-state limits to recursion and the arithmetic grammar. It does not preserve spoken transitions or class discussion, so those details are left unattributed rather than reconstructed.
Update log
- 2026-08-22: Rechecked from finite-state limits to recursion against the official deck, removed dead handout links, and revised metadata and wording after clean review.
References
Loading...