Deterministic Finite Automata
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 7

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction
Any physical body or machine, or animal, or even solar system, which
changes its states with time, can be represented by Automata.
Given any initial state and final state, we can think of intermediate
discrete states, through which transition have taken place.
Objective: Use automata to model the behaviour of computer, and
other real life machines, having finite states or assumed to have
finite states.
Automata theory: Abstract mathematical representation of
computational procedures. FA is used in design of lexical analyzers
in compilers, for searching patterns in arbitrarily large texts, natural
language processing, text processing, etc.
FA is simplest computing model, it is a restricted program without
variables.
FA shares its features with computer. It has finite – a very limited
memory, present in CPU only.

kr chowdhary

TOC

2/ 7

Finite Automata

Figure 1: Finite Automaton

A finite automaton has finite set of states Q it can undergo, an
alphabet set Σ, a set of accepting or final states F , where F ⊆ Q, a
starting state s, and a transition function δ , where δ : Q × Σ = Q.
Thus, a FA M = (Q, Σ, δ , s, F ).
If a FA is in state p and makes a transition to state q on reading of
symbol a ∈ Σ, then this transition is represented as δ (p, a) = q.

kr chowdhary

TOC

3/ 7

Finite automata
If there is an input w = abcd on tape, and transitions are like this:
δ (p, a) = q, δ (q, b) = r , δ (r , c) = s, δ (s, d) = t. Thus, at the begin
we have state and input as (p, abcd), which is called as initial
configuration or ID(Instantaneous description) of the FA.
The sequence of transitions through which it will go are:
(p, abcd) ⊢M (q, bcd) ⊢M (r , cd) ⊢M (s, d) ⊢M (t, ε) or we can say
that configuration (p, abcd) goes to configuation (t, ε) through zero
or more transitions, written as: (p, abcd) ⊢∗M (t, ε); the symbol ⊢ is
called “derives.”
The language of M:
L = L(M) = {w |w ∈ Σ∗ , (p, abcd) ⊢∗M (t, ε), and t ∈ F }, ⊢∗M is
transitive relation, and defined as ⊢M : Q × Σ∗ → Q × Σ∗
Given any input symbol and current state there is a definite next
state. Thus, given a start state, and input string it is possible to
determine entire behaviour of a FA. Hence, this FA is called DFA
(deterministic FA).

kr chowdhary

TOC

4/ 7

FA Example
What is regular expressions and FA for:
Q = {q0 , q1 , q2 }, Σ = {0, 1}, F = {q1 }, and δ is given as:
current
input
0
1
state
q0
q1
q2

q0
q0
q2

q1
q2
q1

Figure 2: Transition diagram of corresponding FA.

Regular expression = 0∗ 1(0+ 1 + 10∗ 1)∗

kr chowdhary

TOC

5/ 7

Self test

Which of following are FA? Justify.
1
2
3
4
5
6
7

Digital computer,
analog computer,
digital voltmeter,
analog voltmeter,
chemical reaction,
interaction of radiation with matter,
transformation of water into vapor.

kr chowdhary

TOC

6/ 7

Bibliography

Chowdhary, K.R. (2025). Finite Automata and Regular Expressions.
In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_2

kr chowdhary

TOC

7/ 7