# Nondeterministic finite automaton

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

An epsilon-NFA relates a state and input symbol or epsilon to possible successor states; one full-input final path suffices for acceptance.

mko-nondeterministic-finite-automaton · definition · v0.10.0



## Mathematical statement

Transitions are [from state,input symbol or null,to state]; null is epsilon and consumes no input. States are nonempty because they contain the start, while the alphabet and final-state set may be empty. The relation may be empty or multivalued and need not be deterministic or total. An empty word may be accepted by a finite epsilon path. An empty final set is valid and recognizes the empty language. One finite accepting path proves membership; bounded-search failure does not prove rejection. An epsilon cycle alone does not accept, and all branches need not accept.





## Representative formula (exact TeX)

N(Q,S)





## Assumptions


- States are nonempty; states/alphabet are finite, unique and disjoint. Alphabet and final states may be empty.
- Path configurations are [state,input position]; acceptance requires complete input consumption and a final state.





## Symbol scope


- N — epsilon-NFA
- Q — finite state set
- S — input alphabet





## Intuition, definition, and misconceptions

Epsilon closure consumes no input.

Acceptance is an existential finite path.

Bounded failure and dead branches do not refute another path; an epsilon cycle without a final endpoint does not accept.

Do not require every branch to accept, let epsilon consume input or identify an epsilon cycle with acceptance.





## Adopted derivation guide

[An existential finite accepting NFA path](https://ocme.evemisslab.com/en/derivations/derivation-mko-nondeterministic-finite-automaton-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Deterministic finite automaton](https://ocme.evemisslab.com/en/mko/mko-finite-automaton/) — Control is finite.
- [Binary relations and set projections](https://ocme.evemisslab.com/en/mko/mko-relation/) — Transitions may be multivalued.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-subset/) — Successors form state subsets.





## Verification boundary

This slice does not claim DFA equivalence or the subset-construction theorem.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add NFA-to-DFA subset construction.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/nondeterministic-finite-automaton.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-nondeterministic-finite-automaton/index.md)