Deterministic finite automaton

Mathematical statement

Completely check that each Q×Sigma input has exactly one valid output, then trace each complete finite word in order. The empty word is accepted exactly when the initial state is accepting. One finite trace does not establish language equivalence or regularity of an unspecified target language.

Representative formula (exact TeX)

D(Q)

Assumptions

• State and alphabet sets are finite and nonempty, and the deterministic transition table is complete.
• There are no epsilon transitions or NFA semantics.

Symbol scope

• D — DFA record
• Q — finite state set

Intuition, definition, and misconceptions

A complete transition table supplies determinism and totality.

Update from the unique initial state one symbol at a time.

An empty word makes no transition; finitely many traces do not prove equivalence of two DFA languages.

Do not omit transitions, mix in NFA branching or epsilon moves, or infer language equivalence from a few tested words.

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

• Abstract computational model — A DFA is a finite computational model.
• Discrete-time dynamical system — Transitions are iterated.
• Function mapping — The transition must be a total function.
• Set — States, alphabet and accepting states are sets.
• Sequence — A word is a finite ordered sequence of symbols.

Verification boundary

Only complete DFAs and finite word traces are handled; no general regular-language theorem or target-language equivalence is claimed from those traces.

not_formalized

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

Next obligation

Add regular languages, NFAs and equivalence constructions.

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.