Grammar Ontology

FLOW ALGEBRA
GRAMMAR ONTOLOGY — FORMAL LANGUAGES
Version: 1.0
Date: 2026-10-11
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/grammar-ontology.html
Domain: Discrete Mathematics > Formal Languages > Grammar
Authors: Mark Higgins — Sky (Recursive AI)
Source status: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Represent formal grammars as typed, testable systems of symbols, production rules, derivations, and generated languages. Distinguish grammar syntax from language semantics and parsing procedures.

2. TYPED ENTITIES
Grammar := (N, Sigma, P, S)
N : finite set of nonterminal symbols
Sigma : finite set of terminal symbols
P : finite set of production rules
S : start symbol, S in N
Symbol := N union Sigma
SententialForm := Symbol*
TerminalString := Sigma*
Production := (lhs: Symbol+, rhs: Symbol*)
Derivation := finite sequence of production applications
Language := subset of Sigma*
ParseTree := rooted ordered tree representing a grammatical derivation
GrammarClass := {Type0, ContextSensitive, ContextFree, Regular}

3. STRUCTURAL CONSTRAINTS
N intersection Sigma = empty_set
S in N
Every production's lhs and rhs use symbols in N union Sigma.
Every production lhs contains at least one nonterminal.
The empty word epsilon is a string of length zero, not a terminal symbol.
A production A -> epsilon denotes an empty right-hand side.

4. CORE RELATIONSHIPS
HAS_NONTERMINAL(Grammar, Nonterminal)
HAS_TERMINAL(Grammar, Terminal)
HAS_START_SYMBOL(Grammar, StartSymbol)
HAS_PRODUCTION(Grammar, Production)
REWRITES(SententialForm, SententialForm)
DERIVES(SententialForm, SententialForm)
GENERATES(Grammar, TerminalString)
RECOGNISES(Automaton, Language)
EQUIVALENT_LANGUAGE(Grammar, Grammar)
CLASSIFIED_AS(Grammar, GrammarClass)

5. FLOW OPERATIONS
ONE_STEP_DERIVE(G, u, v):
  true iff there exist x,y,alpha,beta with u=x alpha y, v=x beta y,
  and (alpha -> beta) in P.

DERIVES_STAR(G,u,v):
  reflexive transitive closure of ONE_STEP_DERIVE.

GENERATED_LANGUAGE(G):
  L(G) = {w in Sigma* | DERIVES_STAR(G,S,w)}.

VALIDATE_GRAMMAR(G):
  verify finite sets, symbol disjointness, valid start symbol,
  and well-formed productions.

CLASSIFY_GRAMMAR(G):
  determine which syntactic restrictions are satisfied;
  report the most restrictive verified class.

6. CHOMSKY HIERARCHY
Type 0 (unrestricted): productions alpha -> beta with alpha containing
  at least one nonterminal; generates recursively enumerable languages.
Type 1 (context-sensitive): noncontracting rules |alpha| <= |beta|,
  with optional S -> epsilon under the usual restriction that S
  does not occur on any production right-hand side.
Type 2 (context-free): productions A -> gamma, A in N,
  gamma in (N union Sigma)*.
Type 3 (regular): consistently right-linear or left-linear productions;
  generates regular languages.
Inclusions: Regular subseteq ContextFree subseteq ContextSensitive
  subseteq RecursivelyEnumerable.
Note: Different grammar conventions require explicit handling of epsilon.

7. INFERENCE RULES
PRODUCTION_APPLICATION:
  (alpha -> beta) in P implies x alpha y => x beta y.
DERIVATION_REFLEXIVITY:
  u =>* u.
DERIVATION_TRANSITIVITY:
  u =>* v and v =>* w imply u =>* w.
LANGUAGE_MEMBERSHIP:
  S =>* w and w in Sigma* imply w in L(G).
LANGUAGE_EQUIVALENCE:
  L(G1) = L(G2) implies EQUIVALENT_LANGUAGE(G1,G2),
  even when production sets or parse trees differ.

8. ALGEBRAIC AND SEMANTIC PROPERTIES
Concatenation of strings is associative.
Epsilon is the two-sided identity for string concatenation.
Grammar derivation is reflexive and transitive under =>*.
Language equality is reflexive, symmetric, and transitive.
Grammar ambiguity means some terminal string has two distinct parse trees
  (equivalently two distinct leftmost derivations for a CFG).
Grammar equivalence does not imply structural identity.
A grammar is a generator; a recogniser may be a corresponding automaton.

9. WORKED EXAMPLE
G = ({S}, {a,b}, {S -> aSb, S -> epsilon}, S)
Derivation: S => aSb => aaSbb => aabb.
L(G) = {a^n b^n | n >= 0}.
This language is context-free but not regular.

10. VALIDATION
CHECK-01: N and Sigma are disjoint.
CHECK-02: S belongs to N.
CHECK-03: Every production is well-typed.
CHECK-04: A claimed derivation records valid intermediate forms.
CHECK-05: Every accepted generated word contains terminals only.
CHECK-06: Claimed grammar class passes its syntactic restrictions.
CHECK-07: Claimed language equivalence is proven, not inferred from examples.
CHECK-08: Ambiguity claims include a witness string and distinct parse trees.
CHECK-09: Avoid asserting general CFG equivalence or ambiguity decidability;
          both are undecidable in general.

11. SEMANTIC_EQUIVALENCE
Aliases: formal grammar, generative grammar (in formal-language context).
Related but not equivalent: parser, automaton, production system,
  natural-language grammar, regular expression.
Equivalence criterion: G1 ~ G2 iff L(G1)=L(G2).
Equivalence verification: require a formal proof or a sound restricted
  decision procedure; finite sampling alone is insufficient.

12. CONFIDENCE
Established definitions and theorems: HIGH.
Class membership: HIGH only after syntactic validation.
Language equivalence: UNVERIFIED unless accompanied by proof.
Derived statements: attach premises, rule identifiers and proof traces.

13. FLOW_HASH
Canonicalisation: UTF-8; normalise line endings and whitespace;
  sort unordered symbol sets; preserve production direction and order
  where semantically relevant; hash canonical flow with SHA-256.
FLOW_HASH: COMPUTE_ON_INGEST (not a precomputed digest).

14. UPDATE_MODEL
On edit: increment version, record timestamp, changed productions,
  affected derivations, language-membership consequences, validation status,
  previous hash and new hash. Revalidate class and examples.

15. AI_CONSUMPTION
Inputs: grammar definition, derivation query, classification request,
  candidate string or proof.
Outputs: typed grammar, validation report, derivation witness,
  language claim, classification, confidence and provenance.
Rules: distinguish proved results from heuristics; never invent a proof;
  flag undecidable general tasks; preserve exact symbols and scope.

END FLOW ALGEBRA