Formal Language Ontology

FLOW ALGEBRA
TITLE: Formal Language Ontology
DOMAIN: Discrete Mathematics / Formal Languages
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/formal-languages/formal-language-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Represent formal languages as precisely typed sets of finite strings over alphabets, with explicit grammar, automaton, derivation, membership, and closure semantics. Separate mathematical truths from claims requiring machine or grammar evidence.

2. TYPED ENTITIES
Alphabet := finite nonempty set of terminal symbols (Sigma).
Symbol := member of Sigma.
String := finite sequence over Sigma; epsilon denotes empty string.
StringLength := |w| in natural numbers.
Language := subset L of Sigma*.
Grammar := (N, Sigma, P, S) with nonterminals N, terminals Sigma, productions P, start symbol S.
Automaton := machine with defined input alphabet and acceptance semantics.
Derivation := finite sequence of grammar production applications.
RecognitionResult := ACCEPT | REJECT | UNKNOWN.
LanguageClass := REGULAR | CONTEXT_FREE | CONTEXT_SENSITIVE | RECURSIVELY_ENUMERABLE.
ProofEvidence := derivation, accepting run, construction, or theorem reference.

3. CORE RELATIONSHIPS
member_of(w, L) iff w in L.
formed_over(w, Sigma) iff every symbol of w belongs to Sigma.
generated_by(L, G) iff L = {w in Sigma* : S =>* w}.
recognised_by(L, M) iff L = {w : M accepts w}.
subset_of(L1, L2) iff every w in L1 belongs to L2.
equivalent_language(L1, L2) iff L1 = L2.

4. OPERATIONS
EMPTY_LANGUAGE(Sigma) := {}.
EPSILON_LANGUAGE(Sigma) := {epsilon}.
UNION(L1,L2) := {w : w in L1 or w in L2}.
INTERSECTION(L1,L2) := {w : w in L1 and w in L2}.
DIFFERENCE(L1,L2) := {w : w in L1 and w not in L2}.
COMPLEMENT(L,Sigma) := Sigma* \ L.
CONCAT(L1,L2) := {uv : u in L1, v in L2}.
STAR(L) := union over n >= 0 of L^n, with L^0 = {epsilon}.
PLUS(L) := L CONCAT STAR(L).
REVERSE(L) := {reverse(w) : w in L}.
LEFT_QUOTIENT(K,L) := {w : exists u in K such that uw in L}.

5. ALGEBRAIC LAWS
UNION(L,{}) = L.
CONCAT(L,{epsilon}) = L = CONCAT({epsilon},L).
CONCAT(L,{}) = {} = CONCAT({},L).
CONCAT(CONCAT(A,B),C) = CONCAT(A,CONCAT(B,C)).
CONCAT(A,UNION(B,C)) = UNION(CONCAT(A,B),CONCAT(A,C)).
STAR({}) = {epsilon}.
STAR({epsilon}) = {epsilon}.
STAR(STAR(L)) = STAR(L).
STAR(L) = {epsilon} UNION CONCAT(L,STAR(L)).
COMPLEMENT(COMPLEMENT(L,Sigma),Sigma) = L.
All operations involving complements must specify the same ambient Sigma*.

6. LANGUAGE CLASSES AND GUARANTEES
REGULAR: recognisable by finite automata; definable by regular expressions.
CONTEXT_FREE: generated by context-free grammars; recognisable by nondeterministic pushdown automata.
CONTEXT_SENSITIVE: generated by noncontracting grammars with standard epsilon exception; recognisable by linear bounded automata under conventional definitions.
RECURSIVELY_ENUMERABLE: recognised by Turing machines, which may fail to halt on nonmembers.
REGULAR subset CONTEXT_FREE subset CONTEXT_SENSITIVE subset RECURSIVELY_ENUMERABLE (proper inclusions).
Regular languages are closed under union, intersection, complement, concatenation and star.
Context-free languages are closed under union, concatenation and star; not generally closed under intersection or complement.

7. INFERENCE RULES
IF w in L1 THEN w in UNION(L1,L2).
IF w in L1 AND w in L2 THEN w in INTERSECTION(L1,L2).
IF u in L1 AND v in L2 THEN uv in CONCAT(L1,L2).
IF w in L THEN w in STAR(L).
IF epsilon in STAR(L) THEN record as true regardless of whether epsilon in L.
IF DFA M accepts w AND recognised_by(L,M) is established THEN w in L.
IF derivation S =>* w in grammar G AND generated_by(L,G) is established THEN w in L.
IF L is regular THEN L is context-free.
IF a language is context-free DO NOT infer it is regular.

8. VALIDATION
CHECK every string contains only declared terminal symbols.
CHECK grammar nonterminals and terminals are disjoint.
CHECK production syntax and class-specific restrictions.
CHECK automaton transitions and acceptance semantics match machine type.
CHECK equivalence claims with a valid proof or decision procedure for the relevant class.
CHECK negative membership claims do not follow solely from search failure or nontermination.
CHECK closure claims against the specific language class.
CHECK epsilon (empty string) differs from {} (empty language).

9. SEMANTIC_EQUIVALENCE
"formal language" == "set of finite strings over an alphabet" under standard formal-language semantics.
"empty word" == "epsilon" == "empty string".
"Kleene closure" == "Kleene star".
"language equality" == "extensional equality of string sets".
NOT_EQUIVALENT: epsilon versus empty language; grammar syntax versus generated language; recognisable versus decidable.

10. CONFIDENCE
CONFIDENCE(mathematical_definitions) := HIGH.
CONFIDENCE(derived_claim) := HIGH only with verified premises and sound inference.
CONFIDENCE(machine_membership) := HIGH with a checked accepting run.
CONFIDENCE(unverified_external_content) := UNVERIFIED.
CONFIDENCE is evidence metadata, not a substitute for a proof.

11. FLOW_HASH
FLOW_HASH.algorithm := SHA-256.
FLOW_HASH.input := canonical UTF-8 serialisation of versioned flow content excluding FLOW_HASH.value.
FLOW_HASH.value := COMPUTE_ON_PUBLICATION.
Do not invent a digest without running canonicalisation and hashing.

12. UPDATE_MODEL
UPDATE_MODEL.version := 1.0.
UPDATE_MODEL.triggers := changed grammar, alphabet, automaton, theorem, definition, or source content.
UPDATE_MODEL.actions := validate types; rerun membership/equivalence tests; update provenance; recompute FLOW_HASH; publish revision.
UPDATE_MODEL.provenance := source URL, revision date, authorship, validation record.

13. AI_CONSUMPTION
AI_CONSUMPTION.format := UTF-8 plain text.
AI_CONSUMPTION.mode := typed symbolic reasoning with explicit assumptions.
AI_CONSUMPTION.required_context := alphabet, language representation, machine/grammar semantics, proof evidence.
AI_CONSUMPTION.outputs := membership result, derivation, closure result, equivalence proof, counterexample, or UNKNOWN.
AI_CONSUMPTION.safety := never claim decidability, proof, or termination without justification.

14. EXAMPLE
Sigma = {a,b}; L = {w in Sigma* : w ends in a}.
"ba" in L; "bb" not in L; epsilon not in L.
L is regular; regex (a|b)*a describes L.
L CONCAT {b} = {w in Sigma* : w ends in ab}.

END FLOW ALGEBRA