Deterministic finite automata

Why it exists

A finite automaton is the simplest model of a computer: a machine with a fixed, finite amount of memory that reads its input once, from left to right, and then says yes or no. It is also the model of a great many real things: the lexical analyser of a compiler (see lexical analysis), a vending machine, the control of a traffic light, a network protocol's state. The deterministic version has no choices: in every state the next symbol decides the next state. Everything in this subject is built on it, and the questions GATE asks are of three kinds: what language does this DFA accept, design a DFA for this language, and how many states are needed.

Prerequisites

You need strings, alphabets and languages (alphabets, strings and languages).

Precise definitions

DFA. A deterministic finite automaton is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$:

• $Q$: a finite set of states;
• $\Sigma$: the input alphabet;
• $\delta : Q \times \Sigma \to Q$: the transition function (a total function: exactly one next state for every state and symbol);
• $q_0 \in Q$: the start state;
• $F \subseteq Q$: the set of accepting (final) states.

Extended transition function. $\delta^* : Q \times \Sigma^* \to Q$ is defined by $\delta^*(q, \varepsilon) = q$ and $\delta^*(q, wa) = \delta(\delta^*(q, w), a)$: the state reached from $q$ after reading the whole string $w$.

Acceptance and language. $M$ accepts $w$ if $\delta^*(q_0, w) \in F$. The language of $M$ is $L(M) = \{ w \in \Sigma^* : \delta^*(q_0, w) \in F \}$. A language is regular if some DFA accepts it.

Representations. A transition table lists $\delta(q, a)$ for every $q$ and $a$ (with marks for the start and accepting states). A state diagram draws states as circles (accepting ones doubled), the start state with an arrow from nowhere, and an edge $q \xrightarrow{a} r$ whenever $\delta(q, a) = r$ (parallel edges are drawn as one edge with several labels).

Complete and partial DFAs. In the definition every state has an edge for every symbol. Diagrams in books often omit the edges that lead to a dead state (trap state) $d$, a non-accepting state with $\delta(d, a) = d$ for all $a$; a machine with missing edges is a partial DFA, and the missing edges mean "go to the dead state and reject". When counting states, a complete DFA must include the dead state if it is needed.

How it works

A run

Reading a string is a walk through the diagram: start in $q_0$, and for each symbol follow the edge with that label. There is exactly one such walk, with $|w|$ steps; the string is accepted if the walk ends in an accepting state. The animation shows a DFA for the binary strings that end with $01$: the three states mean "the string so far does not end with $0$ or with $01$" ($q_0$, which includes the empty string), "ends with $0$" ($q_1$), and "ends with $01$" ($q_2$, accepting). On the input $1101$:

Another machine, for the strings over $\{a, b\}$ with an even number of $a$s, run on $abaab$ (three $a$s, so rejected). It has two states: one remembers "even so far", one "odd so far".

Reading a transition table

(An arrow marks the start state, a star an accepting state.) This is the machine of the first animation. To find $\delta^*(q_0, 1101)$: $q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$, an accepting state.

What a DFA can and cannot do

• Time and memory. It makes exactly one transition per input symbol: time $\Theta(|w|)$, and its memory is its current state, a constant amount independent of the input. It can never "count" beyond what its finite number of states can remember: for example no DFA accepts $\{a^n b^n : n \ge 0\}$ (shown with the pumping lemma later).
• Remembering information. Each state stands for a set of strings with the same future: after reading $u$ and after reading $v$ the machine is in the same state only if every continuation $z$ gives the same verdict for $uz$ and $vz$. Designing a DFA means deciding what must be remembered (design patterns).
• Examples. Binary numbers divisible by $3$: the state is the remainder of the number read so far modulo $3$; reading the bit $b$ turns the value $v$ into $2v + b$, so the remainder $r$ becomes $(2r + b) \bmod 3$: three states. Strings with an even number of $a$s: two states. Strings containing $aba$: four states (progress $0$ to $3$ with an absorbing accepting state).

How many DFAs are there?

For $n$ states and $k$ symbols the number of transition functions is $n^{nk}$ (each of the $nk$ table entries is one of $n$ states), there are $n$ choices of start state and $2^n$ choices of accepting set: $n^{nk} \cdot n \cdot 2^n$ labelled DFAs. For $n = 2$, $k = 2$: $2^4 \cdot 2 \cdot 4 = 128$ (many accept the same language). With the start state fixed there are $n^{nk} 2^n$.

Finite languages need dead states

A DFA for the language of all strings of length at most $n$ needs $n + 2$ states: one for each length $0, \ldots, n$ and a dead state for longer strings (checked by counting the distinguishable classes for $n = 1, \ldots, 5$). In general a complete DFA for a finite language whose longest string has length $n$ needs at least $n + 2$ states.

Worked examples

Cheat box

Traps and GATE patterns

Connections

DFAs are drawn like the state machines of digital logic (state machines) but they have accepting states and no outputs. The lexical analyser of a compiler is a DFA (lexical analysis). Design methods are in design patterns; allowing choices gives the NFA, which accepts exactly the same languages.

PYQs

Consider the following two finite automata D1  and
D2  (as shown in the figure).

Which of the following statements is/are true?

Consider the following deterministic finite automaton
(DFA) defined over the alphabet, Σ = {a, b}. Identify which
of the following language(s) is/are accepted by the given
DFA.

THEORY OF COMPUTATION

The above DFA accepts the set of all strings over {0,1}
that

If the final states and non-final states in the DFA
below are interchanged, then which of the following
languages over the alphabet {a, b} will be accepted
by the new DFA?

In the automaton below,s is the start state and t is the
only final state.

Consider the strings u = abbaba, v = bab, and w = aabb.
Which of the following statements is true?

Consider the machine M:

THEORY OF COMPUTATION
The language recognized by M is:

Self-check

Revision card

References