Nondeterministic finite automaton

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

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 — Control is finite.
• Binary relations and set projections — Transitions may be multivalued.
• 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.