Context-free grammar

Mathematical statement

Each right side is a finite string over terminal and nonterminal symbols, with the epsilon convention explicit. A derivation is a finite production sequence. The generated language contains only terminal-only words derivable from the start. The empty language is not a language containing epsilon. A derivation witness proves membership, but bounded-search failure does not prove nonmembership. Unambiguity, regularity and CFG-PDA equivalence do not follow automatically.

Representative formula (exact TeX)

G(N,T)

Assumptions

• Nonterminal and terminal alphabets are finite, unique and disjoint.
• Every production has exactly one nonterminal lhs and a rhs of legal symbols.

Symbol scope

• G — context-free grammar
• N — nonterminal alphabet
• T — terminal alphabet

Intuition, definition, and misconceptions

Separate grammar qualification from derivation validation.

A valid derivation ending in a terminal-only word supplies a membership witness.

Bounded-search failure is not a nonmembership proof.

Failure to find a derivation at finite depth does not prove nonmembership; an empty language is different from one containing epsilon.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Abstract computational model — A grammar has an execution model.
• Set — Alphabets and productions are sets.
• Sequence — Strings and derivations are finite sequences.

Verification boundary

This slice makes no ambiguity, regularity or CFG-PDA equivalence claim.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add pushdown automata and parsing.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.