Deterministic Automaton Ontology

FLOW ALGEBRA
TITLE: Deterministic Automaton Ontology
DOMAIN: Discrete Mathematics / Automata Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/automata-theory/deterministic-automaton-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 deterministic finite automata (DFAs) as typed mathematical structures with executable transition semantics, language recognition, verification and interoperability rules.

2. TYPED ENTITIES
State := atomic identifier
Alphabet := finite nonempty set of symbols
Word := finite sequence over Alphabet (including epsilon)
StateSet Q := finite nonempty set of State
StartState q0 := element of Q
AcceptingStates F := subset of Q
Transition delta := total function Q x Alphabet -> Q
DFA M := (Q, Alphabet, delta, q0, F)
Run := sequence of states induced by a Word
Language := subset of Alphabet*

3. CORE SEMANTICS
extended_delta(q, epsilon) = q
extended_delta(q, wa) = delta(extended_delta(q, w), a)
accepts(M, w) := extended_delta(q0, w) in F
L(M) := {w in Alphabet* | accepts(M, w)}
rejects(M, w) := not accepts(M, w)

4. DETERMINISM AND TOTALITY
forall q in Q, a in Alphabet: exists exactly one delta(q,a) in Q.
For a partial transition specification, an explicit nonaccepting sink state may be added to make delta total.
Each word determines exactly one run from q0.
An NFA with multiple possible successor states is not a DFA unless determinised.

5. TRANSFORMATIONS
complement(M): keep Q, Alphabet, delta, q0; replace F with Q\F, assuming a complete DFA.
product(M1,M2): states Q1 x Q2; transitions componentwise; choose final pairs for union, intersection or difference.
reachable(M): least subset R containing q0 and closed under delta.
trim_unreachable(M): restrict to reachable states, preserving L(M).
minimise(M): quotient reachable states by indistinguishability of future acceptance.
determinise(N): subset construction for a finite nondeterministic automaton, with epsilon closure where needed.

6. ALGEBRAIC LAWS
L(complement(M)) = Alphabet* \ L(M).
L(union(M1,M2)) = L(M1) union L(M2).
L(intersection(M1,M2)) = L(M1) intersection L(M2).
L(difference(M1,M2)) = L(M1) \ L(M2).
L(minimise(M)) = L(M).
Equivalent DFAs recognise identical languages, even if their state names or structures differ.
Regular languages are exactly those recognised by DFAs.

7. INFERENCE RULES
TRANSITION: q in Q and a in Alphabet -> delta(q,a) in Q.
EMPTY_RUN: q in Q -> extended_delta(q,epsilon)=q.
STEP: extended_delta(q,w)=r and delta(r,a)=s -> extended_delta(q,wa)=s.
ACCEPT: extended_delta(q0,w) in F -> accepts(M,w).
REJECT: extended_delta(q0,w) not in F -> rejects(M,w).
EQUIVALENCE: no reachable distinguishing state in the symmetric-difference product -> L(M1)=L(M2).

8. VALIDATION
V01 Q is finite and nonempty.
V02 Alphabet is finite and nonempty.
V03 q0 belongs to Q.
V04 F is a subset of Q.
V05 delta is defined once and only once for each (q,a).
V06 Every transition target belongs to Q.
V07 Input words contain only alphabet symbols.
V08 Complement requires a complete transition function.
V09 Product operations require aligned alphabets or an explicit alphabet-normalisation procedure.
V10 Equivalence checks must compare accepted languages, not merely state counts.

9. WORKED EXAMPLE
Alphabet = {0,1}
Q = {even,odd}
q0 = even
F = {even}
delta(even,0)=even; delta(even,1)=odd
delta(odd,0)=odd; delta(odd,1)=even
Meaning: accepts exactly binary strings containing an even number of 1 symbols.
accepts(epsilon)=true; accepts(101)=true; accepts(111)=false.

10. SEMANTIC RELATIONSHIPS
DeterministicAutomaton IS_A FiniteAutomaton.
DeterministicAutomaton RECOGNISES RegularLanguage.
TransitionFunction MAPS StateSymbolPair TO State.
StartState MEMBER_OF StateSet.
AcceptingStates SUBSET_OF StateSet.
DeterministicAutomaton EQUIVALENT_TO RegularExpression WHEN languages coincide.
MinimalDFA IS_CANONICAL_UP_TO StateRenaming FOR a fixed regular language.

11. SEMANTIC_EQUIVALENCE
DFA ~ DFA iff L(DFA1)=L(DFA2).
Canonical comparison: minimise reachable complete DFAs and compare up to state renaming, or search for an accepting state in the symmetric-difference product.
Preserve the distinction between language equivalence and structural equality.

12. CONFIDENCE
Mathematical definitions and stated DFA properties: 1.00 (formal, conditional on specified assumptions).
Page-specific correspondence: unverified; do not interpret as source-extracted text.
Confidence values describe rule certainty, not measured model performance.

13. FLOW_HASH
Algorithm: SHA-256
Input: canonical UTF-8 serialisation of version, typed schema, rules and source URL.
Value: compute on ingestion; no fabricated digest is supplied.

14. UPDATE_MODEL
Trigger: source revision, mathematical correction, schema change, or validation failure.
Procedure: revalidate types and laws; increment version; regenerate FLOW_HASH; retain provenance and previous revision.

15. AI_CONSUMPTION
Input: DFA specification, query word or requested transformation.
Parse -> type-check -> verify determinism/totality -> evaluate or transform -> validate output -> return result with provenance.
Never infer transitions that are absent without explicitly applying a completion rule.
Output: typed automaton, accepted/rejected result, transformation trace and validation report.

END FLOW ALGEBRA