DFA Basics and Definitions: 5-Tuple, Transition Table and Worked String Traces

Learners often recognise circles and arrows but still lose the definition when asked whether a machine is truly deterministic, complete, or accepting a particular string. We will move precisely from the five components of a DFA to a transition table and then trace two binary strings, symbol by symbol, through one machine. By the end, you will be able to validate a proposed DFA, trace any input, and explain acceptance in mathematical language.

Use CS Fundamentals for Exams & Placements as the broader subject hub when you want to connect automata with the rest of core computer science.

DFA definition: understand every part of the 5-tuple

A deterministic finite automaton is written as M = (Q, Sigma, delta, q0, F). Each part has a precise type and purpose:

• Q is a finite, non-empty set of states.

• Sigma is a finite input alphabet. It does not contain the empty string.

• delta: Q x Sigma -> Q is the transition function.

• q0 is the start state, and q0 belongs to Q.

• F is the set of accepting states, and F is a subset of Q.

The word finite says that Q contains finitely many states. Deterministic says that every current-state and input-symbol pair has exactly one next state. Therefore, the same complete input always produces the same run.

Keep three commonly mixed symbols separate. q0 is one state. F may contain zero, one, or several states. Sigma* is the set of all finite strings over Sigma, including the empty string epsilon. In a DFA, epsilon is not an alphabet symbol.

DFA transition function: exactly one move for every state-symbol pair

The ordinary transition delta(q, a) consumes one symbol a. Its string extension, written here as delta-star, traces a whole string. The base rule is delta-star(q, epsilon) = q. The recursive rule is delta-star(q, xa) = delta(delta-star(q, x), a), where a is the last symbol.

If |Q| = m and |Sigma| = k, a complete table has m x k filled cells. No cell can be blank or contain two next states, and a DFA has no epsilon transition. Multiple or set-valued moves belong to the contrast explained in Finite Automata: DFA vs NFA and Subset Construction.

For example, let P = ({s,a}, {0,1}, delta, s, {a}). It has four state-symbol pairs: (s,0), (s,1), (a,0), and (a,1). Suppose only delta(s,0)=a, delta(s,1)=s, and delta(a,0)=a are supplied. P is not yet a DFA because (a,1) is missing.

DFA worked example: accept exactly the binary strings ending in 01

Use one machine for the rest of the article:

M = ({q0,q1,q2}, {0,1}, delta, q0, {q2})

Its states remember the useful suffix of the prefix processed so far. q0 means there is no useful suffix for 01, either the prefix is empty or currently ends in 1. q1 means it ends in 0. q2 means it ends in 01.

There are 3 x 2 = 6 required state-symbol pairs, and the table contains each one exactly once.

Now trace 1101. Start at q0. The first 1 keeps the machine at q0, and so does the second 1. Reading 0 moves it to q1; the final 1 moves it to q2.

q0 --1--> q0 --1--> q0 --0--> q1 --1--> q2

All four symbols have been consumed, and q2 belongs to F, so 1101 is accepted.

For 1010, the trace is:

q0 --1--> q0 --0--> q1 --1--> q2 --0--> q1

The run finishes at non-final q1, so 1010 is rejected. For epsilon, no symbol is consumed, so the machine remains at non-final q0 and rejects it. Reaching q2 before the input ends does not stop a DFA.

DFA acceptance: move from one trace to the language L(M)

A DFA accepts a string only after consuming it completely. Formally, M accepts w exactly when delta-star(q0,w) belongs to F. Its language is L(M) = {w in Sigma* | delta-star(q0,w) is in F}. For our machine, this is the set of all binary strings whose final two symbols are 01.

A length-4 accepted string must have the form xx01. Each x is chosen independently from 0 and 1, so there are 2^2 = 4 possibilities: 0001, 0101, 1001, and 1101. Tracing any of the four ends at q2.

Now consider 010. After 01, the machine is at accepting q2, but input remains. The final 0 sends it to q1, so the complete string is rejected. A DFA accepts according to the state after the last symbol, not because it visited a final state earlier.

DFA validation: repair an incomplete machine with a dead state

Return to the partial two-state specification P, with start state s and final set {a}. Add a new non-final state d, define the missing move as delta(a,1)=d, and add delta(d,0)=d and delta(d,1)=d. The repaired machine has Q'={s,a,d} and therefore needs 3 x 2 = 6 transitions. It has the original three plus these three new ones.

The input 01 shows why a dead state is different from a missing edge:

s --0--> a --1--> d

The input is rejected after both symbols are consumed. Once the run reaches d, every later 0 or 1 keeps it at d.

Use this four-check routine on any DFA table or graph:

1. Find exactly one start state.

2. Identify the accepting set F.

3. Confirm one outgoing transition per alphabet symbol from every state.

4. Trace the entire input before deciding acceptance.

An unreachable state does not make a DFA invalid, although minimisation may later remove it.

DFA exam patterns and common definition traps

Recurring question forms include identifying the language of a diagram, computing the final state for a string, finding a missing or duplicate transition, distinguishing a DFA from an NFA, and counting accepted strings of a fixed length. Another common task asks whether swapping accepting and non-accepting states gives the complement. That works only after confirming the DFA is complete.

Keep these traps and corrections together:

• Two arrows on symbol 0 from q0 means the machine is not deterministic.

• No arrow on 1 from q2 means the transition function is not total.

• Visiting q2 while tracing 010 does not justify early acceptance.

• A double circle marks an accepting state, not necessarily the current state.

• A blank cell does not automatically mean rejection. Add an explicit dead-state transition.

The 20+ published practice questions tagged to DFA Basics & Definitions are a useful directional practice pool, not a fixed total. After learning the method here, use DFA Basics MCQs: 12 Solved Questions Explained for immediate practice rather than memorising definitions in isolation.

DFA basics: the short version and the next study step

• A DFA has a finite set of states.

• Every state-symbol pair has exactly one next state.

• epsilon consumes nothing.

• A string is accepted only when its complete trace ends in F.

• A missing transition must be repaired, usually with a dead state.

Our machine has 3 states, an alphabet of size 2, and exactly 6 transitions. It accepts 1101 and rejects 1010. Continue systematically with Theory Of Computation / Automata Theory, then study DFA Minimization for GATE: Minimum States, Step by Step once tracing and totality feel secure.