Regular Language Ontology

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

flow "RegularLanguageOntology" v1.0

# ---------- TYPED ENTITIES ----------
types:
  Symbol: atomic token
  Alphabet: finite set<Symbol>
  String: finite sequence<Symbol>
  Language: set<String>
  State: atomic identifier
  DFA: tuple(Q:set<State>, Sigma:Alphabet, delta:State*Symbol->State, q0:State, F:set<State>)
  NFA: tuple(Q:set<State>, Sigma:Alphabet, delta:State*Symbol->set<State>, I:set<State>, F:set<State>)
  RegularExpression: inductively defined expression over Alphabet
  RightLinearGrammar: tuple(Nonterminals, Terminals, Productions, Start)

# ---------- CORE DEFINITIONS ----------
definitions:
  epsilon: empty string
  Sigma_star: all finite strings over Sigma, including epsilon
  regular_language: L subseteq Sigma_star recognised by a finite automaton
  dfa_accepts: delta_star(q0,w) in F
  nfa_accepts: exists q in delta_star(I,w) such that q in F
  regex_denotation: language described by a regular expression
  right_linear_grammar: productions A->aB, A->a, or A->epsilon (with standard variants)

# ---------- OPERATIONS ----------
operations:
  union(L1,L2): {w | w in L1 or w in L2}
  intersection(L1,L2): {w | w in L1 and w in L2}
  complement(L,Sigma): Sigma_star \ L
  difference(L1,L2): L1 intersection complement(L2,Sigma)
  concatenate(L1,L2): {uv | u in L1 and v in L2}
  kleene_star(L): union over n>=0 of L^n; L^0={epsilon}
  kleene_plus(L): concatenate(L,kleene_star(L))
  reverse(L): {reverse(w) | w in L}
  left_quotient(L,w): {x | wx in L}
  homomorphic_image(h,L): {h(w) | w in L}
  inverse_homomorphic_image(h,L): {w | h(w) in L}

# ---------- EQUIVALENCE & CONSTRUCTIONS ----------
rules:
  kleene_theorem: regular(L) iff some DFA/NFA recognises L iff some regular expression denotes L
  grammar_equivalence: regular(L) iff some right-linear grammar generates L
  subset_construction: every NFA has an equivalent DFA
  epsilon_elimination: epsilon-NFA can be converted to equivalent NFA without epsilon transitions
  minimisation: every regular language has a unique minimal complete DFA up to state renaming
  myhill_nerode: regular(L) iff its right-congruence has finitely many equivalence classes
  closure: regular languages closed under union, intersection, complement, difference, concatenation, star, reversal, quotients, homomorphism, inverse homomorphism
  pumping_lemma: regular(L) implies exists p>=1 such that every w in L with |w|>=p decomposes w=xyz with |xy|<=p, |y|>=1 and xy^i z in L for all i>=0
  pumping_caveat: satisfying a pumping-style condition alone does not prove regularity

# ---------- INFERENCE ----------
inference:
  - IF valid DFA recognises L THEN infer regular(L)
  - IF valid regex denotes L THEN infer regular(L)
  - IF regular(L1) AND regular(L2) THEN infer regular(union(L1,L2))
  - IF regular(L) THEN infer regular(complement(L,Sigma))
  - IF infinitely many Myhill-Nerode distinguishable prefixes exist THEN infer not regular(L)
  - IF pumping lemma is contradicted for every proposed pumping length THEN infer not regular(L)

# ---------- VALIDATION ----------
validation:
  - alphabet must be finite
  - every input symbol of a DFA must have exactly one transition from each state
  - initial and accepting states must belong to Q
  - automaton and regex must use compatible alphabets
  - complement requires an explicit common alphabet and complete DFA semantics
  - verify automaton/regex equivalence by symmetric-difference emptiness
  - test edge cases: empty language, {epsilon}, empty alphabet, unreachable states
  - reject claim that pumping lemma is sufficient for regularity

# ---------- SEMANTIC RELATIONSHIPS ----------
relationships:
  RegularLanguage IS_A FormalLanguage
  RegularLanguage RECOGNISED_BY FiniteAutomaton
  RegularLanguage DESCRIBED_BY RegularExpression
  RegularLanguage GENERATED_BY RightLinearGrammar
  DFA EQUIVALENT_IN_EXPRESSIVE_POWER_TO NFA
  RegularLanguage CHARACTERISED_BY MyhillNerodeFiniteIndex
  RegularLanguage CLOSED_UNDER BooleanAndRegularOperations

SEMANTIC_EQUIVALENCE:
  - "regular language" == "finite-state recognisable language"
  - "DFA-recognisable" == "NFA-recognisable" == "regular-expression definable" (language classes)
  - "regular grammar language" == "regular language" (with right/left-linear grammar conventions)
  - Do not equate regular languages with all context-free languages.

CONFIDENCE:
  mathematical_definitions: 0.99
  closure_and_equivalence_theorems: 0.99
  source_page_alignment: unverified
  note: confidence scores are descriptive metadata, not empirical probabilities

FLOW_HASH:
  method: SHA-256
  input: canonical UTF-8 flow content excluding the FLOW_HASH field
  value: COMPUTE_ON_PUBLICATION

UPDATE_MODEL:
  revision_policy: semantic-versioning
  triggers: corrected theorem, clarified alphabet, updated source page, improved validation
  provenance: retain prior version and canonical hash

AI_CONSUMPTION:
  entity: RegularLanguage
  purpose: formal-language classification, finite-state recognition, automata construction, proof assistance
  required_context: finite alphabet, language specification, acceptance semantics
  safe_inferences: theorem-backed closure, conversion and equivalence claims
  limitations: do not infer regularity from finite examples or the pumping lemma alone
  output: typed entities, constructions, proof obligations, counterexamples, provenance

END FLOW ALGEBRA