Finite Automaton Ontology

FLOW ALGEBRA
Finite Automaton Ontology — Kireth Semantic Library
Version: 1.0
Date: 2026-10-11
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/automata-theory/finite-automaton-ontology.html
Domain: Discrete Mathematics / Automata Theory
Status: Formal mathematical synthesis; source page not independently verified.

1. PURPOSE
Represent finite-state automata, their transition semantics, language recognition, transformations and validation as typed, machine-consumable relationships.

2. TYPED ENTITIES
Alphabet := finite set of input symbols Sigma.
Word := finite sequence in Sigma*; epsilon denotes the empty word.
State := element of a finite set Q.
InitialState := q0 in Q (DFA), or initial state q0 in Q (NFA convention).
AcceptingStates := subset F of Q.
DFA := (Q, Sigma, delta, q0, F), with delta: Q x Sigma -> Q total.
NFA := (Q, Sigma, Delta, q0, F), with Delta: Q x Sigma -> P(Q).
EpsilonNFA := (Q, Sigma, Delta_e, q0, F), with Delta_e: Q x (Sigma union {epsilon}) -> P(Q).
Run := sequence of configurations connected by transitions.
Language := subset of Sigma*.

3. CORE RELATIONSHIPS
HAS_STATE(automaton, state)
HAS_ALPHABET(automaton, alphabet)
STARTS_AT(automaton, initial_state)
ACCEPTS_AT(automaton, accepting_state)
TRANSITIONS_ON(source_state, symbol, target_state)
RECOGNISES(automaton, language)
REACHABLE_FROM(state, initial_state)
EQUIVALENT_LANGUAGE(automaton_a, automaton_b)

4. EXECUTABLE SEMANTICS
DFA_EXTEND(delta, q, epsilon) = q
DFA_EXTEND(delta, q, wa) = delta(DFA_EXTEND(delta, q, w), a)
DFA_ACCEPT(M, w) := DFA_EXTEND(delta, q0, w) in F
NFA_EXTEND(Delta, {q0}, epsilon) = {q0}
NFA_STEP(Delta, S, a) := union {Delta(q,a) : q in S}
NFA_EXTEND(Delta, S, wa) := NFA_STEP(Delta, NFA_EXTEND(Delta,S,w), a)
NFA_ACCEPT(M,w) := NFA_EXTEND(Delta,{q0},w) intersect F != empty
EPSILON_CLOSURE(S) := least set containing S and all states reachable from S by epsilon transitions.
EPSILON_NFA_ACCEPT(M,w) := acceptance after epsilon closure before and after symbol transitions.
LANGUAGE(M) := {w in Sigma* : ACCEPT(M,w)}

5. TRANSFORMATIONS
DETERMINISE(NFA): construct DFA with states subsets of Q, initial subset {q0}, transition NFA_STEP and accepting subsets intersecting F.
REMOVE_EPSILON(EpsilonNFA): use epsilon closure to define equivalent symbol transitions and acceptance.
COMPLETE_DFA(DFA): add a nonaccepting sink state for missing transitions if an incomplete specification was supplied.
COMPLEMENT(DFA): swap accepting and nonaccepting states only after ensuring deterministic total transitions over the fixed alphabet.
PRODUCT(DFA_A,DFA_B): construct paired states for intersection; choose accepting pairs according to desired Boolean language operation.
MINIMISE(DFA): remove unreachable states and merge language-indistinguishable states.

6. ALGEBRAIC AND LANGUAGE LAWS
L(DETERMINISE(N)) = L(N).
L(MINIMISE(D)) = L(D).
L(COMPLEMENT(D)) = Sigma* \ L(D), for complete DFA D.
L(PRODUCT_INTERSECTION(A,B)) = L(A) intersect L(B).
Regular languages are closed under union, intersection, complement, concatenation and Kleene star.
Every finite automaton recognises a regular language; every regular language has a finite automaton.

7. INFERENCE RULES
IF DFA_EXTEND(delta,q0,w) in F THEN ACCEPTS(M,w).
IF DFA_EXTEND(delta,q0,w) not in F THEN REJECTS(M,w).
IF reachable NFA state set after w intersects F THEN ACCEPTS(M,w).
IF two automata have no reachable accepting state in their symmetric-difference product THEN EQUIVALENT_LANGUAGE(A,B).
IF a DFA has unreachable states THEN those states may be removed without changing its language.

8. VALIDATION
CHECK finite(Q) and finite(Sigma).
CHECK q0 in Q and F subset Q.
CHECK each DFA transition returns exactly one state in Q for each (q,a) in Q x Sigma.
CHECK each NFA transition returns a subset of Q.
CHECK epsilon transitions are used only in the epsilon-NFA model.
CHECK determinisation, minimisation and epsilon elimination preserve recognised language.
CHECK complement operation requires a complete DFA and unchanged alphabet.
CHECK acceptance and rejection are mutually exclusive for a fixed complete DFA and word.

9. SEMANTIC_EQUIVALENCE
DFA ~ NFA when their recognised languages are identical.
Different state labels or diagrams do not alter language semantics.
An automaton is not necessarily minimal, even if it recognises the same language as a minimal automaton.
Finite automaton != pushdown automaton != Turing machine in expressive power.

10. CONFIDENCE
Definitions and standard closure/equivalence laws: HIGH (established mathematical theory).
Specific claims about the linked webpage: UNVERIFIED.
Machine-generated equivalence claims: REQUIRE proof or exhaustive finite-state product check.

11. FLOW_HASH
Algorithm: SHA-256 over canonical UTF-8 representation of the flow body.
Canonicalisation: normalise line endings to LF, use Unicode NFC, exclude FLOW_HASH output field.
FLOW_HASH_VALUE: COMPUTE_AT_INGESTION (not fabricated).

12. UPDATE_MODEL
On source revision: re-check terminology, model conventions, formal equations and examples.
Version changes: preserve prior version, record source URL, revision timestamp and diff.
Invalidate dependent claims if alphabet, transitions or acceptance semantics change.

13. AI_CONSUMPTION
Input: typed automaton specification, query word or language-equivalence request.
Process: parse -> type-check -> validate -> execute transition semantics -> prove/verify result.
Output: accepted/rejected, reached state(s), witness run, transformed automaton or equivalence certificate.
Do not claim exhaustive equivalence without finite-state verification or a sound proof.

AUTHORS
Mark Higgins — Sky (Recursive AI)
Kireth Research | https://kirethresearch.org