Theory of Computation
(CS F351)
BITS Pilani Dr.R.Gururaj
CS&IS Dept.
Hyderabad Campus
Finite Automata
(Chapter-2)
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Concepts
1. We look at the models of Computations and devices for
accepting and generating languages.
2. A restricted model of a computer is a Finite Automaton
or a Finite state Machine
3. The FA shares one common property with a real
computer- Both got a CPU of fixed and finite capacity.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
What a finite automaton does:
It accepts a string as an input, delivered to it on an input
tape.
It produces no output.
But it gives an indication of whether the input string is
approved or disapproved or accepted or rejected.
We can see it as a language recognition device.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Hence an Automaton is a Machine designed to respond to
encoded instructions; a robot.
Uses:
Automata are applicable to algorithms and computer programs.
Ex: 1 The lexical analysis process which identifies program
units like operators, identifiers, constants etc., is often based
on the simulation of Finite Automaton
Ex : 2 The problem of finding the occurrences of a string within
the other
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Operations of a Finite Automaton
Strings are fed into the device through input tape.
1. The tape is divided into squares where we can write a single
symbol.
2. The main part of the machine is called as finite control.
3. At any given instance of time the finite control can be at one
of the specified finite no. states.
4. This finite control can sense the symbols written on the tape,
with a movable Read head.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Initially the RH is placed at the leftmost square of the tape.
Then the FC is in initial state.
At regular intervals automaton reads one symbol from the input
tape then enters a new state depends only on the current
state and the symbol read.
That is why this machine is called by the deterministic finite
automaton.
After reading an input symbol, the read head moves one square
to the right on the tape so that on the next move it will read
the symbol in the next square.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
This process is repeated again and again-
- read symbol,
- move the head to the right,
- change the state of the FC
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
At some point , the reading head reaches the end of the input
string.
The automaton then indicates the acceptance or rejection of
what it has read, by its state at the end.
If the state at the end is one among the final states then it is
accepted.
The language accepted by the machine is set of all strings it
accepts.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Formal definition
A Deterministic Finite Automaton is a quintuple- ( K, , , s, F )
K is a finite set of states
is an alphabet
s K is the start state
F subset of K is the set of final states
is the transition function from K X K
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Rules of transition for a automaton M :
Rules are encoded into the transition function.
Thus the automaton M in state q K and symbol read from the input tape is
a , the transition function is given as (q, a) K is the uniquely determined
state to which the M passes.
Since the automaton is not allowed move its head backwards, it can not visit
the part of the tape which is already read.
Hence the already read part of the string will not influence the future of the
machine.
The language accepted by a automaton M, L(M), is the set of all strings
accepted by M
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Ex 1: Let M be the deterministic finite automaton ( K, , , s, F )
Where K={q0, q2}
= {a, b}
s= {q0}
F= {q0}
And is the function tabulated as follows
State (q) Next (q, )
symbol()
q0 a q0
q0 b q1
q1 a q1
q1 b q0
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
L(M) is the set of all strings in {a, b}*, that have an even number of bs
If the M is given the string aabba
The initial configuration is (q0, aabba) then we have
1. (q0, aabba) (q0, abba)
(q0, bba)
(q1, ba)
(q0, a)
(q0, e)
Therefore (q0, aabba) after multiple moves reaches (q0, e)
Hence the string aabba is accepted by M
Ex 2: Check if the string baabbb is accepted, the previous M or not
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
Deterministic Finite
Transducer
Is a device much like DFA, except that its purpose is not
to accept strings or languages.
But to transform input string into output strings
It starts in a designated state and moves from state to
state depending on the input like DFA.
On each step however it emits a string of zero or more
symbols depending on the current state and input
symbol.
State diagram is similar to that of a DFA except that the
label on an arrow will have a/w, meaning if the
input symbol is a follow this arrow and emit w.
CS F351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus
