Finite automaton accept string – yes or no

What the machine decides

A deterministic finite automaton (DFA) reads a string of symbols and then says yes if the string belongs to its language, no otherwise. The answer appears only after the whole string has been processed.

Components of a DFA

A DFA consists of five fixed parts:

• a finite set of states,
• an input alphabet (the symbols it may read),
• a transition function that maps a state-symbol pair to a single next state,
• a designated start state, and
• a set of accept (or final) states.

All of these are defined before the machine runs and never change during execution.

How the machine processes an input

1. Start in the start state.
2. Look at the first symbol of the input.
3. Follow the transition for the current state and that symbol to reach a new state.
4. Repeat steps 2-3 for each remaining symbol.
5. After the last symbol, check whether the current state is an accept state. If it is, answer yes; otherwise answer no.

The process is completely mechanical – no back-tracking, no guessing.

Worked example: strings that end in 01

Consider a DFA that accepts all binary strings ending with the suffix 01. It has three states:

• q0 – start state, also the state for “the last two symbols are not 01”.
• q1 – the last symbol read was a 0.
• q2 – the last two symbols read were 01 (accept state).

The transition table is:

Current state	Input 0	Input 1
q0	q1	q0
q1	q1	q2
q2	q1	q0

Example 1: 11001

1. Start in q0; read 1 → stay in q0.
2. Read 1 → stay in q0.
3. Read 0 → move to q1.
4. Read 0 → stay in q1.
5. Read 1 → move to q2.

All symbols are consumed and the machine ends in q2, an accept state, so the answer is yes.

Example 2: 1100

1. q0 → 1 → q0
2. q0 → 1 → q0
3. q0 → 0 → q1
4. q1 → 0 → q1

The input ends in q1, which is not accepting; the answer is no.

Formal definition (for reference)

A DFA is a 5-tuple (M = (Q, \Sigma, \delta, q_0, F)) where:

• (Q) is a finite set of states,
• (\Sigma) is a finite alphabet,
• (\delta : Q \times \Sigma \to Q) is the transition function,
• (q_0 \in Q) is the start state,
• (F \subseteq Q) is the set of accept states.

The extended transition function (\hat{\delta}) applies (\delta) repeatedly to a whole string. The language recognized by (M) is (L(M) = { w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F }). The yes/no answer is simply the membership test (w \in L(M)).

Designing a DFA: even number of zeros

Suppose we need a DFA that accepts binary strings containing an even number of zeros. We can use two states:

• e – an even count of zeros seen so far (start and accept state).
• o – an odd count of zeros.

Transitions:

• From e, reading 0 moves to o; reading 1 stays in e.
• From o, reading 0 moves back to e; reading 1 stays in o.

The table:

State	0	1
e	o	e
o	e	o

Testing the string 10100:

1. e → 1 → e
2. e → 0 → o
3. o → 1 → o
4. o → 0 → e
5. e → 0 → o

The final state is o, not accepting, so the answer is no. Changing the last symbol to 1 would leave the machine in e, giving a yes.

Common beginner mistakes

• Missing transitions – a DFA must define a move for every state-symbol pair. An undefined entry makes the machine incomplete and unable to answer for some inputs.
• Checking acceptance too early – the decision is made only after the last symbol, not after each step.
• Confusing nondeterministic and deterministic moves – a DFA cannot have two possible next states for the same symbol in the same state.
• Treating the start state as automatically accepting – only states listed in (F) count as accept states.
• Forgetting to include the empty string – if the language should contain the empty string, the start state must be an accept state.

Where the idea appears in textbooks

Introductory theory texts use DFAs to illustrate regular languages such as:

• “All strings over {a,b} with an even number of a’s.”
• “Strings that contain the substring 101.”
• “Binary numbers that are multiples of 3.”

Each example follows the same pattern: define a finite set of states that remember just enough information to decide membership, then let the machine read the input and answer yes or no.

Compilers also rely on DFAs for lexical analysis. A lexical analyzer scans source code character by character, using a DFA to decide whether the characters form a valid token (identifier, number, operator, etc.). The analyzer answers yes for a token that matches a pattern and no otherwise.

You can explore more examples in the Automa course and read the related post on Finite Automaton States and Transitions Explained.

Check yourself

1. Question: Does the DFA with states {q0,q1}, start state q0, accept state q1, and transitions q0-0→q1, q0-1→q0, q1-0→q1, q1-1→q0 accept the string “010”?
   Answer: Yes. The path is q0→q1→q0→q1, ending in q1.

2. Question: In the suffix-ending DFA above, what is the result for the input “10101”?
   Answer: Yes. The last two symbols are 01, so the machine ends in q2.

3. Question: If a transition is missing for state q0 on input 1, what happens when the machine reads a string that begins with 1?
   Answer: The machine is undefined for that input; it cannot produce a yes or no answer.