Transition Function Ontology

FLOW ALGEBRA
TITLE: Transition Function Ontology
DOMAIN: Discrete Mathematics / Automata Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/automata-theory/transition-function-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
Model transition functions as typed rules governing how computational systems change state in response to input symbols, events, stack symbols, or tape symbols. Distinguish deterministic, nondeterministic, partial, and extended transitions.

2. TYPED ENTITIES
StateSet Q : finite_set<State>
InputAlphabet Sigma : finite_set<Symbol>
State q : element(Q)
InputSymbol a : element(Sigma)
TransitionFunction delta : typed_mapping
InitialState q0 : element(Q)
AcceptingStates F : subset(Q)
TransitionRecord t : (source_state, input, target_state)
Configuration c : machine_configuration
ExecutionTrace tau : sequence<Configuration>

3. FORMAL DEFINITIONS
DFA transition: delta : Q x Sigma -> Q (total, single-valued).
Partial DFA transition: delta : Q x Sigma ⇀ Q (may be undefined).
NFA transition: delta : Q x Sigma -> P(Q) (set-valued).
Epsilon-NFA transition: delta : Q x (Sigma union {epsilon}) -> P(Q).
Extended DFA transition delta* : Q x Sigma* -> Q:
  delta*(q, epsilon) = q
  delta*(q, wa) = delta(delta*(q,w), a).
Extended NFA transition delta* : Q x Sigma* -> P(Q):
  delta*(q, epsilon) = {q} (without epsilon moves)
  delta*(q, wa) = union_{r in delta*(q,w)} delta(r,a).
For epsilon-NFAs, apply epsilon-closure at initialisation and after each symbol transition.

4. CORE RELATIONSHIPS
TransitionFunction --maps_from--> StateSet x InputAlphabet
TransitionFunction --maps_to--> StateSet or PowerSet(StateSet)
TransitionRecord --has_source--> State
TransitionRecord --consumes--> InputSymbol
TransitionRecord --has_target--> State
ExtendedTransition --extends--> TransitionFunction
TransitionFunction --determines--> Reachability
TransitionFunction --participates_in--> LanguageRecognition

5. OPERATIONS
STEP_DFA(q,a) := delta(q,a).
STEP_NFA(S,a) := union_{q in S} delta(q,a).
EPSILON_CLOSURE(S) := least set C containing S and closed under epsilon transitions.
RUN_DFA(w) := delta*(q0,w).
ACCEPT_DFA(w) := RUN_DFA(w) in F.
RUN_NFA(w) := delta*(q0,w), incorporating epsilon closure where applicable.
ACCEPT_NFA(w) := RUN_NFA(w) intersection F != empty_set.
REACHABLE(q) := states reachable from q through zero or more transitions.

6. ALGEBRAIC LAWS AND INVARIANTS
Extended transition identity: delta*(q,epsilon) = q for DFAs.
Concatenation: delta*(q,uv) = delta*(delta*(q,u),v) for DFAs.
NFA concatenation: delta*(q,uv) = union_{r in delta*(q,u)} delta*(r,v).
DFA determinism: for each (q,a), exactly one successor exists.
NFA successor set: delta(q,a) subseteq Q; empty successor sets are permitted.
Totality is required for the standard DFA definition, not for partial transition systems.
Reachability is reflexive and transitive under zero-or-more-step semantics.

7. INFERENCE RULES
DFA_STEP: delta(q,a)=r => (q,aw) -> (r,w).
NFA_STEP: r in delta(q,a) => (q,aw) -> (r,w).
EPSILON_STEP: r in delta(q,epsilon) => (q,w) -> (r,w).
ACCEPTANCE_DFA: delta*(q0,w) in F => ACCEPT(w).
ACCEPTANCE_NFA: exists r in delta*(q0,w) with r in F => ACCEPT(w).
UNREACHABLE_STATE: q not in REACHABLE(q0) => q cannot occur in any run from q0.

8. MACHINE VARIANTS
Mealy output function lambda : Q x Sigma -> OutputAlphabet.
Moore output function lambda : Q -> OutputAlphabet.
Pushdown automaton: delta : Q x (Sigma union {epsilon}) x Gamma -> P(Q x Gamma*).
Turing machine: delta : Q x Gamma -> Q x Gamma x {L,R} for a standard deterministic non-halting transition; halting states and stay moves depend on convention.
These signatures are distinct types and must not be conflated with DFA transitions.

9. VALIDATION
CHECK_STATE_MEMBERSHIP: every source and target state belongs to Q.
CHECK_SYMBOL_MEMBERSHIP: each consumed symbol belongs to Sigma, except permitted epsilon moves.
CHECK_DFA_TOTALITY: each (q,a) has exactly one target.
CHECK_NFA_TYPE: each (q,a) maps to a subset of Q.
CHECK_START_AND_ACCEPT: q0 in Q and F subseteq Q.
CHECK_TRACE: each adjacent configuration follows an allowed transition.
CHECK_EXTENDED_RULES: base case and concatenation recurrence hold.
CHECK_REACHABILITY: computed states agree with graph traversal of transition edges.

10. SEMANTIC_EQUIVALENCE
DFA transition table == transition function == labelled deterministic transition graph when they encode identical mappings.
Two machine descriptions are language-equivalent iff they accept the same set of strings; language equivalence does not imply identical state structure.
An NFA and its subset-construction DFA are language-equivalent when determinisation is correct.

11. CONFIDENCE
Formal definitions and standard algebraic laws: HIGH.
Implementation-dependent machine variants and conventions: CONDITIONAL.
Claims about the source webpage: UNVERIFIED.
Confidence must not replace formal verification of a particular automaton.

12. FLOW_HASH
MODEL: SHA-256 over canonical UTF-8 serialisation of typed entities, transitions, alphabet, states, start state, accepting states and version.
STATUS: NOT_COMPUTED; compute on ingestion after canonicalisation.
Avoid claiming a fixed digest before the canonical source representation is established.

13. UPDATE_MODEL
TRIGGER: changed transition, state, alphabet, machine convention, acceptance condition, or source revision.
ACTION: type-check -> validate invariants -> recompute reachability -> retest accepted language -> regenerate canonical representation -> recalculate FLOW_HASH.
VERSION_POLICY: record provenance and retain prior validated versions.

14. AI_CONSUMPTION
INPUT: typed automaton specification, transition function, input string, optional proof obligations.
OUTPUT: validated transition graph, execution trace, reachable states, acceptance result, and explicit assumptions.
SAFETY: reject ill-typed transitions; distinguish deterministic and nondeterministic semantics; mark unresolved or unverified claims.
PROVENANCE: retain SOURCE_URL, VERSION, DATE, AUTHORS and SOURCE_STATUS.

15. EXAMPLE
Q = {q0,q1}; Sigma = {0,1}; F = {q1}.
delta(q0,0)=q0; delta(q0,1)=q1.
delta(q1,0)=q0; delta(q1,1)=q1.
RUN_DFA(101) = q1; ACCEPT_DFA(101) = true.
Language recognised: all binary strings ending in 1.

END FLOW ALGEBRA