Finite automata — DFA - formal definition (5-tuple), state diagrams: Question bank

Quick symbol reminder so nothing here is used before it is grounded. A DFA is the 5-tuple $M = (Q, Σ, δ, q_{0}, F)$ , and every symbol on this page comes from it:

$Q$ = the finite, non-empty set of states (the squares of the hopping game). It must be non-empty because the machine has to be somewhere: even the do-nothing machine needs at least a start square to stand on.
$Σ$ = the alphabet, the finite set of symbols the machine may read.
$Σ^{*}$ = the set of all finite strings over $Σ$ , including the empty string $ε$ (the string of length zero).
$δ : Q \times Σ \to Q$ = one-step transition: given (state, one symbol) it names exactly one next state.
$\hat{δ} : Q \times Σ^{*} \to Q$ = extended transition: given (state, whole string) it names where you land after reading it all.
$q_{0} \in Q$ = the single start state, the square you stand on before any symbol is read; $\hat{δ}$ always begins its run here.
$F \subseteq Q$ = the accept states (drawn as double circles); $M$ accepts $w$ iff $\hat{δ} (q_{0}, w) \in F$ .
$L (M)$ = the ==language of $M$ ==, meaning the set of all strings it accepts: $L (M) = {w \in Σ^{*} : \hat{δ} (q_{0}, w) \in F}$ . So " $L (M) = \emptyset$ " means " $M$ accepts no string at all."
$q_{dead}$ = a dead / trap state: a non-accepting state whose transitions on every symbol loop back to itself. Once a run enters it, it can never leave and never accept — it is the honest home of every "missing arrow."

True or false — justify

A DFA can have zero accept states.

True.

F = \emptyset

is a legal subset of

Q

; the definition only says

F \subseteq Q

, with no lower bound. Then no string can satisfy

\hat{δ} (q_{0}, w) \in F

, so

L (M) = \emptyset

— an empty language is valid even though

Q

and

Σ

themselves must be non-empty for the tuple to describe a working machine.

A DFA can have infinitely many states as long as

δ

stays finite.

False. The word finite in "finite automaton" is a hard requirement —

Q

must be finite because

Q

is the machine's entire memory; an infinite

Q

would smuggle in unbounded memory and let it recognize non-regular languages, defeating the model's purpose.

Every DFA accepts at least one string.

False. If no path from

q_{0}

reaches a state in

F

(or

F = \emptyset

), then

\hat{δ} (q_{0}, w) \in / F

for every

w

, so

L (M) = \emptyset

— which is still a perfectly valid regular language, just an empty one.

Two different DFAs can recognize the exact same language.

True. Given one DFA you can always add unreachable states or split a state into two behaviourally-identical copies without changing which strings reach

F

, so

L (M)

is unchanged. This many-to-one relationship is exactly why minimization exists — to pick the unique smallest representative.

q_{0} \in F

, the DFA accepts the empty string

ε

True. The base case of the extended transition gives

\hat{δ} (q_{0}, ε) = q_{0}

, so "does

M

ε

?" becomes "is

q_{0} \in F

?" Nothing is read, so only the starting position decides.

A DFA with

n

states can only accept strings of length up to

n

False. Self-loops and cycles let a run revisit states, so a length-1000 string can run through the same

n

states over and over; input length is unbounded while the number of distinct remembered situations stays fixed at

n

Swapping accept and non-accept states (

F \to Q ∖ F

) gives a DFA for the complement language.

True. Because

δ

is total, every string

w

has exactly one landing state

\hat{δ} (q_{0}, w)

, which is in either

F

Q ∖ F

but never both; flipping the label therefore flips membership for every string, yielding exactly

\overline{L (M)} = Σ^{*} ∖ L (M)

An NFA is strictly more powerful than a DFA.

False. NFAs are more convenient to design but recognize the exact same class (the regular languages); subset construction mechanically turns any NFA into an equivalent DFA, proving equal power.

δ

and

\hat{δ}

can be used interchangeably.

False.

δ

eats one symbol;

\hat{δ}

eats a whole string by recursion over its length. They only coincide on a single-symbol input (

\hat{δ} (q, a) = δ (q, a)

), and only

\hat{δ}

is even defined on

ε

and on multi-symbol strings.

If a language is finite, some DFA recognizes it.

True. For a finite language you can build a "spelling tree" whose branches spell out each allowed string, mark the ends as accept states, and route every other transition to

q_{dead}

; this is always a valid finite DFA, so every finite language is regular.

Spot the error

(These items quote a claim someone might make about a diagram they are looking at; you supply the fix from the definition alone — no figure is needed to see why each is wrong.)

"My diagram is a DFA: state

q

has two outgoing arrows both labelled

a

Error: not deterministic. A DFA needs exactly one target per (state, symbol); two

a

-arrows out of

q

means

δ (q, a)

isn't single-valued — that is an NFA, not a DFA.

"It's a valid DFA; state

q

just has no arrow drawn for symbol

b

Error:

δ

must be total. A genuinely missing

b

-transition is illegal; the honest reading is that

q

goes on

b

to a dead state

q_{dead}

that loops on itself and never accepts.

