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.


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

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.