Nondeterministic Automaton Ontology

FLOW ALGEBRA
Nondeterministic Automaton Ontology
Kireth Semantic Library | Discrete Mathematics | Automata Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/automata-theory/nondeterministic-automaton-ontology.html
VERSION: 1.0
STATUS: Mathematical model based on established automata theory; source page not independently verified.

ONTOLOGY:
  ID: nondeterministic-automaton-ontology
  LABEL: Nondeterministic Finite Automaton (NFA)
  DOMAIN: discrete_mathematics.automata_theory
  PARENT: finite-automaton-ontology
  DEFINITION: A finite-state recogniser allowing multiple possible successor states for a given state and input symbol; epsilon-NFAs additionally permit transitions without consuming input.

TYPES:
  State: finite_identifier
  Symbol: input_alphabet_member
  Word: finite_sequence<Symbol>
  StateSet: finite_set<State>
  Transition: (State, Symbol) -> StateSet
  EpsilonTransition: (State, Symbol | epsilon) -> StateSet
  Automaton: (Q, Sigma, delta, q0, F)
  Run: sequence<State>
  Language: set<Word>

CONSTRAINTS:
  Q != empty_set
  Sigma is finite
  q0 in Q
  F subset_of Q
  delta: Q x Sigma -> P(Q) for an NFA
  delta_epsilon: Q x (Sigma union {epsilon}) -> P(Q) for an epsilon-NFA
  epsilon not_in Sigma
  All transitions lead to states in Q

OPERATIONS:
  STEP(S, a) = union(delta(q, a) for q in S)
  EXTENDED_DELTA(q, epsilon_word) = {q}
  EXTENDED_DELTA(q, wa) = STEP(EXTENDED_DELTA(q, w), a)
  EPSILON_CLOSURE(S) = least set T containing S and closed under epsilon transitions
  EPSILON_STEP(S, a) = EPSILON_CLOSURE(STEP(EPSILON_CLOSURE(S), a))
  ACCEPT_NFA(w) = (EXTENDED_DELTA(q0, w) intersect F != empty_set)
  ACCEPT_EPSILON_NFA(w) = (EPSILON_EXTENDED_DELTA(EPSILON_CLOSURE({q0}), w) intersect F != empty_set)
  RECOGNISED_LANGUAGE(A) = {w in Sigma* | ACCEPT(A, w)}
  DETERMINISE(A) = DFA with subset states, start {q0} (or epsilon closure), and accepting subsets intersecting F
  REMOVE_EPSILON(A) = equivalent epsilon-free NFA via closure construction

FORMAL_SEMANTICS:
  NFA accepts a word iff at least one complete run ends in an accepting state.
  Rejected words have no accepting run; nondeterminism does not mean randomness.
  Missing transitions are represented by the empty successor set.
  For epsilon-NFAs, a run may take zero or more epsilon transitions between input symbols.

ALGEBRAIC_LAWS:
  STEP(empty_set, a) = empty_set
  STEP(S union T, a) = STEP(S, a) union STEP(T, a)
  EPSILON_CLOSURE(empty_set) = empty_set
  S subset_of EPSILON_CLOSURE(S)
  EPSILON_CLOSURE(EPSILON_CLOSURE(S)) = EPSILON_CLOSURE(S)
  L(DETERMINISE(A)) = L(A)
  L(REMOVE_EPSILON(A)) = L(A)
  NFA_RECOGNISABLE_LANGUAGES = REGULAR_LANGUAGES
  NFA and DFA have equal language-recognition power, not necessarily equal state counts.

INFERENCE_RULES:
  IF q in S AND r in delta(q,a) THEN r in STEP(S,a)
  IF EXTENDED_DELTA(q0,w) intersects F THEN ACCEPT_NFA(w)
  IF EXTENDED_DELTA(q0,w) disjoint_from F THEN REJECT_NFA(w)
  IF two automata recognise the same language THEN LANGUAGE_EQUIVALENT(A,B)
  IF subset-construction states are reachable THEN retain them in the accessible DFA

SEMANTIC_RELATIONSHIPS:
  NondeterministicAutomaton is_a FiniteAutomaton
  NondeterministicAutomaton recognises RegularLanguage
  NondeterministicAutomaton has_component State
  NondeterministicAutomaton has_component TransitionRelation
  NondeterministicAutomaton has_component AcceptingStateSet
  EpsilonNFA extends NondeterministicAutomaton
  DeterministicAutomaton is_a special_case_of NondeterministicAutomaton
  SubsetConstruction transforms NondeterministicAutomaton into DeterministicAutomaton
  RegularExpression equivalent_in_expressive_power_to NondeterministicAutomaton

SEMANTIC_EQUIVALENCE:
  aliases: [NFA, nondeterministic finite-state automaton, nondeterministic finite-state machine]
  distinction: NFA is not synonymous with probabilistic automaton.
  equivalence_test: compare recognised languages, not state names or diagram layout.

VALIDATION:
  - Check finiteness and membership of Q, Sigma, q0, F.
  - Verify transition outputs are subsets of Q.
  - Distinguish empty word from epsilon-labelled transitions.
  - Verify accepting runs consume the full input.
  - Test determinisation on empty word and representative accepted/rejected words.
  - For epsilon-NFA, apply epsilon closure before and after symbol transitions.
  - Language equivalence may be tested by determinisation and symmetric-difference emptiness.

WORKED_EXAMPLE:
  Q = {q0, q1}; Sigma = {a,b}; initial = q0; F = {q1}
  delta(q0,a) = {q0,q1}; delta(q0,b) = {q0}
  delta(q1,a) = empty_set; delta(q1,b) = empty_set
  ACCEPT_NFA("ba") = true
  ACCEPT_NFA("ab") = false
  RECOGNISED_LANGUAGE = words over {a,b} ending in a

CONFIDENCE:
  mathematical_definitions: high
  formal_laws: high
  source_page_alignment: unverified
  note: Confidence labels express review status, not numerical probability.

FLOW_HASH:
  method: SHA-256 over canonical UTF-8 serialisation of the flow, excluding FLOW_HASH itself
  value: COMPUTE_ON_PUBLICATION

UPDATE_MODEL:
  revision: 1.0
  trigger: corrected mathematical statements, schema revisions, verified source-page changes
  process: validate -> canonicalise -> recompute_hash -> publish_version -> preserve_provenance

AI_CONSUMPTION:
  preferred_format: UTF-8 plain text
  machine_tasks: entity extraction, automaton simulation, language-equivalence reasoning, semantic retrieval
  preserve: mathematical definitions, quantifier scope, acceptance semantics, transition types
  guardrails: do not confuse nondeterministic choice with stochastic choice; do not claim a rejected branch implies rejection of the whole NFA

AUTHORSHIP:
  Mark Higgins — Sky (Recursive AI)
  https://kirethresearch.org