δ : Σ \times Q \to Q

, given (symbol, state)."

Order error: the standard signature is

δ : Q \times Σ \to Q

— state first, symbol second. The mapping's values are the same, but matching the convention avoids reading transition tables backwards.

"The start state must not be an accept state."

Error: there is no such rule. Nothing in the tuple forbids

q_{0} \in F

; that overlap is exactly the case where

ε

is accepted. Start-ness and accept-ness are independent properties.

L (M)

is the set of states the machine can reach."

Error:

L (M)

is a set of strings, not states — precisely

{w : \hat{δ} (q_{0}, w) \in F}

. Reachable states are a property of

Q

; the language lives in

Σ^{*}

"A DFA can have two start states to cover both cases."

Error: a DFA has exactly one start state

q_{0} \in Q

. Multiple starts is a nondeterministic feature; determinism means the run is completely fixed the moment you place your token on

q_{0}

"Double-circling every state makes the DFA accept faster."

Error: double circles only mark membership in

F

, not speed. There is no notion of speed here; the machine always reads the entire string, then performs one membership check at the end.

Why questions

Why must

δ

be total (defined for every state–symbol pair)?

So the machine never "gets stuck" mid-string; totality guarantees every input string produces a complete, unique run ending in one well-defined state, which is what makes acceptance an unambiguous yes/no.

Why is the state itself called the machine's "entire memory"?

Because a DFA has no counter, stack, or writable tape — the only thing carried from one symbol to the next is which state you're in, so every fact the machine "remembers" must be encoded as a distinct state.

Why do we define

\hat{δ}

recursively instead of just "run

δ

repeatedly"?

To pin down acceptance precisely and for $ε$ : the base case

\hat{δ} (q, ε) = q

handles the empty string that

δ

alone cannot, and the recursive step gives a rigorous definition you can prove things about by induction on string length.

Why does "count the 0's" reduce to just two states for an even-parity language?

Because the accept/reject fact depends only on even vs odd, not the true count — the minimal memory distinguishing the two answers is a single bit, so two states (even-so-far, odd-so-far) capture everything relevant.

Why can a DFA recognize "ends in 1" but not "has equal 0's and 1's"?

"Ends in 1" needs only the last symbol, a bounded fact fitting in finite states; "equal 0's and 1's" needs an unbounded counter, which finitely many states cannot hold — this impossibility is exactly what the Pumping Lemma proves.

Why are DFAs the right model for a tokenizer?

Token patterns are described by regular expressions, and every regex compiles to a DFA that scans left-to-right in one pass with fixed memory — fast and exactly powerful enough for the job.

Why does flipping

F

work for complement but the same trick fails for an NFA?

In a DFA, totality gives one run per string, so flipping accept-status cleanly inverts membership; in an NFA a string may have both accepting and non-accepting runs at once, so flipping

F

does not reliably invert acceptance.

Edge cases

Must the set of states

Q

be non-empty?

Yes. A DFA needs a start state

q_{0} \in Q

, and

\hat{δ}

must begin its run somewhere; with

Q = \emptyset

there is no

q_{0}

and the tuple is ill-formed, so a non-empty

Q

is an implicit requirement of the definition.

What language does a DFA with

F = Q

(every state accepting) recognize?

All of

Σ^{*}

— every run ends in an accept state, so

L (M) = Σ^{*}

, accepting every string including

ε

Is a machine with an empty alphabet

Σ = \emptyset

meaningful?

Only marginally: the sole readable string is

ε

, so

L (M)

is either

{ε}

(if

q_{0} \in F

) or

\emptyset

. It is technically valid but degenerate — nothing to read means nothing to decide beyond the start state.

Does the empty string

ε

have an even or odd number of 0's?

Even —

#0 (ε) = 0

and

0

is even, so an even-parity DFA correctly accepts

ε

when its start state is the "even" accept state.

Once a run enters a dead/trap state

q_{dead}

, can it ever reach an accept state?

No —

q_{dead}

loops to itself on every symbol and is non-accepting, so any prefix landing there dooms the whole string to rejection regardless of what follows.

If a state is unreachable from

q_{0}

, does removing it change

L (M)

No. Unreachable states never appear in any run

\hat{δ} (q_{0}, w)

, so deleting them leaves acceptance of every string unchanged — this is one clean-up step in minimization.

Can two distinct strings

w_{1} \neq = w_{2}

both land in the same state?

Yes, and they usually do — a state records only "which situation," so many strings collapse to one. With finitely many states but infinitely many strings, the pigeonhole principle forces infinitely many such collisions.

If every transition is a self-loop, what languages are possible?

Only

\emptyset

Σ^{*}

— you never leave

q_{0}

, so

\hat{δ} (q_{0}, w) = q_{0}

for all

w

and acceptance depends solely on whether

q_{0} \in F

, giving all strings or none.

Recall One-line self-test

If you can answer "why must $δ$ be total, and what hides behind a missing arrow?" in one breath, you own the core trap of this topic. Answer ::: Totality guarantees every string has one complete run; a missing arrow is shorthand for a transition into the hidden non-accepting dead state $q_{dead}$ .