Theory of Computation – Deterministic Finite Automata (DFA) – Definition

As discussed in the earlier tutorial, finite automata are the devices that accept the generated language. They take the symbols from the input tape and change state according to the input symbol. If the change of state is to a single state then the automata is called deterministic. This section describes the deterministic finite automata mathematically. And in this section we will also discuss the processing of the string by a deterministic finite automaton.

A deterministic finite automaton is a 5-tulpe ( Q, Σ, δ, F, q₀), where
Q: is a non-empty finite set of states present in the finite control.
Σ: is a non-empty finite set of input symbols which can be passed on to the finite state machine
q₀: is a starting state, q₀ ϵ Q
F: is a non-empty set of final states or accepting states, set of final states is a subset of Q.
δ: is a function called transition function that takes two arguments a state and an input symbol, it returns a single state. δ maps Q x Σ to Q.
For any element q of Q and any symbol a ϵ Σ, we interpret δ(q, a) as the state to which the FA moves, if it is in a state q and receives the input a.

There can be only one starting state, but there may be more than one final state.

Processing of strings by Deterministic Finite Automata
Suppose a₁, a₂, a₃, . . . ., a_n is a sequence of input symbols. We start out with deterministic finite automata having q₀, q₁, q₂, . . . ., q_n states where q₀ is the initial state and q_n is the final state, the string is then processed by the transition function as follows
δ (q₀, a₁) = q₁
δ (q₁, a₂) = q_k
. .
. .
. .
δ (q_x, a) = q_n

Input a₁, a₂, a₃, . . . ., a_n is said to be accepted since q_n is the member of the set of final states. If the last state reached is not in the set of final states then it is rejected. This concept is used to design the DFA and while deciding the final states and intermediate states of the DFA.

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.