Context-Free Grammar Ontology

FLOW ALGEBRA
CONTEXT-FREE GRAMMAR ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Formal Languages
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/context-free-grammar-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
STATUS: Formal mathematical synthesis; source page not independently verified.

1. PURPOSE
Represent context-free grammars (CFGs), derivations, parse trees, language membership, transformations and validation as typed, machine-consumable semantic relationships.

2. TYPED ENTITIES
Grammar := (N: FiniteSet[Nonterminal], T: FiniteSet[Terminal], P: FiniteSet[Production], S: Nonterminal)
Nonterminal := Symbol
Terminal := Symbol
Production := (lhs: Nonterminal, rhs: Sequence[Symbol])
SententialForm := Sequence[Symbol]
Derivation := Sequence[SententialForm]
ParseTree := RootedOrderedTree[Symbol]
Language := Set[Sequence[Terminal]]
Condition: N ∩ T = ∅; S ∈ N; each production lhs ∈ N and rhs ∈ (N ∪ T)*.
The empty sequence is ε. Empty-language ∅ and empty-string ε are distinct.

3. CORE OPERATIONS
GENERATE(G) := { w ∈ T* | S ⇒* w }
DERIVE_ONCE(α,A→β,γ) := replace one occurrence of A in αAγ with β, yielding αβγ.
DERIVE_STAR := reflexive-transitive closure of DERIVE_ONCE.
ACCEPT(G,w) := (w ∈ GENERATE(G)).
PARSE(G,w) := set of valid parse trees with root S and terminal yield w.
AMBIGUOUS(G) := ∃w ∈ GENERATE(G): |PARSE(G,w)| ≥ 2.
NULLABLE(A) := A ⇒* ε.
PRODUCTIVE(A) := ∃w ∈ T*: A ⇒* w.
REACHABLE(A) := A occurs in some sentential form derivable from S.

4. FORMAL LAWS AND INVARIANTS
CFG(G) ⇒ GENERATE(G) is context-free.
S ⇒* w with w ∈ T* ⇔ w ∈ GENERATE(G).
Every valid parse tree corresponds to a derivation and vice versa (up to derivation order).
If S ⇒* ε then ε ∈ GENERATE(G).
A grammar may be ambiguous even if its language has an unambiguous grammar.
Context-free languages are closed under union, concatenation and Kleene star.
Context-free languages are closed under intersection with regular languages.
Context-free languages are not closed under arbitrary intersection or complement.
Context-free language equivalence and universality are undecidable in general.
Membership for CFGs is decidable.

5. NORMAL FORMS AND TRANSFORMATIONS
CNF(G) := equivalent grammar whose productions are A→BC or A→a, optionally S0→ε when ε belongs to the language, with a fresh start symbol S0 not appearing on any RHS.
GNF(G) := equivalent grammar whose nonempty productions are A→aα with a ∈ T and α ∈ N*, with an appropriate optional start-to-ε production.
REMOVE_USELESS := eliminate unreachable or unproductive nonterminals without changing the generated language.
REMOVE_UNIT := eliminate unit productions A→B while preserving the language.
REMOVE_EPSILON := eliminate ε-productions while preserving the empty word via a designated start production if required.
VALIDATE_TRANSFORMATION(G,H) := assert GENERATE(G)=GENERATE(H); a transformation's declared preconditions must hold.

6. INFERENCE RULES
[PRODUCTION] (A→β)∈P ⇒ A⇒β.
[CONTEXT] α⇒β ⇒ xαy⇒xβy for x,y∈(N∪T)*.
[REFLEXIVE] α⇒*α.
[TRANSITIVE] α⇒*β ∧ β⇒*γ ⇒ α⇒*γ.
[MEMBERSHIP] S⇒*w ∧ w∈T* ⇒ ACCEPT(G,w).
[NULLABLE] A→ε ⇒ NULLABLE(A).
[NULLABLE_COMPOSITION] A→B1...Bk ∧ ∀i NULLABLE(Bi) ⇒ NULLABLE(A).
[AMBIGUITY_WITNESS] t1≠t2 ∧ t1,t2∈PARSE(G,w) ⇒ AMBIGUOUS(G).

7. EXAMPLE
N={S}; T={'(',')'}; P={S→SS, S→'(' S ')', S→ε}.
GENERATE(G) is the language of balanced parentheses.
S⇒'(' S ')'⇒'(' ')' demonstrates membership of "()".
The grammar is ambiguous: "()" has distinct parse trees from S→SS with an ε branch and from S→'(' S ')'.

8. SEMANTIC RELATIONSHIPS
ContextFreeGrammar IS_A FormalGrammar.
ContextFreeGrammar GENERATES ContextFreeLanguage.
ProductionRule REWRITES Nonterminal.
Derivation USES ProductionRule.
ParseTree REPRESENTS DerivationStructure.
PushdownAutomaton RECOGNISES ContextFreeLanguage.
ChomskyNormalForm IS_NORMAL_FORM_OF ContextFreeGrammar.
Terminal IS_MEMBER_OF TerminalAlphabet.
Nonterminal IS_MEMBER_OF NonterminalSet.

9. SEMANTIC_EQUIVALENCE
CFG ≡ Type2Grammar (Chomsky hierarchy terminology).
GENERATE(G) ≡ L(G).
A→α ≡ production with left-hand nonterminal A and right-hand sentential form α.
Grammar equivalence G1 ≡L G2 means L(G1)=L(G2), not identical production sets.
Parse-tree equivalence and language equivalence are different relations.

10. VALIDATION
CHECK_FINITE(N,T,P).
CHECK_DISJOINT(N,T).
CHECK_START(S∈N).
CHECK_PRODUCTIONS(∀(A→α)∈P: A∈N ∧ α∈(N∪T)*).
CHECK_DERIVATION(each step uses exactly one production in a valid context).
CHECK_PARSE_TREE(root=S, internal expansions match P, leaves yield w).
CHECK_EPSILON_HANDLING(ε not treated as a terminal symbol).
CHECK_LANGUAGE_CLAIMS(undecidable questions must not be labelled generally decidable).

11. CONFIDENCE
Formal definitions and established closure/decidability properties: HIGH.
Example membership and ambiguity witness: HIGH.
Unverified alignment with source-page wording: NOT_ASSESSED.
Confidence measures evidence quality, not the truth value of a theorem.

12. FLOW_HASH
HASH_INPUT := canonical UTF-8 representation of ontology ID, version, typed entities, axioms, inference rules and source URL.
FLOW_HASH := SHA-256(HASH_INPUT) computed on publication; no uncomputed digest is asserted here.

13. UPDATE_MODEL
On change: increment version; record changed entities, rules and provenance; re-run grammar and derivation validation; recompute FLOW_HASH; preserve historical versions.
Do not infer formal equivalence from matching terminology alone.

14. AI_CONSUMPTION
INPUT: {grammar, optional_string, task: validate|derive|parse|membership|normalise|compare}.
OUTPUT: {result, witness_or_proof, preconditions, validation_status, confidence, provenance}.
For undecidable general questions, return UNKNOWN/UNDECIDABLE rather than fabricate a decision.
For grammar transformations, preserve ε-membership and explicitly document any fresh start symbol.

END FLOW ALGEBRA