# Context-free grammar

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A CFG uses finite disjoint nonterminal and terminal alphabets, a start symbol and finite productions with a single nonterminal on each left side.

mko-context-free-grammar · definition · v0.10.0



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

[A CFG production list and derivation witness](https://ocme.evemisslab.com/en/derivations/derivation-mko-context-free-grammar-01/)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](https://ocme.evemisslab.com/en/mko/mko-computational-model/) — A grammar has an execution model.
- [Set](https://ocme.evemisslab.com/en/mko/mko-set/) — Alphabets and productions are sets.
- [Sequence](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/context-free-grammar.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-context-free-grammar/index.md)