# 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, q0), 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
q0: is a starting state, q0 ϵ 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 a1, a2, a3, . . . ., an is a sequence of input symbols. We start out with deterministic finite automata having q0, q1, q2, . . . ., qn states where q0 is the initial state and qn is the final state, the string is then processed by the transition function as follows
δ (q0, a1) = q1
δ (q1, a2) = qk
. .
. .
. .
δ (qx, a) = qn

Input a1, a2, a3, . . . ., an is said to be accepted since qn 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.

Note: Join free Sanfoundry classes at Telegram or Youtube 