Finite Automata
Prof. Shrisha Rao
IIIT Bangalore
srao@iiitb.ac.in
2025-08-05
1/12
Finite Automata
• An automaton is an abstraction of a device, without regard to
its technology or internal workings. The plural of automaton
is automata.
• The simplest non-trivial automaton is an on-off switch:
• The on-off switch has exactly two states, namely on and
off.
• In general, a finite automaton (FA) has a finite number of
states. The set of states of a FA is denoted by uppercase Q.
2/12
Input Symbols
• A FA also receives an input of some type. For instance, an
on-off switch is typically activated by a finger push.
• The input to a FA is denoted by a symbol such as 0, 1, a, b.
The numerical values or other meanings of such symbols are
not pertinent; they are to be interpreted just as symbols that
denote some inputs to a FA.
• For instance, the “finger push” input to an on-off switch
may be denoted by the symbol 0 (or equivalently, 1, a, etc.).
• The set of symbols accepted by a FA is called the alphabet,
denoted by Σ.
3/12
Denoting a FA
• A FA is denoted with a “bubble diagram” with states denoted
by circles, and transitions between states denoted by arrows.
The labels on the arrows indicate the input symbols.
• For instance, the FA for an on-off switch may be denoted as
follows:
• In general, the states of a FA are denoted by uppercase letters,
as A, B, C, etc. They can also be denoted by qi , q2 , etc.
4/12
Transition Function
• So, a FA has a set of states Q and a set of input symbols Σ.
• It also has a transition function denoted by δ, and given by
δ : Q × Σ −→ Q.
• In other words, δ is given by δ(qi , a) = qj , where qi , qj ∈ Q,
and a ∈ Σ.
• For instance, with the on-off switch, we have
δ(ON, 0) = OFF, and δ(OFF, 0) = ON.
5/12
Denoting a FA as a 5-tuple
A FA can thus also be denoted as a 5-tuple ⟨Q, Σ, δ, q0 , F⟩, where:
• Q is the set of states of the FA;
• Σ is the alphabet of the FA;
• δ : Q × Σ −→ Q is the transition function of the FA;
• q0 ∈ Q is a distinguished state of the FA, called its start state;
and
• F ⊆ Q is the set of accept states of the FA.
6/12
Denoting Start State and Accept States
• In a bubble diagram, a start state (which is often shown
left-most) is denoted by an inward arrow.
• Accept states are denoted by concentric circles (instead of a
single circle).
• For instance, an on-off switch where the switch is supposed
to start in the off position, and where on is the accept state,
may be denoted as follows:
7/12
Strings and Accepted Strings
• A sequence of input symbols given to an automaton is called
a string. Strings may be denoted as 01100, 012 02 , abc, etc.,
depending on the alphabet.
• A string is said to be accepted by a FA if it ends in an accept
state when started from its start state and given that string of
symbols in sequence.
• For instance, the on-off switch started from the off state,
with the on state being the accept state, accepts all strings
with an odd number of 0s.
• The set of strings accepted by a FA is called the language of
the FA. The language of a FA is typically infinite.
8/12
Constructing a FA
A typical exercise in this regard is to construct a FA that accepts a
specified language.
(1) Construct a FA that accepts all binary strings that contain at
least one 0.
9/12
A FA that accepts strings with at least one 0
Solution:
Left for you to do: give the 5-tuple specification of this FA.
10/12
Construct other FAs
(2) Construct a FA that accepts all binary strings that contain at
most one 0.
(3) Construct an FA that accepts all non-zero binary numbers
that are multiples of 4.
11/12
FA that accepts strings with at most one 0
Solution:
Again, give the 5-tuple specification of this FA.
12/12
Further Exercises
For all of these, give a bubble diagram representation as well as
writing down the appropriate 5-tuple specification.
(4) Construct a FA that accepts any string with an odd number
of 1s.
(5) Construct a FA that accepts all strings over {a, b, c} that
contain an odd number of a’s.
(6) Construct a FA that accepts only strings over {a, b, c} where
the progression of the symbols is in reverse alphabetical order.
In other words, cba, ccbbaaa, ba, etc., are all to be accepted,
but aac, aabccab, aabbaccc, etc., are not.
(7) Construct a FA that accepts all non-empty binary strings
where the number of 0s is odd, and the number of 1s is a
multiple of 3.
