Deterministic Finite Automata (DFA)

acceptance by a DFA

Acceptance is the moment of verdict: a DFA either accepts an input string or rejects it, and the rule for which is beautifully simple. Run the machine on the string from the start state; when the input is exhausted, look at the state you ended in. If that final state is an accept state, the machine accepts; if not, it rejects. There is no in-between and no third answer — every string gets a clean yes or no.

In symbols, a DFA M = (Q, Σ, δ, q0, F) accepts the string w exactly when δ-hat(q0, w) ∈ F, that is, when the unique run starting at q0 ends inside the set of accept states. Rejection is simply the complement: w is rejected when δ-hat(q0, w) is a state not in F. Because δ is total, every string has a well-defined ending state, so acceptance is defined for every possible input — nothing is left undecided.

Two honest reminders. First, only the final state matters; merely passing through an accept state partway does not count as acceptance. Second, acceptance is about a single string at a time; the collection of all strings a machine accepts is a separate, bigger idea called the language of the DFA. Rejecting is not the same as crashing — a DFA never crashes; rejection is a deliberate, well-defined outcome.

On the 'ends in 1' DFA: 1101 ends in state B (an accept state), so it is accepted; 1100 ends in state A (not accepting), so it is rejected; the empty string ε ends in the start state A, also rejected. Three strings, three definite verdicts.

Accept w iff δ-hat(q0, w) ∈ F; otherwise reject. Every string gets exactly one verdict.

Acceptance is decided once, at the end, by the final state alone. A string that visits an accept state in the middle but ends elsewhere is rejected.

Also called
acceptance conditionaccepting a string接受接受條件