Definition of an Automaton:-An Automaton is

defined as a system that preforms certain

functions without human intervention. it accepts
raw material and energy as input and converts
them into the final product under the guidance of
control signals. or an automata is defined as a
system where energy, materials, and information
are transformed, transmitted and used for
performing some functions without direct
involvement of man. Ex: Any automatic machine
like printing machine, washing machine etc.

ip

AUTOMATON
q1, q2, ,qn

o1
o2
...

...

i1
i2
i3

oq

Description of a Finite Automata (Finite State

Machine): A Finite automaton can be represented
by five-tuple structure M(Q,, , q0, F), where

1. Q is a finite non empty set of states.

2. is a finite non empty set of inputs called
the input alphabets.
3.
is a function which maps Q into Q
and is called transmission function (next
state function) (present state input
alphabet next state).

4. q0 Q is the initial state.

5. F Q is the set of final states (may be more
than 1).

Note: Q* into Q means Present state String

of input symbols(including ) Next State.
String being processed

Model of a automaton

$ $ $
Reading Head

Characteristics of automaton:
1. Input: i1, i2,,ip are the input of the model
each of which can take a finite number of
fixed values from an input I.
2. Output: o1, o2,,oq are the outputs of the
model each of which can give the finite
number of fixed values to an output O.
3. States: At any instant of time the automaton
can be in one of the states q1, q2, ,qn.
4. States Relation: The next state of an
automaton at any instant of time is determine
by the present state and present input.
5. Output relation: The output is related to
either state only or to both the input and the
state.
Note: An automaton in which the output depends
only on the input is called an automaton without a
memory. Ex:- logic gate. An automaton in which
the output depends on the state and input is called
an automaton with a finite memory. Ex:- flipflops, shift register, Mealy machine. An
automaton in which the output depends only on
the states of the machine is called Moore
Machine.

$ $
Input Tape

Finite Control
Block diagram of a finite automaton
I)

Input tape: The input tape is divided onto

squares, each square containing a single
symbol from the input alphabet . The end
squares of the tape contain the end marker
$. The absence of the end markers
indicates that the tape is of infinite long.
Input string is processed from left to right.
II) Reading Head: The head examines only
one square at a time and can move one
square either to the left or to the right, we
restrict the movement of reading head
only to the right side.
III) Finite Control: The input to the finite
control will usually be the Symbol under
the reading head and the present state of
the machine. Outputs will be A). A motion
of R-head along the tape to the next
square. B). The next state of the finite
state machine given by (q,a).

Transition system: A Transition system is a

finite directed labeled graph in which each
vertex(node) represents a state and the directed
edge indicates the transmission of a state and
the edges are labeled with input/output.
0/0

1/1
1/0

q0

q1
0/0
Fig. A Transition System.

In Figure, the initial state is represented by a

circle with an arrow pointing toward it, the final
state by two concentric circles and the other
states are represented by a circle. The edges are
labeled by input/output (eq. 1/0 or 1/1).
For example, if the system is in the state q0 & the
input is 1 is applied, the system moves to state q1
as there is a directed edge from q0 to q1 with
label1/0. It output 0.
Definition of Transition System: A transition
System consist of 5-tuple (Q,, , Q0, F).

I. Here Q, and F are finite non empty set of

states, the input alphabets, and set of final
states respectively, as in the case of FA.
II. Q0 Q and Q0 is the non-empty set of initial

Determine the initial and final states.

q0 & q1
q3
101011 will be accepted.
111010 will be rejected.
Properties of Transition Functions:

Property 1: (q, ) = q is a finite automata, This

means that the state of the system can be changed

only by an input symbol.
Property 2:- for all strings w and input symbol a
(q,aw) = ( (q,a)w)
(q,wa)= ( (q,w),a)

This property gives the state after the automaton

consumes or reads the first symbol of a string aw.
Ex: prove that for any input transition function
and for any two input string x and y.
Proof: By method pf mathematical induction
1.

2.

state.

III. is finite Q Q .

In other words, if (q1, , q2) is in . It means that

the graph starts at the vertex q1, goes along a set
of edges and reaches the vertex q2.
A Transition system accepts a string w in * if

i). There exists a path which originates from

some initial state, goes along the arrows and
terminates at some final state.

ii). The path value obtained by concatenation of

all- edge-labels of the path is equal to w.
1/0
0/1

q0
0/0

^/0
q1

q3
^/0

q2

1011/0

(q, xy) = ((q, x), y)

3.

Basis: on |y| i.e. length of y when |y|=1,

y=a.
L.H.S= (q,xa)
= ( (q,x),a) (by using prop. 2)
=R.H.S.

Induction Hypothesis: Assume the result

for all string x and string y with |y|=n.
Let y be a string of length n+1.
Write y=y1a, where |y1| = n.
L.H.S. = (q,xy1a) = (q,x1a) where
x1=xy1
= ( (q,x1)a) ( by using prop. 2).
= ( (q,xy1) a )
= ( ( (q,x), y1 ) a ) by step 2.result
= ( (q,x)y1a)
= ( (q,x)y) = R.H.S.
By the principle of mathematical
induction, this is true for all strings.

Ex.:- prove that if (q,x) = (q,y), then

(q,xz) = (q,yz) for all strings z in +.

Sol:- (q,xz) = ( (q,x)z) by previous results.

= ( (q,y)z) (given)

=(q,yz) (reverse the previous result)

Regular Languages: a regular language over an

alphabet is one that can be obtained from these basic
languages using the operations Union, Concatenation
and Kleene* (Kleene* operation arises from the
concatenation to produce infinite languages).
A regular language can be described by explicit
formula { } by leaving out the set of { } or replacing
them with ( ) and replacing by +; the result is called
a regular expression.
Language

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Corresponding
Regular Expression
{^}
^
{0}
0
{001} or ({0},{0},{1})
001
0+1
{0,1} or ({0}{1})
0+10
{0,10} or ({0} {10})
{1,^}{001}
(1+^)001
{110}*{10}
(110)*(0+1)
{1}*{10}
(1)*10 or 1*0 or 1+0
*
{10,111,11010}
(10+111+11010)*
{0,10}*{{11}*U{001,^}) (0+10)*((11)*+001+^)

Definition:
Regular Languages and Regular
Expressions over : The set R of regular languages
over and the corresponding regular expressions are
defined as follows:

1. is an element of R, then the corresponding RE is .

2. {^} is an element of R, then corresponding RE is ^.

3. For each a is an element of R, and the

corresponding RE is a.
4. If L1 and L2 are any element of R and r1 and r2 are
corresponding RE.
a. L1L2 are any element of R and the
corresponding RE is (r1+r2).
b. L1L2 is an elements of any element of R and
the corresponding RE is (r1r2).

c. L1* is an elements of R and the corresponding

RE is (r1*).
Note: Only those languages that can be obtained
by using statements 1 to 4 are regular languages
over .

Acceptability of a string by a finite Automation:

Definition: A string x is accepted by a finite automaton
M=(Q, , , q0, F) if (q0, x)=q for some q F.
This is basically the acceptability of a string by
the final state,
Example: The FSM is given below
Table:
State
q0
q1
q2
q3

0
q2
q3
q0
q1

Input symbol

q1

1
1

q0
0
0

1
q1
q0
q3
q2

q3

1
q2

Here Q = { q0, q1, q2, q3 }

= {0, 1 }
F = { q0 }

Input String(x) = 110101

( q0, 110101 ) ( q1, 10101 )

( q0, 0101 ) ( q2, 101 ) ( q3, 01 )

( q1, 1 ) ( q0, ) q0
0
1
1
1
1 q
0 q
Hence q0 q1
q3 q1 q0
0
2

This indicates that the current input symbol is

being processed by machine.
Non-Deterministic FSM:
The concept of non-determinism plays a central
role in both the theory of languages and the
theory of computation, and it is useful to
understand this notion fully in a very simple
context initially. The finite automaton model
allows zero, one, or more transitions from a state
on the same input symbol. This model is called a
nondeterministic finite automaton(NFA).

For one input there is one or more output states.

0
q0

aa(NFA)

q1
(a+b)(c+d)

q0

q1

q0
b

q2
Figure: Transition system representing NDA
If an automaton is in a state {q0} and the input
symbol is 0, what will be the next state?, from
figre it is clear that next state will be either {q0}
or {q1}. Some moves of the machine cannot be
determined uniquely by the input symbol and the
present state. Such machines are called NDA.
Definition: A Non-Deterministic Finite Automata
(NDFA) is a 5 tuple (Q, , , q0, F), where
I) Q is a finite non-empty set of states.

II) is a finite non-empty set of inputs.

IV) q0 Q is the initial state; and

V) F Q is the set of final states.

Some rules to generate FA
,
q0

q0

q0

q0

q0

q1

0+1

q0

0 + 10

q0

(1 + ) 001

q0

q1

q2 1

0 ,1

q2

F
1
0 q1 1
1

1+0

q0 1

a
q1

q0

(10+111+11010)

q1

q1

1
F

a
a
aa

0
a

q0

qf

0
q0

q3 1

b
(a+b)c

q1 0

(110)* (0+1)

q0

Some regular Expression and their corresponding FA

a+b

a ,b

q0

q0

a ,b

(a + b)

001

III) is the transition function mapping from

Q into 2Q which is the power set of Q,
the set of all subset of Q.

q4

q2
0

1
q3

Difference between DFA and NDFA is only in .

for DFA outcome is a state, i.e. an element of Q;
for NDFA, the outcome is a subset of Q.

Example: Design a FA over alphabet = {0, 1},

which accepts the set of strings either start with
01 and or end with 01.

Facts of designing Procedure of FA

we can describe some facts or observation of FA
a. In the designing of the FA, first of all we
have to analyze the set of strings i.e.
language which is accepted by the FA.
b. Make sure that every state is check for the
output state for every input symbol of .
c. Make sure that no state must have two
different output states for a single input
symbol.
d. Make sure that there is one initial state and
at least one final state in transition diagram
of FA.

Solution: By the analysis of problem, it is clear

that FA will accepts the strings such as 01,
01111, 010000, 000101, 0001101,.
0, 1

Example: Construct a FA that accepts set strings

where the number of 0s in every string is
multiple of three over alphabet = {0, 1}.
Solution: Multiple of three means number of 0s
on the string may be 0, 3, 6, 9, 12, . . .
1
1

q1

q0

q3

1
q5
Example: Design a FA which accepts the
language L= {w/ w has both an even number of
0s and an even number of 1s over alphabets
= {0, 1}}.
Solution:
1

1
q5
0, 1

1
0

q2

q2

q4

1
Example: Design FA for the Language
L ={(01)I 12j | i1, j1}.
Solution: By analysis Language L, it is clear that
FA will accepts strings start with any number of
01(not empty) and end with even number of 1s.
1
0
0
1
1 q4
1
q0
q3
q1
q2

q2

q0

q0

q1

q1
0 0
q3

example:NFA
0
1

q0
1

0 ,1

q1

q2

0
q3

w =0100

q4

0 ,1

(q0, 0100) = { q0, q3, q4 }

since q4 is an accepting state, the input string will
be accepted by NDFA.

Example: NFA

II.

0 ,1
q0

q1

0 ,1

q2

0 ,1

q3

* (q0, 11) = ( r , 1 )
r (q0,1)
= (r,1)
r(q0,q1)

= (q0,1)(q1,1)

* ( q0 , 01 )

* (q0, 111)

{ q0, q1 } { q2 }
= ( r, 1 )
r (q0,0)
= ( r, 1 )
r { q0 }
= (q0, 1 )
= {q0, q1 }

= ( r, 1 )
r (q0,11)
= ( r, 1 )

r {q0, q1, q2}

= (q0, 1 ) (q1, 1 ) (q2, 1)
= { q0, q1 } { q2 } { q3 }
= { q0, q1, q2, q3 }
The Equivalence of DFA and NDFA:
or Prove that for every NFA, there is an
corresponding FA which simulate the behavior
of NFA. for every string L.
Solution: Before describing the equivalence of
NFA and DFA, let us take a look at the term
equivalence. The term equivalence means equal
in some respect. For example, a BA degree is
equivalent to an B.E. degree, as both are bachelor
degrees, and for appearing in the civil services
examination, either of them is equally applicable.
However, both are not equal, as a person with a
BA degree cannot be appointed as engineer and a
person with a BA degree cannot be appointed as a
history teacher.
I.

A DFA can simulate the behavior of NDFA

by increasing the number of states.

Any NDFA is a more general machine

without being more powerful.

let M = ( Q, , q0, , F ) is an NFA.

M1= (Q1, , q1, 1, F1 ) is a DFA.
I) Q1 = 2Q
II) q1 = { q0 }
III) =
IV) F1 = { q Q1 and q F }
V) 1 (q, a ) = ( r, a )
rq
1 ([q1, q2, , qi] , a ) = (q1, a) (q2, a)
(qi, a)
equivalently
1 ([q1, q2, , qi] , a ) = [ p1, p2, . . ., pj]
if and only if
1 ({q1, q2, , qi} , a ) = {p1, p2, . . . , pj }
1 (q1, x ) = [q1, q2, , qi]
if and only if
(q0, x ) = {q1, q2, , qi}
Prove by using Mathematical Induction
1. Basis: |x| = 0
(q0, ) = { q0 } and
1 (q1, ) = q1 = {q0}
so the equation is true.

2. Assume equation is true for all string y with

|y| = m
1 (q1, y) = (q0, y)
3. let x be a string of length m+1.
x= ya
1 (q1, ya)

= 1 (1 (q1, y),a )
= 1 ( (q0, y),a )
= ( r, a)
r (q0,y)
= ( q0, ya )

Examples: Construct a deterministic

equivalent to M = ( [q0, q1], {0,1}, ,
where is
state/
0
q0
q0
q1
q1

automaton
q0 , {q0} )
1
q1
q0q1

Solution:
i.
The states are subset of {q0, q1} i.e. {},
{q0}, {q1}, { q0, q1}.
ii.
[q0] is initial state.
iii.
[q0] and [q0, q1] are final states, both
states contain q0.
iv.
Transition table for DFA
state/
0
1

[q0]
[q1]
[q0]
[q1]
[q1]
[q0, q1]
[q0, q1]
[q0, q1]
[q0, q1]
When M has n-states, the corresponding FA has
2n states. However, we need not to construct
for all these 2n states. But only for those states
are reachable from {q0}, we halt on when no
more new states appear under the input.
Example:
Find a deterministic acceptor
equivalent to M = ( [q0, q1, q2 ], {a, b}, , q0,
{q2} ) where is
state/
q0
q1
q2

0
q0, q1
q0
__

1
q2
q1
q0, q1

Solution:
M = { 2Q, {a,b}, , [q0], F }
F = { [ q2], [q0, q2], [q1. q2], [q0, q1, q2] }
state/
[q0]
[q2]
[q0, q1 ]
[ q1, q2]

0
[q0, q1]
__
[q0, q1 ]
[q0]

1
[q2]
[q0, q1]
[ q1, q2]
[q0, q1]

Example: Find a deterministic acceptor

equivalent to
M = ({q0, q1, q2, q3}, {a,b}, , q0, {q3} )
where is
state/
q0
q1
q2
q3

0
q0, q1
q2
q3
__

1
q0
q1
q3
q2

Sol: M1 = (2Q, {a,b}, , [q0], F )

F = [q3], [q0. q3], [q1, q3], [q2, q3], [q0, q1, q3],
[q0, q2, q3], [q1, q2, q3] and [q0, q1, q2, q3]
state/
[q0]
[q0,q1]
[q0,q1,q2]
[q0,q1,q3]
[q0, q1, q2, q3]

0
[q0, q1]
[q0,q1,q2]
[q0, q1, q2, q3]
[q0,q1,q2]
[q0, q1, q2, q3]

1
[q0]
[q0, q1]
[q0,q1,q3]
[q0,q1,q2]
[q0, q1, q2, q3]

Example: Convert he NFA given in Figure to

its equivalent DFA.
a,b
a
b
q1
q2
qf
Transition table for the NFA in figure
Current State
Input Symbol
a
b
q1, q2
q1
q1
q2
__
qf
qf
__
__
Transition Table for DFA corresponding to DFA
Current State
Input Symbol
a
b
[q1, q2]
[q1]
[q1]
[q1, q2]
[q1, q2]
[q1, qf]
[q1, qf]
[q1, q2]
[q1]
Example: Convert the NFA given in Table to
Corresponding DFA.
Transition Table for an NFA
Current State
Input Symbol
0
1
q2
qf
q1
q2
__
q3
q3
q4
q3
q4
q3, qf
__
qf
__
q1
Transition Table for DFA corresponding to DFA
Current State
Input Symbol
0
1
[q2]
[qf]
[q1]
[q2]
[q3]

[q3]
[q4]
[q3]

[q4]
[qf]
[q3, qf]
[q1, q3]
[q2, q4]

[q1]
[q1, q3]
[q3, qf]
[q3]

[q3, qf]

[q4]
[q2, q4]
[q3, qf]

Example: Convert the NFA fiven in table to its

corresponding DFA.
Transition Table for an NFA
Current State
Input Symbol
0
1
q0
q1
q0, q2
q1
q2
q0
q2
q0
__

S3

S4

S5

Example: Consider the NFA with - moves

shown in figure.
a
q1
q3

q0
q5
qf

b
q2
q4

Fig: NFA with - moves.

Find the equivalent DFA.
Sol: M = ( Q, , , S, F )
S6

Fig:- NFA with - moves

If there is a NFA M with - moves, then there
exists an equivalent DFA M1 which has equal string
recognizing power or if some NFA M with moves accepts an input string w, then there exists
an equivalent DFA M1 which also accepts w.
Method for constructing equivalent DFA from
given NFA with -moves.
1. Using - closure Method

we use two operations - closure and move().

- closure ( move ( q,a)): Next state from

state q on input a ( Note: - closure( ) = )

Initial state of equivalent DFA is - closure(),

is the initial state of given NFA and final
states are those sets, which have atleast one
final state of given NFA.

Transition Table for DFA corresponding to DFA

Current State
Input Symbol
0
1
[q0]
[q1]
[q0, q2]
[q1]
[q2]
[q0]
[q2]
[q0]

[q0, q2]
[q0, q1]
[q0, q2]
[q0, q1]
[q1, q2]
[q0, q2]
[q1, q2]
[q0, q2]
[q0]

NFA with -moves :

a
S1

b
S2

1. - closure(q): Set of states which are

reachable from state q on - input including
state q. It is equivalent to one state of
equivalent DFA.
2. move(q,a) = set of reachable states on input a
from state q.

S = - closure (initial state of NFA)

= - closure (q0) (state reachable from q0

on input - including q0)
= { q0, q1, q2 }

( S , a ) = - closure ( move ({ q0, q1, q2 },

a ))
= - closure (q3)

= { q3, q5, qf} (next state)

let A = { q3, q5, qf}.
where
( S , b ) = - closure ( move ({ q0, q1, q2 },
b ))
= - closure (q4)
= {q4, q5, qf }
let B = {q4, q5, qf }

Here we have two states A & B. so we have to

define possible transitions from these states and
we continue the process until no next state remain
to be considered.

let A = { q1, q2, q3, q4, q8},where

( S , b ) = - closure ( move ({P}, b ))
= - closure ( ) = .

( A , a ) = - closure ( move ({ q3, q5, qf}, a ))

= - closure ( move ( ) ) = .

( A , a ) = - closure ( move ({ q1, q2, q3,

q4, q8}, a )) = - closure (q5)
= {q2, q3, q4, q5, q7, q8} (next state)
let B ={q2, q3, q4, q5, q7, q8}

( B , a ) = - closure ( move ({q4, q5, qf }, a ))

= - closure ( move ( ) ) = .

( A , b ) = - closure ( move ({ q1, q2, q3,

q4, q8}, b )) = - closure (q6, qf)
= {q2, q3, q4, q6, q7, q8, qf} (next state)
let C = {q2, q3, q4, q6, q7, q8, qf}

( A , b ) = - closure ( move ({ q3, q5, qf}, b ))

= - closure ( move ( ) ) = .

( B , b ) = - closure ( move ({q4, q5, qf }, b ))

= - closure ( move ( ) ) = .
state/
S
A
B

Table for DFA

a
A

Q = { S, A, B }
= { a, b}
F = { A, B }

( B , a ) = - closure ( move ({q2, q3, q4, q5,

q7, q8}, a )) = - closure(q5)
={q2, q3, q4, q5, q7, q8} =B

b
B

( B , b ) = - closure ( move ({q2, q3, q4, q5,

q7, q8}, b )) = - closure (q6, qf)
= {q2, q3, q4, q6, q7, q8, qf} = C.
( C , a ) = - closure ( move ({q2, q3, q4, q6,
q7, q8, qf}, a )) = - closure(q5)
={q2, q3, q4, q5, q7, q8}=B

Example: Consider the following NFA with moves. Construct an equivalent DFA.
a
q3
q5

q1
q2
q7
q8

b
q4
q6

Figure: NFA having - moves

let M = ( Q, , , S, F ) is an equivalent DFA
S = - closure (initial state of NFA)
= - closure (P) (state reachable from P on
input - including P)
= { P } (next state)
( S , a ) = - closure ( move ({ P }, a ))
= - closure (q1)
= { q1, q2, q3, q4, q8} (next state)

( C , b ) = - closure ( move ({q2, q3, q4, q6,

q7, q8, qf}, b )) = - closure (q6, qf)
= {q2, q3, q4, q6, q7, q8, qf} = C.

q9

state/
S
A
B
C

a
A
B
B
B

C
C
C

B
a
a
2. Removal of Null Moves
The basic Strategies for the removal of null
string are as follows:
Let A and B be the two states connected by a
null string .

Strategy 1: If A is an initial state, then move A to

overlap B with all its connected structures as
shown in figure.
a

b) Concatenation
f1

q0 = q1

Strategy 2: If B is a final state, then move B to

overlap A with all its connected structures as
shown in figure.
a
a

B
A
B

Strategy 3: If A is the initial state and B is the

final state, then move A to overlap B with all its
connected structures and make A the final state
as shown in figure.
a
a
A

f2

f1

q2

f2

Concatenation(PQ)
c) Kleene*

qf

f1

q1
f1

Kleenee* P*

Strategy 4: If both A and B are normal states (

neither final nor initial), either can be moved to
overlap the other with all its connected
structures.

Equivalent of FA to a Regular Set: The method

going to give for constructing a finite automaton
equivalent to a given regular expression is called
subset method which involves two steps.

Note: If there is confusion in removing the null

moves, remove them using -closure as
discussed earlier.

Step 1: Construct a transition graph equivalent to

the regular expression using - moves. This is
done by kleenes theorem.

Kleenes Theorem:

(a)

(c)

(b)

a) Union
f1

q0

q1
f1

q2

f2
f2
Union(P + Q )

q8

Step 2: Construct the transition table for the

transition graph obtained in step 1. Using the
method conversion of NFA to DFA & construct
the equivalent DFA.
Example:- Construct a finite automaton for the
regular language represented by the regular
expression (a + b )*cd*e.
Solution: The following steps details the
creation of the finite automaton for the given
expression:
Step 1: The regular expression (a + b)* means
the repetition of the symbol a and b any number
of times (including zero) and in any order. Thus,
the automaton for this part of the regular
expression is given by loop that repeats for both
a and b at any state as shown in figure i.

0,1

Step 2: The finite automaton corresponding to

the regular expression cd* consists of an arc with
the c. this arc comes from the previous state of
the finite automaton from where cd* follows
sequentially. This arc ends on a state, say A, on
which there is a loop to indicate the nuber of
repetitions (including zero) of d. The part of the
finite automaton corresponding to the regular
expression cd* is shown in figure 2.
Step 3: The finite automaton corresponding to
the regular expression e, consists of an arc with
label e coming from a previous state and ending
into some state, say F. since e is the last part of
the total regular expression (a + b )*cd*e, F has
to be a final state. The part of the finite
automaton corresponding to the regular
expression e is shown in figure 3.

q0

(a)

(0 +

1)*

q1

(0 + 1)

q5

(00 + 11)

q2

(b)

(00 + 11)

q1

(0 +

q2

q6

q1

q7 1

0,1
q2

q8
(e)

qf

10

qf
( 0 + 11) 0*1
(b)
q1
0

0+11

q2

q0
1

q4

q0
qf

qf

q3

(c)
q1

qf

(0 + 1)

(d)

(a)

q0

qf

1)*

q8

q6

q0

Solution: (Construction of transition graph): First

we construct the transition graph with -moves
then eliminate -moves.
q0

q2

10 + ( 0 + 11) 0*1

q0

Example: Construct the FA equivalent to the RE

(0 + 1)*(00 + 11)(0 + 1)*

(0 + 1)*(00 + 11)(0 + 1)*

q1

0, 1

Solution: (Construction of transition graph): First

we construct the transition graph with -moves
then eliminate -moves.

Figure 4

Figure 3

Example: Construct the FA equivalent to the

regular expression 10 + ( 0 + 11) 0*1

a, b

Figure 2

Figure 1

q0

q5

0,1

Step 4: The complete finite automaton for the

regular expression (a + b )*cd*e can be obtained
by combining the finite automata in fig 1 -3
serially, as shown in figure 4.
d
a, b
c
Previous
A
State
S

Previous
State

q0

q7

qf

q3

(d)
q1

q2

q2

d
(e)

qf

qf

Example: Design a grammar generating the

language L = { wcwR| w (a, b)+}.

Solution: (a, b)+ indicates that w contain at

least one symbol. The example strings are in
the language L are aca, abcba, bbcbb, aacaa,
abbcbba, . . . Thus productions P are

Example: Design a grammar generating the

language L = { anbncn | n 1 }.

Example: Design a grammar generating the

language L = {anbn | n 1 }.

Solution: Every string w belonging to the

language begins with a substring containing a
symbols. This follows a substring of equal
number of b symbols, which further follows
the substring of same number of c symbols.
The example strings in the language L are abc,
aaabbbccc, aabbcc, aaaabbbbcccc, . . . etc. Thus
the productions P are:

S aSb | ab

Example: Design a grammar generating the

language L = { ww | w (a, b)+ }

S aSa | bSb | aXa| bXb

Xc

Solution: Every string contains equal number

of as and bs. Every string w in L contains a
substring of as followed by a substring of
equal number of bs. The example strings in
the language L are ab, aabb, aaaabbbb, aaabbb,
. . . . Thus productions P are

Example: Design a grammar generating the

language L = { ancmbn | m, n 1 }.

Solution: every string w belonging to the

language begins with a substring containing a
symbols. this follows a substring of c symbols.
the substring of cs follows the substring of b
symbols and the number of bs is the same as
that of as. the example strings in the language
are acb, accb, aacccbbb, aaaccbbb, . . . . Thus,
we have the set of productions P as follows:
S aSb | aXb
X cX | c.

Example: Design a grammar generating the

language L = { anbm |m, n 1 }.

Solution: every string w belonging to the

language begins with a substring containing a
symbols. This follows substring of b symbols
and the number of bs are independent of as.
The example strings in the language L are ab,
aab, abb, aabbbb, abbb, abbb, etc. Thus the
productions P are:
S AB
A aA | a
B bB | b

S aSXc | abc
cX Xc
bX bb
it can be seen that every string in the language
L has the length 3n.

Solution: we see that each string in the language

L is of the length 2n (n 1). The first substring
of length n is the same as that of the subsequent
substring of length n. The example strings in the
language L are aa, abab, bbbb, baba, bbabba,
babbab, . . . . thus productions P are :
S XYZ
XY aXA | bXB
AZ YaZ
BZ YbZ
Aa aA
Ab bA
Ba aB
Bb bB
aY Ya
bY Yb
XY
Z
Example: Design a grammar for a language of
all palindromes over {a, b}.
Solution: The basis for our grammar is as
follows:

Note: Final state is also known as Accepting state.

An alphabet a or b is a palindrome. If a string x

is palindrome then the strings axa and bxb are
also palindromes. thus the grammar can be
designed as follows:
S aSa | bSb | a | b | aa | bb.

Example: Design a grammar for a language L

over {a, b} such that each string in L contains
equal number of as and bs.

Solution: The string can start with either a or

b. Thus, we have the production
S aX | bY

Now the design of X should be such that it

inserts one b more than a in the output string.
Similarly, design of Y should be such that it
inserts one a more than b in the output string,
Thus, we have
X b | aXX | bS
Y a | bYY | aS

Questions: Find the regular

corresponding to following:

expression

1. a, b starting from (abb)

- abb ( a + b )*
2. a, b ending with (baa)
- ( a + b )* baa
3. a, b ending with (baa) and starting
with (abb).
- abb ( a + b )* baa
4. a, b containing exactly 2as
- b*ab*ab*
5. a, b containing atmost 2as
- b* + b*ab* + b*ab*ab*
6. a, b containing atleast 2as
- b*a ( a + b)* a (a + b)*
7. a, b containing abb as substring
- ( a + b)* abb (a + b )*
8. String of length 2.
- (a + b) (a + b) or ( a + b)2
9. String of length 6.
- (a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
10. String of length 2 or less.
- (+a+b)(+a+b)

11. String of even length

- (aa + ab + ba + bb)*
12. String with odd number of 1s
- 0* ( 10*10* )* 10*
13. String of length of 6 or less.
- ( + 0 + 1 )6
14. Strings ending with 1 and not containing 00
- ( 1 + 01 )+
15. Language of C identifiers.
- ( l + _) ( l + d + _ )*
16. Real Literals in Pascal
- sd+(pd+ + pd+Esd+ + Esd+ )
17. Strings Containing exactly 2 0s
- 1*01*01*
18. String containing atleast 2 0s.
- 1* 0 ( 1 + 0 ) * 0 ( 1 + 0 ) *
19. Strings that do not end with 01.
- + 1 + (0 + 1 )*0 + ( 0 + 1 )*11
20. Strings that begin or end with 00 or 11.
- (00 + 11) (0 + 1 )* + ( 0 + 1 )* ( 00 + 11 )
21. Strings not containing the substring 00
- ( + 0 ) ( 1 + 10 )* or ( 1 + 10 )* ( + 0 )
22. Strings in which the number of 0s is even
- 1* ( 01* 01* ) *
23. Strings containing no more than one
occurrence of the string 00.
- ( 1 + 01 )* ( + 0 + 00 ) ( 1 + 10 )*
24. Strings in which every 0 is followed
immediately by 11.
- 1* ( 011+ )*
25. { 0, 1, 2}
0+1+2
2n + 1
26. { 1
|n>0}
- ( 11 )+ 1
27. { w { a, b }* | w has only one a }
- b*ab*
28. Set of all strings over { 0, 1} which has
atmost 2 0s.
- 1+ + 1*01* + 1*01*01*
29. { a2, a5, a8, . . . }
- (aaa)*aa
30. { an | n is divisible by 2 or 3 or n = 5 }
- (aa)* + (aaa)* + aaaaa
31. Strings beginning and ending with a.

- a ( a + b )* a
32. Strings having atmost one pair 0s or
atmost one pair of 1s.
- ( 1 + 01)* + ( 1 + 01)* 00 ( 1 + 10)* +
( 0 + 10 )* + ( 0 + 10)*11(0 + 01 )*
33. String in which number of occurrences of
a is divisible by 3.
- ( b* a b* a b* a b*)*
34. String with 3 consecutive
- ( a + b )* bbb ( a + b )*
35. Strings beginning with 00
- 00 ( 0 + 1 )*
36. String ending with 00 and beginning with 1.
- 1 ( 0 + 1 )* 00
Difference between DFA and NDFA
Sr.

DFA

NDFA

1.

Deterministic
Finite Automata

Non-Deterministic
Finite Automata

2.

Every transition is
unique
and
deterministic
in
nature.

Multiple transition for

an input on a state are
possible, which means
moves
are
nondeterministic in nature.

3.

Null-transitions
are not allowed

Null-transitions
allowed.

4.

Requires
less
memory
as
transition diagram
needs less number
of states.

Requires
more
memory as transition
diagrams needs more
number of states.

5.

Range
transition
:QQ.

6.

are

of Range of transition is
is :Q2Q

All DFAs are All DFA are NDFA.

NDFAs but vice
versa is not true.

2. Text Editor: smart and speedy text

editors can be constructed using FA.
3. Spell checkers: spell checkers can be
designed using FA. In our computer
system, we have a dictionary, FA can
recognize the correctness of a word and
can give the appropriate suggestion to the
users also.
4. Sequential Circuits: FA can also be used
to design sequential circuits.
5. Image Processing.
6. Natural Language Processing.
7. Internet Browsers: To scan large body of
information.
8. Communication: Designing of protocols
for exchange of information.
9. Pattern matching.
10. Forensic Science
11. Cellular machines uses cellular Automata
Limitations of Finite Automaton:
FA is most restricted model of automatic
machines. It is an abstract model of a computer
system. a FA has following limitations:
1.
2.
3.
4.
5.

6.

7.

8.
Applications of Finite Automaton.
1. Lexical Analyzers: Lexical analysis is a
part of compilation and used to recognize
the validity of input programs. Whether
the input program is grammatically
constructed or not.

9.

The memory is limited.

Memory is read-only memory.
Memory is sequentially accessed.
FA has only string recognizing power.
Head movement is restricted in one
direction, either from left to right or from
right to left.
Limited Computability mean it can act
like a scanner FA are not computing
devices but these act only as scanner.
Periodicity: FA cannot remember large
amount of information or strings of large
size.
Impossibility of Multiplications: Full
length of multiplier and multiplicand
cannot be stored.
Binary Response: Response of FA is
binary either accepted or rejected after a
long sequence of moves.

0
Moore and Mealy Machines: Finite automata
with output: The finite automata which we were
considered in the earlier have binary output i.e.
either they accept the string or they do not accept
the string. This acceptability was decided on the
basis of the reachability of final state by the
initial state. Now, we remove this restriction and
consider the model where the outputs can be
chosen from some other alphabets.
The value of the output function Z(t) in the most
general case is a function of the present state q(t)
and present input x(t), i.e.
Z(t) = (q(t), x(t) )
Where is called the output function. This
generalized model is usually called the mealy
machine.
if the output function Z(t) depends only on the
present state and is independent of the current
input, the output function may be written as

q0/0

q3/0
0
1

q1/1

0
q2/0

0
Transition graph
input string 0111
0

q0

q3 1

q0 1

q1 1

q2

output 00010

Definition: A Mealy machine has 6-tuple

(Q, , ,, ,q0), where
I.
II.
III.
IV.
V.
VI.

Q is a finite set of states.

is the output alphabet,
is the input alphabet,
is the transition function Q into Q.
is the output function mapping Q into .
q0 is initial state.

Z(T) = (q(t))
Example: Mealy Machine

this restricted model is called the Moore machine.

Definition: A Moore machine has 6-tuple
(Q, , ,, ,q0), where
I.
II.
III.
IV.
V.
VI.

Q is a finite set of states.

is the input alphabet,
is the output alphabet,
is the transition function Q into Q.
is the output function mapping Q into .
q0 is initial state.

Present
state
q0
q1
q2
q3

Example: Moore Machine

Next State
a=0
a=1
q3
q1
q1
q2
q2
q3
q3
q0

Present
State

Next State
a=0
a=1
state
output
state
output
q3
0
q2
0
q1
1
q4
0
q2
1
q1
1
q4
1
q3
0

q1
q2
q3
q4

q3

Output
( )
0
1
0
0

0/1

q1

0/1

q4

q2
Transition graph
Input string : 0011
q1

q3 0

Output String = 0100

q2 1

q4 1

q3

Note: for a Moore machine, if the input string is

of length n, the output string is of length n+1. The
first output is (q0) for all output strings. In the
case of a Mealy machine if the input string is of
length n, the output string is also same length.
Convert the Following Moore Machine to Mealy
Machine.
Present
State
q0
q1
q2
q3

Next State
a=0
a=1
q3
q1
q1
q2
q2
q3
q3
q0

Output
()
0
1
0
0

Present
a=0
a=1
State
Next
O/p
Next
O/p
q3
0
q1
1
q0
q1
q1
1
q2
0
q2
q2
0
q3=
0
q3
q3
0
q0
0
Convert the Following Moore Machine to Mealy
Machine.
Present
State
q1
q2
q3
Present
State
q1
q2
q3

Next State
a=0
a=1
q1
q2
q1
q3
q1
q3

Next
q1
q2
q3

a=0

O/p
0
0
0

Next
q2
q3
q0

Output
()
0
0
1
a=1

O/p
0
1
1

Convert the Following Mealy Machine to Moore

Machine.
Present
State
q1
q2
q3
q4

Next
q3
q1
q2
q4

a=0

O/p
0
1
1
1

Next
q2
q4
q1
q3

a=1

O/p
0
0
1
0

Present
State
q1
q20
q21
q3
q40
q41
Present
State
q1
q20
q21
q3
q40
q41

Next
q3
q1
q1
q21
q41
q41

a=0

O/p
0
1
1
1
1
1

Next
q20
q40
q41
q1
q3
q3

Next State
a=0
a=1
q3
q20
q1
q40
q1
q41
q21
q1
q41
q3
q41
q3

a=1

O/p
0
0
1
1
0
0

Output
()
1
0
1
0
0
1

Convert the Following Mealy Machine to Moore

Machine.
Present
State
q1
q2
q3

Next
q2
q2
q2

Present
State
q1
q21
q22
q3
q3

Next
q21
q22
q22
q21
q21

Present
State
q1
q21
q22
q3
q3

a=0

a=0

O/p
z1
z2
z1

Next
q3
q3
q3

O/p
z1
z2
z2
z1
z1

Next
q31
q31
q31
q32
q32

Next State
a=0
a=1
q21
q31
q22
q31
q22
q31
q21
q32
q21
q32

a=1

a=1

O/p
z1
z1
z2

O/p
z1
z1
z1
z2
z2

Output
()

z1
z2
z1
z2

Question: Design a Moore machine which counts

the occurrence of substring aab in input string.
Solution: Let the Moore machine be
M0 = (Q, , , , ,q0)
Q = { q0, q1, q2, q3 }
= { a, b}
We will design this machine in such a way that
machine prints out the character 0 except for q3,
which prints a 1. To get q3, we must come from
state q2 and have 1st read b. To get state q2, we
must read atleast two as in a row, having started
in any state.
={0,1}
(q0) = 0, (q1) = 0, (q2) = 0, (q3) = 1
The following machine will
occurrence for us.
a

counts

aab

a
q0/0

q0/1
b

q0/0 b

q0/1

By the analyzing mealy machine transition

diagram, we can easily notice that it is also finite
automata without any final state and output is
there for input-symbol on corresponding
transition. Output for every input symbol is
represented as level on each transition
corresponding output. For e.q. in between q1 and
q2 is labeled by 0/1, 0 is input symbol and 1 is the
output symbol.
Question: Design a mealy machine, which prints
1s complement of input bit string over alphabet
= { 0, 1}.
Solution: If input string is 101110 then 1s
complements of 101110 will be 010001, so we
have to design a mealy machine which will print
output 010001 for the input string 10110.
M0 = (Q, , , , ,q0)
Q = { q0 }
= { 0, 1}
={0,1}
q0 is the initial state.

0/1

Question: Construct a mealy machine which

calculates the residue mod-4 for each binary
string treated as binary integer.
Solution: When we divide any number by 4 then
remainder can be 0, 1, 2, &3. so clearly mealy
machine will have four states.
Let the Mealy machine be
M0 = (Q, , , , ,q0)
Q = { q1, q2, q3, q4 }
= { a, b}
={0,1}
q1 is the initial state & is transition function.
( q1, 0 ) = 0
( q1, 1 ) = 0
( q2, 0 ) = 1
( q2, 1 ) = 0
( q3, 0 ) = 1
( q3, 1 ) = 1
( q4, 0 ) = 1
( q4, 1 ) = 0
Transition Diagram for M0 is as follows:
0/1
q1

1/0

1/0

1/0
Question: Construct a mealy machine which
calculate residue mod-4 for each binary string
treated as binary integer.
Solution:
M0 = (Q, , , , ,q0)
Q = { q0, q1, q2, q3 }
= { 0, 1}
= { 0, 1, 2, 3}
0/0
q0

1/3
1/1

0/2

0/0
q2

0/1

1/3

q1

1/1

q2
1/0

0/0

q0

0/2

q3

Ardens Theorem: let P and Q be two regular

expressions over . If P does not contain , then
the following equation in R, is

Conversion of FA to Regular Expression.

Example: The transition system is given in figure.

R = Q + RP ---(i)

a
q1

has a unique solution QP*---(ii)

Proof: let us First check if QP* is a solution to
(i). To check this, let us substitute R by QP* on
both sides of (i)
R = Q + RP = Q + QP*P = Q ( + P*P) = QP*
Hence eqn(i) is satisfied when R = QP*. This
means R = QP* is a solution of eqn(i).
Let us check if it is the only solution. To do this,
replace R by Q + RP on the Right Hand Side. of
eqn(ii), we get
R = Q + RP = Q + ( Q + RP )P
= Q + QP + RP2
= Q + QP + ( Q + RP )P2
= Q + QP + QP2 + RP3

b
q2

i+1

= Q + QP + QP + + QP + RP

= Q ( + P + P2 + + Pi) + RPi+1

We now show that any solution of equation (i) is

equivalent to QP*.
Let w be the string of length I in the set R. then w
belongs to the set Q ( + P + P2 + + Pi) +
RPi+1. As P does not contain , RPi+1 has no
string less than i+1. This means that w belongs to
the set RPi+1. This means that w belongs to the set
Q ( + P + P2 + + Pi) and hence to QP*.
Rules for using Ardens Theorem:

1. The transition graph does nt have - moves.

2. It has only one initial state.
3. Vi the regular expression ( of final state)
represents the set of strings accepted by the
system ( Vi is final state).
4. q = qi (incoming edge) alphabets + (only
for initial state).

a
q3

Prove that the strings recognized are

( a + a ( b + aa)* b )* a ( b + aa ) * a
we can directly apply the method since the graph
does not contain any -move and there is only
one initial state.
q1 = q1a + q2b +
q2 = q1a + q2b + q3a
q3 = q2a
reduce the number of unknowns by repeated
substitution.
q2 = q1a + q2b + q3a
q2 = q1a + q2b + q2aa
q2 = q1a + q2( b + aa )
R= Q+R P

...
2

q2 = q1a( b + aa )*
Now substitute q2 in q1

QP*

q1 = q1a + q2b +

q1 = q1a + q1a ( b + aa )*b +

q1 = q1( a + a(b + aa )* +

R = R
q1 =

+ Q QP*

.( a + a(b + aa )*)*

= ( a + a(b + aa )*)*

q2 = ( a + a ( b + aa )*)*a( b + aa )*
q3 = ( a + a ( b + aa )*)*a( b + aa )*a
Since q3 is a final state, the set of strings
recognized by the graph.
Example:

a
q1
b
a

q3

q2
a

b
b

q4

We can directly apply the method since the graph

does not contain any -move and there is only
one initial state.
q1 = q2b + q3a +
q2 = q1a

q3 = q1b

q4 = q2a + q3b + q4a + q4b

Proof: suppose that the set Q has n elements. for

any string x in L with length atleast n. of we write
x = a1a2an;

q1 = q2b + q3b +

q1 = q1ab + q1ba +

then the sequence of n+1 states.

q1 = q1 (ab + ba ) +
R =R

q0 = * ( q 0 , )

+ Q QP*

q1 = * ( q0 , a1 )

q1 = .(ab + ba )*
q1 = (ab + ba )*

q2 = * ( q0 , a1a2 )
q3 = * ( q0 , a1a2a3 )
. . .

Example:-

0
q1

Pumping
Leema
for
regular
Languages/Regular Sets:
Pumping Lemma: let M = (Q, , , q0, F ) be a
finite automaton with n states. let L be the regular
set accepted by M. let x L and |x| n, then there
exists such that x = , and m L
for each m 0.

q2

0, 1
0

q3

We can directly apply the method since the graph

does not contain any -move and there is only

one initial state.

q1 = q10 +

q2 = q11 + q21
q3 = q20 + q3( 0 + 1 )
q1 = q10 +

R = RP + Q QP*
q1 = .(0)* = 0 *
q2 = q11 + q21
q2 = 0*1 + q21

R = Q + RP QP*
q2 = 0*11*

As the final states are q1 and q2, we need not

solve q3.
q1 + q2
0* + 0*11*
0* ( + 11*) = 0*1*

qn = * ( q0 , a1a2. . . an )

qi
q0
suppose qi = qi + p

qf

0ii+pn
then
* ( q0 , a1a2. . . ai ) = qi
* ( qi , ai+1ai+2. . . ai+p ) = qi+p = qi
* ( qi , ai+p+1ai+p+2. . . an ) = qf F
To simplify the notation,
let = a1a2. . . ai

= ai+1ai+2. . . ai+p
= ai+p+1ai+p+2. . . an

if i 0 will be
if i + p 0 will be

since * ( qi , ) = qi , have * ( qi , m ) = qi for

every m 0 and it follows that
* ( q0 , m ) = qf for every m 0 since p > 0
and i + p n.
Note: The decomposition is valid only for strings
of length greater than or equal to the number of

states. for such a string x = as many times as

we like and get strings of the form m which
are longer than and are in L. by considering
the path from q0 to qi and then the path from qi to
qf ( without going through the loop), we get a
path ending in a final state with path value (
this corresponds to the case when m = 0).
Application of Pumping Lemma:
This problem can be used to prove that certain
sets are not regular. we now give the steps needed
for proving that a given set is not regular.
Step 1: Assume that L is regular. Let n be the
number of states in the corresponding FA.
Step 2: Choose a string x such that |x| n, use
pumping lemma to write x = with || n and
|| > 0.
m

Step 3: Find a suitable integer m such that

L. this contradicts our assumption Hence L is
not regular.
2

Example: Show that the set L = { a i | I 1 } is

not regular.
1

16

Sol: L = {, a , a , a , a , . . . }
= { , a, aaaa, aaaaaaaaa, . . . }

Hence, | 2 | strictly lies between n 2 and ( n +

1)2, but is not equal to any one of them. thus, |
2 | is not a perfect square and so 2 L. but
by pumping lemma, 2 L. this is
contradiction. thus L is not regular.
Example: Show that L = { aQ | Q is a prime} is
not a regular.

Solution: Step 1: We suppose L is a regular. let n

be the number of states in the finite automaton
accepting L.
Step 2: Let Q be a prime number greater than n.
let x = aQ. by pumping lemma, x be written as x =
, with || n and || > 0. , , are simply
strings of as. so = ap for some p 1 (and n).
Step 3: let m = Q+1, the |m|
= || + | m-1| = Q + (m-1)p = Q + QP =
Q(1+p).
by pumping lemma, m L. but |m|= Q +
Qp = Q(1+p) and Q(1+p) is not prime. so m
L. this is contradiction. thus L is not regular.
Example: Show that L = { 0i1i | i1} is not
regular.

Step 1: Suppose L is regular. let n be the number

of states in finite automaton accepting L.

Solution: Step 1: Suppose L is regular. Let n be

the number of states in the finite automaton
accepting L.

Step 2: let x = a n . then |x| = n 2 > n. by

pumping lemma, we can write x= with ||
n and || > 0.

Step 2: let x = 0n1n. then |x| = 2n > n. by pumping

lemma, we write x = with || n and || > 0.

Step 3: Consider .
| 2 | = | | + 2|| + | | > | | + || + || as || >
0.
this means

n 2 = | | = | | + || + || < | 2 |
as || n we have || n. therefore
| 2 | =| | + 2|| + | | n 2 + n.
i.e.

n 2 <| 2 | n 2 + n < n 2 + n + n + 1

n 2 <| 2 | < ( n + 1)2

Step 3: we want to find m, s the m L for

getting a contradiction. the string can be in any
of the following:
case 1: has only 0s i.e. = 0k for some k1.
case 2: has only 1s i.e. = 1l for some l1.
case 3: has both 0s and 1s i.e. = 0k1l for
some k, l1.
in case 1, we can take m=0, as = 0n1n, =
0n-k1n. as k1, n-kn so L.

In case 2, we can take m =0, as = 0n1n, =

0n1n-l. as l1, n-ln so L.

In case 3, we can take m =2, as = 0n-k0k1l1n-l.

2 = 0n-k0k1l0k1l1n-l, as 2 is not of the form
0n1n, 2 L. thus in all the cases we get a
contradiction. Thus L is not regular.
Example: Show that L = {zz | z{a, b}*} is not
regular.
Sol: Step 1: suppose L is regular, let n be the
number of states in the automaton M accepting L.
Step 2: let us consider zz = anbanb in L |zz| =
2(n+1) > n. we can apply pumping lemma to
write zz = with || n and || > 0.
Step 3: We want to find m so that m L for
getting a contradiction. the string can be in only
one of the following form:
case 1: has no bs i.e. y =ak for some k1.
case 2: has only one b.
we may note that can not have two bs if so ||
n+2. but || || n.
in case 1, we can take m =0. then 0 = is of
the for an-kbanb, here n-k n, we can not write
in the form so L.

In case 2, we can take m = 0. then 0 = has

only one b ( as one b is removed from , b
being in ). so L as any element in L should
have an even number of as and an even number
of bs. thus in both case, we get a contradiction.
therefore, L is not regular.
2n

Example: Is L = {a | n 1} regular?
Solution: We can write a2n as aa(a2)m, where m
0 } is simply {a2 }* so L is represented by the
regular expression aa(P)*, where P represents
{a2}. the corresponding FA is shown in figure:

q0

q1

qf

q2
a

Pumping lemma fails to solve this problem

because this is a regular grammar.
Closure properties of Regular sets:

The term closure property relates to a

mathematical system (structure) containing a set
and operations performed on the elements of the
set. For example, let I+ be the set of positive
integers and addition (+) and subtraction (-) be the
two operations performed on the elements of this
set. When the addition operation is performed on
the elements of this set the result obtained is some
positive integer and belongs I+. When the
subtraction operation is performed, the result
obtained may or may not belongs to I+. Thus the
execution of the addition operation does not
violate the boundary of the set I+ whereas
subtraction may do so. We say that the set I+ is
closed over the addition operation but not over
subtraction. Similarly, a set of all 3 3matrices is
closed over the operation of addition, subtraction
and transpose, but not over the operation of the
determinant.
Every regular set can be expressed by its
corresponding regular expression. In addition, for
every regular expression, there exists a
corresponding regular set. If an operation
performed on regular set(s) leads to another set,
which is also regular, then the regular set(s) are
closed over that operation.
The regular sets are closed over the operations of
union, concatenation, transpose, complement,
intersection, difference and Kleenes star.
1. Regular sets are closed over the union
operation.
Proof: let S1 and S2 be two regular sets
associated with regular expressions R1 and R2
respectively. Let there be a set S3 = ( S1 S2).
then every element of S3 can be expressed
either by expression R1, R2 or both. Thus, the
set S3 can be generated by the regular
expression (R1 + R2). The association of S3
with regular sets has generated a regular set,
regular sets are closed over the Union
operation.
2. Regular sets are closed over the concatenation
operation.

Proof: Let S1 and S2 be the two regular sets

associated with the regular expressions R1 and
R2 respectively. Let there be a set S3 created
by the concatenation of the elements of S1 and
S2 in order. Now each string belonging to S3 is
such that it can be decomposed into two parts,
with the first belonging to S1 (corresponding
to R1) and the second to S2 (corresponding to
R2). Thus, every element of S3 can be
generated by the regular expression R1R2. The
association of S3 with a regular expression
(R1R2) indicates that S3 is a regular set. Since
concatenation of two regular sets has
generated a regular set, regular sets are closed
over concatenation operation.
3. Regular sets are closed over the transpose
(string reversal) operation.
Proof: Let S1 be a regular set associated with
the regular expression R1. let M1 be the finite
automaton corresponding to R1. Now, for
every string (w S1), there is a path in M1
from the initial state to final state. Now, the
following operations are performed on M1 to
create a new finite automaton, say M2.
a. Reverse the direction of every arc/arm.
b. Change the initial state ( origionally in
M1) to the final state.
c. Create a new start state S and connect it
to all the acceptor states of M1 using transitions.
d. Remove all -transitions.
Let S2 be a set of all strings accepted by M2.
Now every string (xS2) is reverse
(transpose) of some string (wS1) thus S2 is a
set of transposed strings of S1. Since S2 is
associated with a finite automaton M2, it is
associated with a regular expression, Hence
S2 is a regular set has created another regular
set, regular sets are loosed over the transpose
operation.
0
1
q0

q1

d0,1
Fo

q0

q1

q2

0,1

If final state is reachable from initial state then LT

is also regular.
4. Regular sets are closed over the complement
operation
Proof: let L be a regular set(language) over
the character set ; then its complement L is
a set of all string over * that are not in L,
that is L = * - L.
Let M be the finite automaton for the language
L. now, covert all the final states ofM to nonfinal states and vice versa to generate a new
finite automaton, say M. Now, if for a string
, M stops in final state the M stops in the
non-final state and viceversa. Hence M is the finite automaton for
Since there is a finite automaton for ,
is
a regular set. Hence, regular sets are closed
over the complement operation.
5. Regular sets are closed over intersection
operation
Proof: let S1 and S2 be two regular sets.
Therefore, their complements

s1

s2

and

are also regular sets. Union of s 1 and s 2,

that is, ( s 1 s 2) is also a regular sets.
Complement of ( s 1 s 2), that is, ( s1
is also a regular set.

By De Morgans Law, S1 S2 = ( s1 s2 ).
Hence, (S1 S2) is also a regular set.
Therefore, regular sets are closed over the
intersection operation.
6. Regular sets are closed over the difference
operation.

Proof: let S1 and S2 be te two regular sets.

since S2 is a regular set, s 2 is also a regular
set, (S1 s 2) is also a regular set.
S1 s 2 = S1 S2 is also a regular set.
Therefore, regular sets are closed over the
intersection operation.
7. Regular sets are closed over the Kleenes
star.
proof: The closure over Kleenes star() is
also known as Kleenes closure. closure of a
regular set over Kleenes star means that if R
is a regular expression, then R* is also a
regular expression.
Let R be a regular expression and M be its
corresponding finite automaton, as shown in
figure,

C1 belongs to the language set L and those in the

class C2 do not belongs to L.
The language L can be implemented on the finite
state machine (FSM) such that each state in the
FSM corresponds to a particular class.
FA contains minimum two states.
1. where the strings belonging to the class
C1 reach the final state and
2. Other where the strings belonging to the
class C2 reach the non-final state. Thus,
the language L can be implemented using
a FA.
0
0
1
F

Since L1 is regular.
q0

qi

qk

qf

Now wrap around the finite automaton M and

superimpose the final state qf with the initial state
q0 to make the initial state as the final state and to
create a new finite automaton, say M as shown
in figure.

Similarly consider a language L2 over {0, 1} such

that all strings belonging to L2 wnd with 00.
all the string classified into 5-classes.
Class C1: string length less than 2 I.e. , 0, 1.
Class C2: those ending with 00.
Class C3: those ending with 01.
Class C4: those ending with 10.

q0

qi

qk

Now if a string is accepted by the finite

automaton M, then M accepts all the strings that
involve the repetition of . such as , , ,
and so on. Thus, M is a finite automaton
for R*. since there exists a finite automaton for
R*, it is a regular set corresponding to R*. Hence,
regular sets are closed over Kleenes closure.
Myhill-Nerode Theorem [ Equivalent classes
and Regular Languages]: Consider a language
L with = {0, 1} such that a string belong to L
if and only if it ends with 0. we can categorized,
all the strings into two categories ( classes), those
ending with 0(say class C1) and those ending
with 1(say class C2). All the strings in the class

Class C5: those ending with 11.

q0

q1

qf

since L2 is regular
If the number of equivalent classes over a
language L is finite then the language L is
regular. This statement is refered to as MyhillNerode theorem.
L3 = {0n1n|n>0} to recognize this machine should
be able to remember how many 0s it has seen
and if the no. of 1s is exactly the same as that of
number of 0s. However, the FSM is devoid of
any kind of memory the 0 count and match it

with the 1 count. the no. of equivalent classes

generated by the language L3 over {0,1}* is
infinite, with each class corresponding to number
of 0s on any string. Since the number equivalent
classes are not finite, according to Myhill-Nerode
theorem, the language L3 is not regular.
Consider a language L4 = {w|w is palindrome
over {a,b}}.
Now, the recursive definition of a palindrome
over {a, b} is as follows:
- is a palindrome

a is a palindrome
b is a palindrome
if a string x is a palindrome then axa, bxb are
palindromes.
To recognize L4, a machine should be able to
mark the middle of the string and match the
symbols on the both sides of the middle. FSM
has no memory, so counting is nt possible.
another possible mechanism is to create a class
corresponding to the string before the middle of
the input string and to match this class with the
class of the reverse string after the middle. if they
are same then the string is a palindrome.
Otherwise, it is not. However the number of
possible classes for the string before the middle is
infinite; hence the language L4 can not be
implemented on a finite automaton and hence, is
not regular.
L5 = {ww | w is a string over {0.1} is not regular}
because the language L5 belongs to the same
group as the language L4.
L6 over = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; a string w
over * belongs to L6 if the number formed by w
is divisible by 9.
For example: 9, 18, 27, . . . are belongs to L6 1,
2, 3, . . . rest does not belongs to L6.
Here string can be divided into 9 equivalent
classes, with each class corresponding to a
remainder 0 to 8. if remainder 0, then the string

belongs to L6, otherwise it does not since the

number of equivalent classes. for L6 is finite(9),
the language L6 can be implemented on the FSM
and therefore L6 is regular.
Current
state
q0
q1
q2
q3
q4
q5
q6
q7
q8

0
q0
q1
q2
q3
q4
q5
q6
q7
q8

1
q1
q2
q3
q4
q5
q6
q7
q8
q0

2
q2
q3
q4
q5
q6
q7
q8
q0
q1

3
q3
q4
q5
q6
q7
q8
q0
q1
q2

Input Symbol
4 5 6
q4 q5 q6
q5 q6 q7
q6 q7 q8
q7 q8 q0
q8 q0 q1
q0 q1 q2
q1 q2 q3
q2 q3 q4
q3 q4 q5

7
q7
q8
q0
q1
q2
q3
q4
q5
q6

8
q8
q0
q1
q2
q3
q4
q5
q6
q7

9
q0
q1
q2
q3
q4
q5
q6
q7
q8

Minimization of Finite Automata:

Definition: Two state q1 and q2 are equivalent (
denoted by q1q2). if both (q1, x) and (q2, x) are
final states or both of them are non final state for
all x*.
As it is difficult to construct (q1, x) and (q2, x)
for all x* because there are an infinite number
of strings in *.
Definition: Two states q1 and q2 are k-equivalent(
k 0 ) if both (q1, x) and (q2, x) are final states
or both non final states for all strings x of length
k or less.
Example:
Current State
q0
q1
q2
q3
q4
q5
q6
qf

a
q1(N)
q5(N)
qf(F)
q6(N)
qf(F)
q5(N)
q5(N)
q0(N)

Input State

b
q4(N)
qf(F)
q5(N)
q4(N)
q5(N)
q3(N)
qf(F)
qf(F)

a) 0-level equivalence: The only string with

length zero i.e. , if is applied on any state
qi remains on the same state qi.
if is applied in state qf we get final state.

if is applied in state any other state,

Current
we get non final state.
state
The state of state Q can be partitioned
q0
into two subsets: {qf} and {q0, q1, q2, q3,
q3
q4, q5, q6}
This partition is denoted by
q1
0 = { {q0, q1, q2, q3, q4, q5, q6}, {qf}}
q6
b) 1- Level equivalence: The strings with
length one are a and b, equivalence at
q2
level 1 can exists if and only if, there
q4
exists equivalence at level 0. Hence, qf
cannot be equivalent to any other state at
level 1.
1) The state q0, q3, & q5 have same
behavior. These state lead to a non-final
state for both the strings a and b.
2) The state q2 and q4 have the same
behavior a- F, b-NF.
Hence the set partition for 1-level
equivalence is as follows:
1 = { {q0, q3, q5}, {q1,q6}, {q2 q4}}, {qf}}

Input Symbol
aaa
aab
aba
abb
baa
bab
q5(N) q3(N) q0(N) qf(N) q0(N) qf(N)
q5(N) q3(N) q0(N) qf(N) q0(N) qf(N)

bba
bbb
q5(N) q3(N)
q5(N) q3(N)

q5(N) q3(N) q0(N) q4(N) q1(N) q4(N) q0(N) qf(N)

q5(N) q3(N) q3(N) q4(N) q1(N) q4(N) q0(N) qf(N)
q1(N) q4(N) q0(N) qf(N)
q1(N) q4(N) q0(N) qf(N)
Algorithm
Automaton):

(minimization

q5(N) q3(N) q6(N) q4(N)

q5(N) q3(N) q6(N) q4(N)
of

Finite

Step 1: (construction of 0): By definition of 0level equivalence, 0 = {Q10, Q20 } where Q10 is
the set of all final states and Q20 = Q Q10.
Step 2: (Construction of k+1 and k ): let Qik be
any subset in k. if q1 and q2 are in Qik, they are
(k+1)-equivalent provided (q1, a ) and (q2, a )
are in the same equivalent class in k for every
a.

Current
state
q0
q3
q5

aa
q5(N)
q5(N)
q5(N)

Input String
ab
ba
qf(F) qf(F)
qf(F) qf(F)
q3(N) q6(N)

bb
q5(N)
q5(N)
q4(N)

if so, q1 and q2 are (k+1)- equivalent. in this way,

Qik is further divided into (k+1)-equivalent
classes. repeat this for every Qik in k to get all
the elements of k+1.

q1
q6

q5(N)
q5(N)

q3(N)
q3(N)

q0(N)
q0(N)

qf(F)
qf(F)

Step 3: Construct n for n = 1, 2, until n =

n+1.

q2
q4

q0(N)
q0(N)

qf(F)
qf(F)

q5(N)
q5(N)

q3(N)
q3(N)

Example:

c) 2-Level equivalence: The string length two

is aa, ab, ba & bb. Equivalence at level 2 can
exist. If there is equivalence at level 1.
{q0, q3, q5}, {q1,q6}, {q2 q4}
2 = { {q0, q3},{q5}, {q1,q6}, {q2 q4}, {qf}}
d) 3-level equivalence: the strings with length
three are aaa, aab, aba, abb, baa, bab, bba,
and bbb.
3 = { {q0, q3},{q5}, {q1,q6}, {q2 q4}, {qf}}
3 is same as 2. Hence, no further division is
possible.

Current State
q0
q1
q2
q3
q4
q5
q6
q7

Input Symbol
a
b
q1(N)
q0(N)
q0(N)
q2(N)
q3(F)
q1(N)
q3(F)
q0(N)
q3(F)
q5(N)
q6(N)
q4(N)
q5(N)
q6(N)
q6(N)
q3(F)

By Step 1:
Q10 = {q3}, Q20 = Q Q10

0 = {{q3}, { q0, q1, q2, q4, q5, q6, q7 }}. As {q3 }

can not be partitioned further.

Q13 = {q2}, Q33 = {q1, q7 }, Q23 = {q6 }, Q43 = {q3,

q5}, Q53 = {q0, q4 }.

Q11 = {q3 }, Q21 = {q2, q4 }, Q31 = {q7 }, Q41 =

{q0, q1, q5, q6 }

3 ={{q2}, {q1, q7 }, {q6 }, {q3, q5}, {q0, q4 }}.

1 = {{q3 }, {q2, q4 }, {q7 }, {q0, q1, q5, q6 }}

Hence at higher level, we will get the same

equivalence.

Q12 = {q3}, Q32 = {q7 }, Q22 = {q0, q6 }, Q42 = {q1,

q5}, Q52 = {q2, q4 }.
Thus
2 = {{q3 }, {q0, q6}, {q7 }, {q1, q5}, {q2, q4 }}
Q13 = {q3}, Q33 = {q7 }, Q23 = {q0, q6 }, Q43 = {q1,
q5}, Q53 = {q2, q4 }.
3 = {{q3 }, {q0, q6}, {q7 }, {q1, q5}, {q2, q4 }}
3 = 2 (n+1 = n )
Hence at higher level, we will get the same
equivalence.
Q = {[q3 ], [q0, q6], [q7 ], [q1, q5], [q2, q4 ]}
q0 = [q0, q6] F = [q3].
Example 2:
Current State
q0
q1
q2
q3
q4
q5
q6
q7

0
q1(N)
q6(N)
q0(N)
q2(F)
q7(N)
q2(F)
q6(N)
q6(N)

Input Symbol
1
q5(N)
q2(F)
q2(F)
q6(N)
q5(N)
q6(N)
q4(N)
q2(F)

By Step 1:
Q10 = F = {q2}, Q20 = Q Q10 = { q0, q1, q3, q4, q5,
q6, q7 }
0 = {{q2}, { q0, q1, q3, q4, q5, q6, q7 }}. As {q2 }
can not be partitioned further.
Q11 = {q2 }, Q21 = {q3, q5 }, Q31 = {q1, q7 }, Q41 =
{q0, q4, q6 }
1 ={ {q2 }, {q3, q5 }, {q1, q7 }, {q0, q4, q6 }}
Q12 = {q2}, Q32 = {q1, q7 }, Q22 = {q6 }, Q42 = {q3,
q5}, Q52 = {q0, q4 }.
2 ={{q2}, {q1, q7 }, {q6 }, {q3, q5}, {q0, q4 }}.

3 = 2 (n+1 = n )

Q = {[ q2], [q1, q7 ], [q6 ], [q3, q5], [q0, q4] }

q0 = [q0, q4], F = [ q2].
Equivalence of Two Finite Automata: Two
finite automata over are equivalent if they
accept the same set of strings over . when two
finite automata are not equivalent; there is some
string over satisfying the following: One
automaton reaches a final state on application of
, whereas the other automaton reaches a nonfinal state.
Comparison Method: Let M and M be two
finite automata over . we construct a
comparison table consisting of n+1 columns,
where n is the number of input symbols. the first
column consists of pair of vertices of the form (q,
q) where qM and qM.
Case 1: If we reach a pair of (q, q) such that q is
final state of M and q is a non-final of M or
vice-versa, we terminate the construction and
conclude that M and M are not equivalent.
Case 2: Here the construction is terminated when
no new element appears in the second and
subsequent columns which are not in the first
column (i.e. when all the elements in the second
and subsequent column appear in the first
column). In this case we conclude that M and M
are equivalent.
Example:
Consider the following two DFAs M and M over
{0, 1} given in figure. determine M and M are
c
equivalent.
d
q1
d d
q2
gp

q3

Figure: Automaton M
c

q4
d

q5

from q2 and q5 respectively. As q1 is a final state

in M1 and q6 is a non-final state in M2, we see that
M1 and M2 are not equivalent: we can also not
that q1 id dd-reachable from q1 and hence dd is
accepted by M1. dd is not acceptable by M2 as
only q6 is dd-reachable from q4, but q6 is nonfinal.

q7
c

q6

Figure: Automaton M

Current state

Sol: The initial states in M and M are q1 and q4

respectively. Hence the first element of the first
column in the comparison table must be (q1,
q4). the first element in the second column in
(q1, q4) since both q1 and q4 are c-reachable
from the respective initial states.
Current State
(q, q)
(q1, q4)
(q2, q5)
(q3, q6)
(q2, q7)

Input Symbol
c (qc, qc)
(q1, q4)
(q3, q6)
(q2, q7)
(q3, q6)

d (qd, qd)
(q2, q5)
(q1, q4)
(q3, q6)
(q1, q4)

As we do not get a pair of (q, q), where q is a

final state and q is a non-final state( or viceversa) at every row, we proceed all the
elements. Therefore M and M are equivalent.
Example: show that the automat M1 and M2
defined by figure are not equivalent.
c
c
d

q1

d d
q2

q3

q4

q5

q7

c
d

q6

d
Sol: The initial states in M1 and M2 are q1 and q4
respectively. Hence the first column in
comparison table is (q1, q4). q2 and q5 are dreachable from q1 and q4. we see fro the
comparison table that q1 and q6 are d-reachable

(q,q)
(q1,q4)
(q2,q5)

Input Symbol
c
d
(qc,qc)
(qd,qd)
(q1,q4)
(q2,q5)
(q3,q7)
(q1,q6)

Grammar:
Before giving the definition of
grammar, we shall study, two types of sentences
in English, with a view to formalizing the
construction of theses sentences. The sentences
we consider are those with a noun and a verb, or
those with a noun-verb and adverb (such as Ram
ate quickly or Sham ran). the sentences Ram
are quickly has the words Ram, ate, quickly
written in that order. If we replace Ram by
sham, tom, etc. i.e. be any verb in the past
tense, and quickly by slowly i.e. by an adverb,
we get other grammatically correct sentences so
the structure of Ram ate quickly can be given as
<noun><verb><adverb>.
for <noun>, we can substitute Ram, Sham,
Tom etc.
for <verb>, we can substitute ate, ran,
walked etc.
for <adverb>, we can substitute quickly,
slowly etc.
we have to note that <noun> <verb> <adverb>
is not a sentence but only the description of a
particular type of sentence. if we replace
<noun> <verb> and <adverb> by suitable
words, we get actual grammatically correct
sentences.
Let S be a variable denoting a sentence. Now we
can form the following rules to generate two
types of sentences.

Productions:
S <noun><verb><adverb> | <noun><verb>
<noun> Ram|Sham|Tom|Geeta
<verb> ran|ate|walked

<adverb> slowly|quickly

let us denote the collection of rules given above

by P.
If our vocabulary is thus restricted to Ram,
Sham, Geeta, Tom, ran, ate, walked,
quickly and slowly, and our sentences are of
the
form
<noun><verb><adverb>
and
<noun><verb>, we can describe the grammar by
a 4-tuple.
(VN, T, P, S), where

1. Reverse Substitution is not permitted.

2. No inversion operation is permitted, for
example:, if S AB is production, it is not
necessary that AB S is a production.

Remarks: The derivation of a string is complete

when the working string can not be modified. If
the final string does not contain any variable, it is
a sentence in the language. if the final string
contains a variable, it is a sentential form and in
this case the production generator gets stuck.

Definition: The language generated by a

grammar G (denoted by L(G)) is defined as
* }. The elements of L(G) are called
{T*|S
G
sentences L(G) is the set of all terminal strings
derived from the start symbol S.

VN = {<noun>, <verb>, <adverb>}

Example:

T= {Ram, Sham, Tom, Geeta, ate, ran,

walked, quickly, slowly}

If G = ({S}, {0,1}, { S 0S1, S }, S ), find

L(G).

P is the collection of rules described above

(the rules are called productions).
S is the special symbol denoting a sequence.
The sentences are obtained by i) starting with
S ii) replacing words using the productions
and iii) terminating when a string of
terminals is obtained.
Definition: A phrase structure grammar (or
simply a grammar) is (VN, T, P, S), where
i)

VN is a finite non empty set whose

elements are called variables ( nonterminals).
ii) T is a finite non-empty set whose elements
are called terminals.
iii) VN T .
iv) S is a special variable (i.e. an element of
VN) called start symbol.
v) P is a finite set whose elements are ,
where and are strings on VN T. has at
least one symbol from VN. The elements of P
are called productions or productions rules.
Note:

Sol: As S is a production. S . So is in
G
L(G).
also, for all n 1.

S 0S1 02S12 . . . 0nS1n0n1n

G
G
G
G
G
therefore,
0n1n L(G) for n 1.
L(G) = {0n1n |n 1}

Context-Free Grammars: A context-free

grammar (CFG) is denoted by G = {V,T,P,S},
where V and T are finite sets of variables and
terminals respectively. we assume V and T are
disjoint. P is a finite set of productions, each
production is of the form A. where A is a
variable and is a string of symbols from (VT)*
finally S is a special variable called the start
symbol.
The right-hand side of a CFG is not restricted and it
may be null or a combination of variables and
terminals. The possible length of right-hand
sentential from ranges from 0 to i.e. 0 | | .

As we know that a CFG has no context neither

left nor right. this is why, it is known as contextfree. Many programming languages have
recursive structure that can be defined by CFGs.
Example: Consider a grammar G = (V, T, P, S)
having productions. S aSa | bSb | . check the
productions and find the languages generated.
Sol: let

P1: S aSa (RHS is terminal variable terminal)

P2: S bSb (RHS is terminal variable terminal)

P3: S (RHS is null string).

Since all productions are of the form A ,

where (V T)*. hence G is a CFG.
Language Generated:

bSb
bnSbn (using n step
derivation)
n m
m n
or
bnamSambn
S a b Sb a
(using m step
derivation)
or
bnamambn (using
S anbmbman
S
R
*
So L(G) = { : (a+b) }
S
S

aSa
anSan

or
or

Leftmost and Rightmost Derivation:

Leftmost derivation: if G = (V, T, P, S) is a

*
CFG and L(G) then a derivation S
is
L
called leftmost derivation iff all steps involved in
derivation have leftmost variable replacement
only.
Rightmost derivation: if G = (V, T, P, S) is a
*
CFG and L(G) then a derivation S
is
R
called rightmost derivation iff all steps involved
in derivation have rightmost variable replacement
only.
Example: Consider the grammar S S + S | S
S | a | b. find the leftmost and rightmost
derivations for string = a a + b.
Sol: let
P1: S S + S (RHS is variable terminal variable)
P2: S S S (RHS is variable terminal variable)

P3: S a (RHS is terminal )

P4: S b (RHS is terminal )

Hence the given grammar is CFG.

Leftmost derivation: for = a a + b

S S S ( using S S S)
L
a S ( using S a)
L
a S + S ( using S S + S )
L
a a + S ( using S a )
L
a a + b ( using S b )
L
The last symbol from the left is b, so using S b ).

(Note: Leftmost variable is highlighted in each step).

Rightmost Derivation:- for = a a + b.

S S S ( using S S S)
R
S S S + S ( using S S + S)
R
(since, in the above sentential form second
symbol from the right is so, we can not use S
a|b. therefore, we use S S + S ).

S S + b (using S b )
R
S a + b (using S a )
R
a a + b (using S a )
R
(Note: Rightmost variable is highlighted in each step).
Chomsky
classification
of
Grammars|
Languages (Chomsky Hierarchy): Noam
chomsky has classified all grammars in four
categories ( type 0 to type 3) based on the right
hand side forms of the productions.
Type 3: This is most restricted type. productions
of type A or A B|B. where A, B VN,
and T are known as type 3 or regular
grammar productions. in production of type 3. S
is also allowed, if is in generated
language.
for example: production S aS, S a are type
3 production.
Left-linear production: A Ba

Right-linear production: A aB

a left linear or right linear grammar is called

regular grammar. The language generated by a
regular grammar is known as regular language.

Type 2: Type 2 grammar is called context free

grammars. A production of the form , where
, (VN, T)* is known as type 2 production and
the language generated by the type of grammars
is called context-free language (CFL).
For example: S S + S, S S S, S id are
type 2 productions.

Type 1: Type 1 are context sensitive grammars

(CSGs). if all productions of a grammar are of
type 1 then grammar is known as type 1
grammar.

Derivation Trees: A natural way of exhibiting

the structure of a derivation is to draw a
derivation tree or parse tree. At the root of the
tree is the variable with which the derivation
begins. Interior (intermediated) nodes are
variables and leaf nodes are terminals.
For example: CFG S S + S | S S | a | b and
construct the derivation trees for all productions.
for the production
i)

In CSG, there is left context or right context or

both. For example, production A a. In
this is left context or is right context of A and
A is the variable which is replaced by a. the
production of S is allowed in type 1. If is
in L(G), but S should not appear on the right hand
side of any production. for example, productions
S AB, S , A c are type 1 productions,
but the production of type A Sc is not
allowed.

For example: productions of type AS aS, SB

Sb, S are type 0 productions.

ii)
iii)

S S+S

S a

S
a

iv)

S b

S
b

If L(G) then it is represented by a tree called

derivation tree or parse tree satisfying the
following

Classifying the Type of grammars:

1. Type 0 grammars include Type 1, Type 2,

Type 3 grammars.
2. Type 1 grammars include Type 2 and Type 3
grammars.
3. Type 2 grammar includes Type 3 grammars.
Type 0
Phrase structured Grammars
C.F.G.
Type 2
Regular grammers
Type 3
C.S.G.
Type
k: Aut1

(Note: we assume that is the context on left and

right).

Type 0: These types of grammar are also known

as phrase-structure grammars, and RHS of these
are free from any restriction. All grammars are
type 0 grammars.

SSS

Turing
Machine
Push down
Automata
Finite
Automata
Linear Bounded
Autmata

1. The root has label S ( the starting

symbol).
2. The all interior (internal) vertices (nodes)
are labeled with variables.
3. The leaves or terminal nodes are labeled
with or terminal symbols.
4. If A 1 2 3. . . n is a production in
G, then A becomes the parent of nodes
labeled 1, 2, 3,. . . ,n and
5. The collection of leaves from left to right
produces string .

Leftmost derivations tree of previous example.

S

A A1|A2|A3||An|1| 2| 3|| n

Where 1, 2, , n do not begin with A, then we

replace A-productions by

Elimination of Left Recursion: let the variable

A has left recursive productions as follows:

A 1 A| 2 A| 3 A|| n A

Where A 1A| 2A| 3A|| nA|.

a
b
Ambiguity: A grammar G is ambiguous if there
exists some string L(G) for which there are
two or more distinct derivation trees or there are
two of more distinct leftmost derivations.

Example: CFG E E + T | T

i.e.

terminal. Remove the left recursion (if any).

Ambiguity is a negative property of a grammar

and it is usually (but not always) possible to find
an equivalent unambiguous grammar. An
inherently ambiguous language is a language
for which no unambiguous grammar exists.
Example of Ambiguity:

Left-most derivation
a) S S + S a + S a + S + S a + a +
L
L
L
L
Sa+a+a S
L
+

b) S S + S S + S + S a + S + S a
L
L
L
L
+a+Sa+a+a
L
S
S

S
a

Where E is the starting symbol and id is the

Sol: Recursive production are
EE+T , TTF

Eliminating Left Recursion:

E E + T is replaced by E TE
T T F is replaced by T FT

=a+a+a

F id.

Where E +TE |

S S+S|a

TTF|F

S
a

Where T FT |
So, productions of G are:
E +TE

E +TE |
T FT

T FT |

F id.
Left Factoring: Two or more productions of a
variable A of the grammar G are said to have left
factoring if A productions are of the form
A 1| 2| 3|| n, where i (VN T)*
and does not start with . All these A-productions
have common left factor .
Elimination of Left Factoring: let the variable A
has (left factoring) productions as follows:
A 1| 2| 3|| n|1| 2| 3|| n, where
1, 2, 3, , n and 1, 2, 3, , n, do not
contain as a prefix, then we replace Aproduction by,

A A | 1| 2| 3|| n

Where A 1| 2| 3|| n

Example: Consider the grammar S aSa | aa

and remove the left factoring ( if any).
Sol: S aSa and S aa,

we have = a as a left factoring, we get the

productions:
S aS

S Sa | a

Removal of Ambiguity: for removing ambiguity

i)
ii)

Remove the Left Recursion.

Remove the Left Factoring.

(This is heuristic approach for removal of

ambiguity).
Example:
SS+S|SS|a|b

Sol: Step 1:

Find left recursive statement

SS+S
SSS
After removing left recursion
S aS | bS
S +SS | SS |
Now check for ambiguous string =
a a + a.
S aS
S a S S
S a a S S
S a a + a S S S
S a a + a S S
S a a + a S
Saa+aaa+a
So, we conclude that removal of left recursion (
and left factoring also) helps in removal on
ambiguity of the ambiguous grammar.
Simplification of CFG :
i)
Removal of Null productions:
Definition: A production A is called
a null production and variable B having
* is called null variable.
production B

Removing Null productions: Consider

the Null production X & for every
non-null production
Y X, where , (VN T )*.
a) Add enough productions of the form
Y such that .
b) Delete the production X .

Example: S aSa | bSb | .

Sol: S aSa | bSb | aa | bb

Example: S aS | aA | , A
Solution: S aS | aA | a | a
S aS | a

Example: S a | Xb | aYa,
XY|
Yb|X

Solution: S a | Xb | aYa | b | aa
XY

Yb|X

Removal of Unit Production: A production of

the type A B, where A, B are variables is
called unit production. These productions create
indirection and this result into requirement of
extra steps in deriving the terminal strings.
For example: Consider the grammar S aA | a

AB
BC
C aS
Solution: we find S aA bS aC aaS.
It means we are getting as after two intermediate
steps, A B C aS. So, we have the
production S aaS, instead of A B, B C,
C aS, which create indirection.
Steps for removing unit production.

Step 1: Collect all the unit productions

Step 2: if A A1 A2 . . . An ,
where is string of terminals, then replace the RHS
of A by and remove the productions
A1 A2 . . . An

Example: Consider the grammar S aS | bS | A

| B, A a, B b remove the unit productions
( if any).

Solution: we have two unit productions: S A

and S B and from variable A and B we get
terminals a and b respectively. So, replacing the
occurrences of A and B variables in S
productions, we get simplified productions:
S aS | bS | a | b.

Removal of useless Symbol: The symbols that

can be used in any production due to their
unavailability in the productions or inability in
deriving the terminal(s) are known as useless
symbols.
Example: Consider the grammar S aS | bS a |
b, A a, B b, in this symbols (variables)
A and B cannot be used because we can reach the
variables A and B from the starting symbol S. so
A and B are useless symbols and these are
removed from the grammar.
Now, the simplified grammar is
S aS | bS | a | b.

Application of Grammars:
1. Specifying syntax of programming
languages.
2. Representation symtactic structure in
natural languages,
3. Model of computation.

Order in which defects should be Removed:

1. Eliminate null productions
2. Eliminate Unit productions
3. Eliminate non-reachable Non-terminals
Reduced Form:
Example: Find the reduced grammar equivalent
to the grammar G whose productions are S AB
| CA, B BC | AB, A a, C aB|b.
Solution:

Step 1: W1 = { A, C } as A a and C b be
productions with a terminal string on RHS.

W2 = { A, C } { A1 | A1 with (
{ A, C } ) }
= { A, C } { S } as we have S CA.
W3 = { A, C, S } { A1 | A1 with (
{ A, C } ) }
= { A, C, S } = W2
VN = W2 = { S, A, C }
P = { A1 |A1, ( VN ) }
P = { S CA, A a, C b }
Thus,
G1 = ({S, A, C} , { a, b},
{ S CA, A a, C b }, S )
Step 2: W1 = { S }
W2 = { S } { A, C } [because S CA ]
= { S, A, C }

W3 = { S, A, C } { a, b} = { S, A, C, a, b}
[because A a, C b ]
As W3 = VN T, P = P

Therefore G = ({S, A, C} , { a, b}, { S CA, A

a, C b }, S ) is reduced grammar.
Example:
S aAa, A Sb | bCC | DaA, C abb | DD,
E aC, D aDa

Solution: Step 1: W1 = {c} as C abb be

production with terminals string on RHS.
W2 = {C} {E, A } as E aC and A bCC
= { C, E, A }
W3 = { C, E, A } { S } as S aAa
= { C, E, A, S}

W4 = { C, E, A, S} = W3 = W3
Hence
VN = W3 = {S, A, C, E}

P = {S aAa, A Sb | bCC, C abb, E

aC }
G1 = (VN, {a, b}, P, S)
Step 2: We start with W1 = { S }
As we have S aAa
W2 = {S} {A, a}
As A Sb | bCC

W3 = {S, A, a} { S, b, C } = {S, A, C, a, b}

There is no NULL production and Unit

As we have C abb

production.

P = { A | A1 W3 }

S ASA,

G = ({ S, A, C} , {a, b}, P, S) is reduced

grammar.

X1 SA ( In CNF)

W4 = W3 {a, b} = W3
Hence

Consider P1 : Replace the terminal a by a new

= { S aAa, A Sb | bCC, C abb}

Therefore

Now, replace SA by a new variable X1 and so,

Normal Forms: In Context free productions, we

have no restriction on RHS. If, we restrict the
RHS in different manner and this results into
different normal forms.
If G is a CFG and productions of G satisfy
certain restrictions, then G is said to in a normal
form.
Two popular and important normal forms are:
1. Chomsky Normal Form (CNF) and
2. Griebach Normal Form (GNF).
Chomsky Normal Form: A Context-free
grammar is in Chomsky Normal Form (CNF) if
every production is of one of the two types.
A BC (<variable> <Variable> < Variable> )
A a (< variable > <Terminal> )

Where A, B and C are variables and a is a

terminal symbol.
Methods for converting a CFG to CNF:
Step 1: Eliminate NULL productions
Step 2: Eliminate UNIT productions.
Step 3: Change the RHS to single terminal or
string of two variables.
Example:
S aSa | bSb | a | b, convert it into CNF.
Solution: Let P1 : S aSa (Not in CNF)

P2 : S bSb (Not in CNF)

P3 : S a ( In CNF)

P4 : S b ( In CNF)

variable A, we get

S AX1, where
A a (In CNF)

Consider P2: Replace the terminal b by a new

variable B, we get
S BSB, now, replace SB by a new variable Y2
and so, S BY2, where
Y2 SB (In CNF)
B b (In CNF)

Thus grammar G is in CNF has following

productions

S AX1 | BX2 | a | b
A a, B b

X1 SA, Y2 SB.
Example:

Let

be

the

grammar

with

productions

S AACD

A aAb |
C aC | a

D aDa | bDb | .

Solution: Step 1: Remove the Null-productions:

The nullable Variables are A and D.
S AACD | ACD | AAC | CD | AC | C
A aAb | ab
C aC | a

D aDa | bDb | aa | bb

Step 2: Remove Unit productions

S aC | a and delete S C

Step 3: S AACD | ACD | AAC | CD |AC | aC |

a A aAb | ab
C aC | a

D aDa | bDb | aa |bb

Replace the terminal b by a new variable Xb,

and the terminal a by Xa, we get
S AACD | ACD | AAC | CD |AC | XaC | Xa

A XaAXb | Xa Xb
C XaC | Xa

D XaDXa | XbDXb | XaXa | XbXb

Xa a, Xb b
Final Step:

S AT1 T1 AT2 T2 CD
S AT2

S AU1 U1 AC

A XaW1 W1 AXb

A XaXb

C XaC | a
D XaY1
D XbZ1

Y1 DXa

Z1 DXb

D XaXb | XaXb
Xa a

Xb b

Griebach Normal Form: Every Context-Free

Language L without can be generated by a

grammar for which every production is of the

form A a, where A is a variable, a is a

terminal and is a string of variable (possibly

empty or ( VN )).

A grammar in GNF is the natural generalization

of a regular grammar ( right linear).
Method for converting a CFG into GNF :
1. Eliminate the NULL productions
2. Change the intermediate terminal into
variables.
3. Remove all the variables of G as A1, A2, A3, .
. . , An.
4. Repeat Step 5 and Step 6 for I = 1, 2, . . . , n
5. If Ai a 1 2 n, where a T, and j is a
variable or a terminal symbol.
Repeat for j = 1, 2,. . . , m

If j is a terminal then replace it by a variable

An+j consider the next Ai- production and go
to step 5.
6. If Ai 1 2 n, where 1 is a variable,
then preform the following:
If 1 is same as Ai, then remove the leftrecursion and go to step 5.
Else replace 1 by all RHS of 1-productions
one by one. Consider the remaining Aiproductions, which are not in GNF and go to
step 5.
7. Exit.
Advantages of GNF:
1. Avoids Left Recursion
2. Always has terminal in leftmost position in
RHS of each production.
3. Helps select production correctly.
4. Guarantees derivation length no longer than
string length.
Example: G = ({A1, A2, A3}, {a, b}, P, A1},
where P consists of the following production
rules.
A1 A2A3

A2 A3A1 | b
A3 A1A2 | a

Convert it into GNF.

Solution: (Renaming is not required)
Consider the A1-production
A1 A2A3 (Not in GNF)

Replacing A2 by its RHS, we get

A1 bA3 (In GNF)

A1 A3A1A3 (Not in GNF)

Now, consider A1 A3A1A3 and replacing A3

by its RHS, we get
A1 aA1A3 (In GNF)

A1 A1A2A1A3 (Not in GNF)

So, A1-productions are A1 bA3 | aA1A3 |

A1A2A1A3.
Now, Consider A1 A1A2A1A3 and removing
left recursion, we get

A1 bA3A4 | bA3 (In GNF)

A4 aA1A3A2A1A1A3A4| aA1A3A2A1A1A3

(A4 is a new variable and it is a production that is

Example: E E + T | T,

A1 aA1A3A4| aA1A3 (In GNF) where

A4 A2A1A3A4| A2A1A3
not in GNF)

So, now all A1-productions are in GNF. Consider

A2-productions:
A2 A3A1 (Not in GNF)
A2 b (In GNF)

Now, consider A2 A3A1 and replacing A3 by

its RHS, we get
A2 aA1

(In GNF)

A2 A1A2A1 (Not in GNF)

Now, consider A2 A1A2A1 and replacing A1

by its RHS, we get

A2 bA3A4A2A1 (In GNF)

A2 bA3A2A1 (In GNF)

A2 aA1A3A4A2A1 (In GNF)

A2 aA1A3A2A1 (In GNF)

So, all A2-productions are in GNF.

Consider A3-productions:
A3 a (In GNF)

A3 A1A2 (Not in GNF)

Now, consider A3 A1A2 and replacing A1 by

its RHS, we get

A3 bA3A4A2 (In GNF)

A3 bA3A2 (In GNF)

A3 aA1A3A4A2 (In GNF)

A3 aA1A3A2 (In GNF)
Consider A4-productions:

A4 A2A1A3A4| A2A1A3 (Not in GNF)

Replacing A2 by its RHS, we get
A4 bA1A3A4| bA1A3
A4 aA1A3A4| aA1A3

A4 bA3A4A2A1A1A3A4| bA3A4A2A1A1A3

A4 bA3A2A1A1A3A4| bA3A2A1A1A3

A4 aA1A3A4A2A1A1A3A4| aA1A3A4A2A1A1A3

Now, all A4-productions are in GNF. All

productions are in GNF.
T T F | F,
F ( E ) | a,

Solution:

Eliminate the Unit Productions

T T F | ( E ) | a,

E E + T | T F |( E ) | a,

The equivalent grammars without

unit productions is, G1 = (V, T, P1, S ),
where P1 consists of
i)
ii)
iii)

E E + T | T F |( E ) | a,
T T F | ( E ) | a,
F ( E ) | a,

Step 2: Reduce the Terminals into Variables

We introduce new variables A, B, C
corresponding to +, , ) respectively. The
modified productions are
i)
ii)
iii)
iv)
v)
vi)

E EAT | TBF |( EC | a,
T TBF |( EC | a,
F ( E ) | a,
A +,
B ,
C)

Step 3: The variables A, B, C, F, T and E are

renamed as A1, A2, A3, A4, A5, A6 respectively.
The productions becomes
A1 +

(In GNF)

A2 (In GNF)
A3 )

(In GNF)

A4 ( A6A3 (In GNF)

A4 a (In GNF)

A5 A5A2A4 (Not in GNF)

A5 ( A6 A3
A5 a

(In GNF)

(In GNF)

A6 A6A1A5 (Not in GNF)

A6 A5A2A4

(Not in GNF)

A6 (A6A3 (In GNF)

A6 a

(In GNF)

Production A1, A2, A3 and A4 are in GNF.

Consider production A5-production
A5 A5A2A4 (Not in GNF)

and renaming left recursion, we get

A5 ( A6 A3 A7 | ( A6 A3 (In GNF)
A5 aA7 | a

A7 A2A4A7 | A2A4

(A7 is a new variable and it is production that

is Not in GNF).

So, now all A5- productions are in GNF.

Consider A6-productions
A6 A6A1A5 (Not in GNF)

A6 A5A2A4

(Not in GNF)

now, Consider A6 A5A2A4 and replacing A5

by its RHS, we get

A6 aA7A2A4 | aA2A4 (In GNF)

A6 (A6A3A7A2A4 |(A6A3A7A2A4 (In GNF)

Now, Consider A6 A6A1A5 and removing

left recursion, we get

A6 (A6A3A8 |(A6A3

A8 A1A5A8 | A1A5

and replacing A1 by its RHS, we get

A8 A5A8 | A5 (In GNF)

Now, all the productions are in GNF. Hence

grammar is in GNF.
Applications Of CFG:
1. Parser Design
2. Design of Natural Languages
Construction.
3. Design of Mark-up Languages.
Defects in CFG:
It may restrict the grammar from
generating the string (No generation of
terminal)
It may involve multiple Names and
definitions so confusion.
Illegal operation (null production misused).
Symbols not appearing any sentential form.
In CFG, not necessary to use all symbols.
Push-Down Automata
Push-Down Automata: A PDA is a tool to
implement context-free languages (CFLs). The
biggest drawback of finite automata is absence of
memory. there is no mechanism to remember the
count of Input symbol or to match.

A6 aA8 | a

let us consider L= {0n1n | n 1 } .This is a

context free language but not regular.

A6 (A6A3A2A4A8 |(A6A3A2A4

A Finite automata cannot accept L, i.e. strings of

the form 0n1n as it has to remember the number of
0s in a string and so it will require an infinite
number of states. this difficulty can be avoided by
adding an auxiliary memory in the form of stack.
To implement the language L on the PDA, the 0s
in the given string are added to stack. when a
symbol 1 is encountered in the Input string, 0 is
removed from the stack. thus the matching of
number of 0s and number of 1s is done. An
empty stack at the consumption of the string
indicates the acceptance of the string by the PDA.

A6 aA7A2A4A8 | aA7A2A4 | aA2A4A8 | aA2A4

A6 (A6A3A7A2A4A8 |(A6A3A7A2A4

All above A6 grammar are in GNF.

A8 A1A5A8 | A1A5 (Not in GNF)

(A8 is a new variable and it is production is not

in GNF).

So, now all A6-productions are in GNF.

Consider A7-production
A7 A2A4A7 | A2A4

and replacing A2 by its RHS, we get

A7 +A4 | +A4A7 (In GNF)
Consider A8-production

(S 0S1 | 01 } generates L.

Top of
Stack

Initial
Symbol

Z0

Stack

Removing Direction

Finite
State
Control

Storing Direction

Reading
Head

Definition (Mathematical Description of PDA) :

A PDA Consists of & tuple ( Q, , , , q0, Z0, F )
1. Q is a finite and non-empty set of states.
2. is a finite and non-empty set of input
alphabets.
3. is a set of symbols that can be pushed into
the stack.
4. is the transition function which maps from
Q ( { } ) to Q (finite subset).
5. q0 Q is the initial (starting ) state.
6. Z0 is the initial (starting) stack symbol.
7. F Q is the set of final states.

Moves of Push-down Automata: The move of

PD means that what are the options to proceed
further after reading inputs in some state and
writing some string on the stack. PDA is basically
non-deterministic device having some finite
number of choices of moves in each situation.
The move will be of two types:

DPDA

1. In first type, an Input symbol is read from

the tape, and depending upon the topmost
symbol on the stack and present state, PDA
has number of choices to proceed next.
Ex: ( q, a, Z ) {(q, ) }
q Q, .

2. In the second type of move, the input

symbol is not read from the tape and
topmost symbol of the stack is used. The
topmost of the stack is modified without
reading the input symbol. It is also known
as - move.

NDPDA

Model of Push-Down Automata: It consists of a

finite tape, a reading head, which reads from the
tape, a stack memory (Push-down store).

Non-deterministic PDA : NPDA has finite

number of choices for its inputs. A NPDA
accepts an Input if a sequence of choices lead to
some final state or cause PDA to empty its stack.
Deterministic PDA : pda is deterministic if:

1. for each q in Q and Z in , whenever (q,

, Z) is non empty, then (q, a, Z) is
empty for all a in .
2. For no q in Q, and Z in , and a in
{} does (q, a, Z) contains more than
one element.
Acceptance by PDA: A PDA has final state like
( q0, , Z0 ) (F, , ),
Design a PDA to accept strings with More as
than bs.
Solution:
( q0, a, Z0 )
( q0, b, Z0 )
( q1, a, a )
( q1, a, b )
( q1, b, a )
( q1, b, b )
( q1, , a )

(q1, aZ0 )
(q1, bZ0 )
(q1, aa )
(q1, )
(q1, )
(q1, bb )
(qf, a )

(q1, aZ0 )
(q1, aa )
(q2, a )
(q2, )
(qf, Z0 )

Design a PDA to accept the language {ancan | n

1}
Solution:
( q0, a, Z0 )
( q1, a, a )
( q1, c, a )
( q2, a, a )
( q2, , Z0 )

Design a PDA to accept language {anbn | n>0 }

Design a PDA for language {anbman | m, n 1 }.

Solution:

Solution

( q0, a, Z0 )
( q1, a, a )
( q1, b, a )
( q2, b, a )
( q2, , Z0 )

(q1, aZ0 )
(q1, aa )
(q2, )
(q2, )
(qf, Z0 )

Note: LL parsers (left to right scan using

Leftmost derivation) usually are top-down
parsers, and LR parser ( left to right scan;
Rightmost derivation in reverse order ) usually
are bottom up parsers.
Design a PDA to accept language {wcwR | w
(a+b)* }
Solution:

( q0, a, Z0 )
( q0, b, Z0 )
( q1, a, a )
( q1, b, a )
( q1, a, b )
( q1, b, b )
( q1, c, a )
( q1, c, b )
( q2, a, a )
( q2, b, b )
( q2, , Z0 )

(q1, aZ0 )
(q1, bZ0 )
(q1, aa )
(q1, ba )
(q1, ab )
(q1, bb )
(q2, a )
(q2, b )
(q2, )
(q2, )
(qf, Z0 )

( q0, a, Z0 )
( q1, a, a )
( q1, c, a )
( q2, b, a )
( q2, , Z0 )

(q1, aaZ0 )
(q1, aaa )
(q2, a )
(q2, )
(qf, Z0 )

( q0, a, Z0 )
( q1, a, a )
( q1, c, a )
( q2, b, a )
( q3, b, a )
( q2, , Z0 )

(q1, aZ0 )
(q1, aa )
(q2, a )
(q3, a )
(q2, )
(qf, Z0 )

Design a PDA for language L = {ancb2n | n 1 }

Solution:

Solution 2:

( q0, a, Z0 )
( q1, a, a )
( q1, b, a )
( q2, b, a )
( q2, a, a )
( q3, a, a )
( q3, , Z0 )

(q1, aZ0 )
(q1, aa )
(q2, a )
(q2, a )
(q3, )
(q3, )
(qf, Z0 )

(q1, aZ0 )
(q1, aa )
(q2, a )
(q3, a )
(q3, )
(qf, Z0 )

Design a PDA for language L = {anbn+2 | n 1 }

Solution:
( q0, a, Z0 )
( q1, a, a )
( q1, b, a )
( q2, b, a )
( q3, b, a )
( q3, , Z0 )

Parsing: The importance of a grammer is that it

provides the platform to describe ( generate or
produce ) a certain language.
1. Syntax: It means the grammatical
construct of a program.
2. Semantics: It means, the meaning of a
program. it is all about the operations that
are to be carried out by some means.
We define parsing, Parsing is a technique to
construct a parse (derivation) tree or to check
whether there is some leftmost derivation or not
for a given word (string) using a certain grammar.
if the syntax of a given string is correct then the
answer is YES otherwise the answer is NO.
In general parsing is categorized into two
categories.
1. Top-down parsing
2. Bottom-up parsing
Top-Down Parsing: We start with initial symbol
and replace the leftmost variable in each step and
finally get the string. This approach is known as
top-down parsing. In the parse tree, start symbol
is root, terminals are leaves (input symbols) and

other nodes are variables. we start from the root

and replacing the intermediate nodes one by one
from left to right reach the leaves. this is the
reason why this approach is known as top-down
approach. This approach is also known as
recursive descent parsing.
*
S
(From the starting symbol to generate sentence)

Note: If a leftmost derivation is constructed by

looking k symbols ahead in the given string, then
the grammar is known as LL(k) grammar. Due to
non-determinism problem in the grammar , we
have to use LL(k) approach in the parsing. we
can reduce the non-determinism to some extent
by converting a grammar in CNF and removing
the left recursion and left factoring.
A grammar G having the property to look k (k
1) symbols ahead in the given string to parse that
given string is known as LL(k) grammar.
Example: let grammar G=({S, A, B}, {a, b}, P,
S) where P1 : S aA
S bB
S .
A aS and
B bS
Design the parsing Table.
Variable
S
A
B

P3

Symbols
a
P1
P4

b
P2

P5

How to implement a Parser: A parser is a

program, which read input string, using certain
context-free grammar and finds a leftmost
derivation or construct a parse tree.
There are two forms of parsers:
1. Top-down parsers: Construct parse tree
from root toward leaves.
2. Bottom-up parsers: Construct parse tree
from leaves to root.
Note: Both top-down and bottom-up parsers scan
the input from left to right.

Bottom-up parsing: The basic idea of a bottomup parser is that we start with input string and
replace the terminal(s) by respective variable
such that these replacements lead to the starting
symbol of the grammar So, in each step, we
reduce the input string to reach the starting
symbol. This approach is reverse of the top-down
approach.
Bottom-up parser reads the input symbol from left
and uses rightmost derivation in reverse order like
predictive parsing, with most tables, have we use
stack to push symbols. If the first few symbol
(sentential form) at the top of the stack match the
RHS of some variable, then we pop out these
symbols from the stack and we push that variable
(left-hand-side of production on the stack). This is
called a reduction. another name for bottom-up
parsers is shift-reduce(SR) parsers.
Handles are the sequences (terminals and
variables or both) on the stack that match with
some RHS in the given grammar productions and
after replacement lead to the start symbol. there
are three actions in the bottom-up parsing.
1. Shift the current input(token) on the
stack and read the next token.
2. Reduce by some suitable LHS of
production rule.
3. Acceptance Final reduction, which
leads to starting symbol.
Context Free Grammar is G = {VN, T, P, S },
design the parsing table and parse the string
babbba and check L(G)?
P1: SbAB
Parsing Table
Variables
Symbols
P2: SaAB
b
P3: AaA
a
S

P2
P1
P4: BbB
A

P3
P5
P5: A b
B

P
P4
P6: B a
6
Suppose: = babbba L(G) ?

P1
P3
P5
P4
P4
S bAB
baAB
babB
babbB
P6babbba.
babbbB

Hence babbba L(G). YES

4.2 For every production X in P, make a

Context-Free grammar is G = {VN, T, P, S},

design the parsing table and parse the string = a
+ a a.

transition function.

(q, , X ) (q, )

productions are:

4.3 For every terminal a, make a transition

P1 : S F + S

function.

P2 : S F S

(q, a, a ) (q, )

P3: S F

4.4 To indicate the end of the string, we put a

P4 : F a

marker $ at the end of the string. this marker is

Parsing Table
a

P3

P4

used to remove the initial symbol Z0 from the

a+

+a

P1

P2

P4

P4

aa

++

push-down store to make the stack empty.

(q, $, Z0 ) (qf, $Z0 )

Design Parsing table and Top-Down parser for

given productions.
EE+T

ET

TTF

F
a

F
b

TF

F(E)
F x1
F x2

Solution:
Remove Left Recursion and Left Factoring.

P1
P4
P2
P
P3
S
F+S
a+S
a + F S 4 a + a S
P
a + a F 4 a + a a.

P1: E +TE

Rules to Construct Top-Down Parser:

P5: T FT

Hence the string a + a a L(G). YES

Step 1: Remove left recursion, if any, from the

production set P.
Step 2: Remove the left factoring, if any, from the
production set P.
Step 3: Since the PDA takes one symbol at a
time, reduce the given grammar into LL(1).
step 4: Now design the PDA as follow:
4.1 To put the starting symbol S in the pushdown
store. make a transition function (q0, , Z0 )
(q, SZ0 ) (q0 initial state)

P2: E TE
P3: E

P4: T FT
P6: T

P7: F ( E )
P8: F xN
P9: N 1

P10: N 2

we have LL(1) grammar.

T
F

Parsing Table:
V/T
E
E
T
T
F
N

P3

P6

x
P2

P5

P8

P9

P10

(
P2

P5

P7

P1

P4

Parser:
Rule
R0

Input
(q0, , Z0 )

R1
R2
R3
R4
R5
R6
R7
R8
R9
R10

(q, , E)
(q, , E)
(q, , E)
(q, , T)
(q, , T)
(q, , T)
(q, , F)
(q, , F)
(q, , N)
(q, , N)

R11
R12
R13
R14
R15
R16
R17

(q, 1, 1 )
(q, 2, 2 )
(q, (, ( )
(q, ), ) )
(q, x, x )
(q, +, + )
(q, , )

R18

(q, $, Z0)

output
(q, EZ0 )

Step
4.1

(q, TE )
(q, +TE )
(q, )
(q, FT )
(q, FT )
(q, )
(q, ( E ))
(q, xN)
(q, 1)
(q, 2)

4.2
4.2
4.2
4.2
4.2
4.2
4.2
4.2
4.2
4.2

(q, )
(q, )
(q, )
(q, )
(q, )
(q, )
(q, )

4.3
4.3
4.3
4.3
4.3
4.3
4.3

(qf, $Z0)

4.4

Consider = x1 + (x2). parse on above PDA.

State

Unread Input

q0
q
q
q
q
q
q
q
q
q

x1 + (x2) $
x1 + (x2) $
x1 + (x2) $
x1 + (x2) $
x1 + (x2) $
1 + (x2) $
1 + (x2) $
+ (x2) $
+ (x2) $
+ (x2) $

PushDown
store
Z0
EZ0
TEZ0
FTEZ0
xNTEZ0
NTEZ0
1TEZ0
TEZ0
EZ0
+TEZ0

Rule
used
R0
R1
R4
R8
R15
R9
R11
R6
R2

q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
qf

(x2) $
(x2) $
(x2) $
x2) $
x2) $
x2) $
x2) $
2) $
)$
)$
)$
)$
$
$
$

TEZ0
FTEZ0
(E)TEZ0
E)TEZ0
TE)TEZ0
FTE)TEZ0
xNTE)TEZ0
NTE)TEZ0
2TE)TEZ0
TE)TEZ0
E)TEZ0
)TEZ0
TEZ0
EZ0
Z0
$Z0

R16
R4
R7
R13
R1
R4
R8
R15
R10
R12
R6
R3
R14
R6
R3
R18

Rules to Construct bottom-up parser:

Rule 1: (q, a, Z0) (q, aZ0) a T
Rule 2: (q, a, ) (q, a) a T

Rule 3: (q, , aR) (q, A) a T, aR is reverse

of a. for each A
Rule 4: (q, , S) (qf, )

Design bottom-up parser for given productions

Productions:
EE+T
ET

TTF
TF

F(E)

F x1
F x2

Solution:

Here E is the starting symbol and +, , (, ), x1 &

x2 are terminals. a T.
Pro
duc
tio
ns
P1
P2

Input

(q, a, Z0)
(q, a, )

Output

R
ul
e

(q,aZ0)
(q, a)

1
2

P3
P4
P5
P6
P7
P8
P9
P10

(q, ,
T+E)
(q, , T)
(q, ,
FT)
(q, , F)
(q, ,)E()
(q, , 1x)
(q, , 2x)
(q, , E)

(q, E)

(q, E)
(q, T)

3
3

(q, T)
(q, F)
(q, F)
(q, F)
(qf, )

3
3
3
3
4

EE+T
ET
TTF
TF
F(E)
F x1
F x2

Consider = x1 +( x2) parse on PDA.

Sta
te
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
qf

Rest of
Input
x1 + ( x2)
1 + (x2)
+ (x2)
+( x2)
+ (x2)
+ (x2)
(x2)
x2)
2)
)
)
)
)

Stack
Z0
x Z0
1x Z0
F Z0
T Z0
E Z0
+E Z0
(+E Z0
x(+E Z0
2x(+E Z0
F(+E Z0
T(+E Z0
E(+E Z0
)E(+E Z0
F+E Z0
T+EZ0
EZ0
Z0

action
Shift
Shift
Reduce
Reduce
Reduce
Shift
Shift
Shift
Shift
Reduce
Reduce
Reduce
Shift
Reduce
Reduce
Reduce
Reduce

Produ
ction
P1
P2
P8
P6
P4
P2
P2
P2
P2
P9
P6
P4
P2
P7
P6
P3
P10

Design a CFG for the language L = {0n1n | n 0 }

Solution: At n = 0, becomes a valid string in
the language L. The corresponding production is
S .

To incorporate the equal numbers of 0s and 1s,

the production used is S 0S1. Every transitive
substitution of S inserts an equal number of 0s
and 1s.
Hence, the production set for the CFG G
corresponding to CFL L is
S | 0S1 | 01

Design a CFG for the language L = { 0n12n | n

0}
Solution: At n = 0, becomes a valid string in
the language L. The corresponding production is
S .

To incorporate the double numbers of 1s as 0s,

the production used in S 0S11. Every
transitive substitution of S inserts double the
number of 1s following 0s.
S | 0S11 | 011

Design a CFG for the language L over { 0, 1 } to

generate all possible strings of even length.
Solution: The number 0 is considered to be even.
The string of length 0 is and the corresponding
production is S . A String of length 2 over
{0, 1} consists of one of the strings 00, 01, 10, or
11. The corresponding productions are S 00 |
01 | 10 | 11.
An even length of string of length 2n ( n > 1 )
contains one or more repetitions of the strings 00,
01, 10, or 11. The corresponding productions are
S 00 | 01 | 10 | 11.
Hence, the productions set for the CFG G
corresponding to the CFL L is
S | 00 | 01 | 10 | 11 | 00S | 01S | 10S | 11S

Design a CFG for the language L over {0, 1} to

generate all the strings having alternate sequence
of 0 and 1.
Solution: The minimum string length in L is 2.
The corresponding strings are 01 or 10. If a string
in L begins with 01, then it should follow a
repetition of 01 and terminate with either 01 or 0,
and if it begins with 10, then it should follow a
repetition of 10 and terminate either with 10 or 1.
The corresponding productions in CFG are
S 01 | 10 | 01A | 10B
A 01A | 0 | 01
B 10B | 1 | 10

Design a CFG generating the set of odd-length

strings in {a, b }* with middle symbol a.
Solution: S aSa | aSb | bSa | bSb | a.
Design a CFG generating the set of even-length
strings in {a, b }* with the two middle symbols.
Solution: S aSa | aSb | bSa | bSb | aa | bb
Design a CFG generating the set of odd-length
strings in {a, b}* whose first, middle, and last
symbols are all the same.
Solution: S aTa | bUb
T aTa | aTb | bTa | bTb | a
U aUa | aUb | bUa | bUb | b.
Design the CFG equivalent to a Regular
Expression ( 011 + 1 )* (01)*.
Solution: S AC
A |BA
B 011 | 1
C | DC
D 01

Design the CFG equivalent to a Regular

Expression ( 100 + 1 ) ( 1 )* ( 011 + 1 )+ Solution:
S ABD
A 100 | 1
B |1B
C D | DC
D 011 | 1

Design the CFG equivalent to language L = {

0i1j0k | j = I + k }
Solution: L = 0i 1i+k 0k
0i 1i 1k 0k
S AB
A 0A1 |
B 1B0 |

Design the CFG equivalent to language L = {

0i1j0k | j > i + k }
Solution: j = i + j + k
0i 1i+j+k 0k
0i 1i 1m 1k 0k

S BCD
B 0B1 |
D 1D0 |
C 1 | 1C

Turing Machine

We need such machines that can perform

recognizing as well as computation. Without
computational capability a machine is not much
useful as desired. We have computer system,
which is capable of doing recognizing as well as
computational. so, we are interested in designing
of an automaton(machine) that can solve both
objectives.
1. Recognizing
2. Computation
A Turing machine is a generalization of a PDA,
which uses a -tape instead of a tape and stack.
the potential length of the tape is assumed to be
infinite and divided into cells. One cell can hold
one input symbol. The head of TM is capable to
read as well as write on the tape and move left or
right or remain stationary. Turing machines
accept the languages are known as type 0
languages or the recursively enumerable (RE)
languages.
Note: One thesis called Churchs thesis support
the fact that a Turing machine can simulate the
behavior of a general-purpose computer system.
The church-turing thesis states that any algorithm
procedure that can be carried out by human
begins/computer can be carried out by turing
machine. It has been universally accepted by
computer scientist that the turing machine
provides an ideal theoretical model of a
computer.
Model of a Turing Machine: The turing
machine can be thought of as finite control
connected to a R/W head. It has one tape which is
divided into a number of cells. The block diagram
of the basic model for Turing is

1 2

Read/ Write
Head

Finite state
Control

n
Infinite Tape

Each cell can store only one symbol. The input to

and output from the the finite state automaton are
effected by the R/W head which can examine one
cell at a time. In one move, the machine examines
the present symbol under the R/W head on the
tape and the present state of an automaton to
determine
i.

a new symbol to be written on the tape in

the cell under the R/W head.
ii. a motion of the R/W head along the tape:
either the head moves one cell left(L), or
one cell right(R).
iii. The next state of the automaton, and
iv. Whether to half or not.
Mathematical description of a Turing Machine:
A Turing Machine M is described by 7-tuple
namely (Q, , , , q0, , F), where
i. Q is a finite non empty set of states.
ii. is a non empty set of symbols,
iii. is a finite non-empty set of symbols
including . = ,
iv. is a transition function which maps
from Q to Q (L|R|S)
i.e. (q, x) (q, y, D ) D is direction of
movement of R/W head: D= L or R or S
according as the movement is to the left
or right or stationary.
Note: i. The acceptability of a string is
decided by the reachability from the initial
state to some final state.
ii. may not be defined for some elements
of Q .
v. q0 Q is the initial state.
vi. represent the blank on the tape,
vii. F is set of final states.

Depending upon the number of moves in

transition, a TM be deterministic or nondeterministic. If TM has almost one move in a
transition then it is called deterministic TM
(DTM), if one or more than one move is in a
transition table it is called non-deterministic TM
(NTM). A standard TM reads one cell of the tape
and changes its state (optional) and moves left or
right one cell.
The halt state(h) means the stopping point of
processing by a TM when TM processes some
input then TM may fall into one of these given
below:
a.
b.
c.
d.
e.

Halting State(h)
Non-Halting State( non-final)
Loop (finite or infinite)
Crash and
Hang State (Undefined Transition)

When TM reads inputs on the tape then it keeps

write on the tape and when it halts or stops the
processing then whatever written on the tape is
the output of the TM. So, we have no need to
have final states as such. When TM does not stop
its processing and it is on for infinite time this
situation is known as infinite loop and when head
damages the tape then it is known as crash. for
some input, if TM does not decide what to do,
then we will say that TM is in hang state. A TM
can stop its processing in halting state or in nonhalting states.
Halting Problem: A turing machine accepts a
language means that the TM will stop eventually
in a halting state for each word that is in the
language. Halting state does not mean the
accepting state but it is additional state similar to
accepting state. However, if the word is not in the
language then Turing machine may stop in
halting or non-halting state or loop forever or
crash. In this case, we can never be sure whether
the given word is accepted or rejected i.e. the
Turing machine does not decide the word
problem (known as halting problem of TM).

Note: All languages (Regular Language, CFL,

CSL, Type 0 (pharse structured) language) are
accepted by TM. A language that is accepted by a
TM is known as recursive enumerable(R.E.).
being enumerable means, a TM precisely lists all
the strings of the language. Some
type-0
languages are not decidable by TMs known as
recursive set (language). For a recursive language
a TM always halts for its member strings and
rejects other.
Computation with Turing Machine:
we
represent integer numbers on the tape in forms of
0. suppose i is a positive integer, the 0i represents
this integer numbers.
For example:
5

1. 5 is represented by 0 as shown in figure.

0 0 0 0 0
2.

integers 2 and 4 are represented by 02104 as

shown in figure.
0 0 1 0 0 0 0
Note: If f1 is defined for all the arguments a1,
a2, . . . ,an then f1 is known as total recursive
function. The total recursive function is
analogous to recursive langages. A function
f(a1, a2, . . . , an) computed by a TM is known as
partial recursive function analogous to the
recursive enumerable set (RE languages).
TM Computable Functions

Total Recursive Functions

Recursive Languages
Input

Process

TM Always Halts

Partial Recursive Functions

Recursive Enumerable Languages
Input

Process

TM may or may not Halt

UNIVERSAL TURING MACHINE (UTM):

A Universal Turing machine is a specific Turing
machine that can simulate the behavior of any

TM. Alan Turing describes such a machine. Its

existence means that there is a turing machine
known as UTM, which is capable of running any
algorithm. The key idea is to think of the
description of a Turing machine itself as data.
we think a UTM as a reprogrammable TM.
A universal Turing Machine takes as input the
description of a turing machine along with the
initial tape contents, and simulates the behavior
of any individual TM. Building such an UTM
appears to be a daunting task.
Problem: Design a TM for L = { w: w (a + b )*
} ending in substring abb.
Solution:
State
q0
q1
q2
q3
*qf

a
q1, a, R
q1, a, R
q1, a, R
q1, a, R
___

b
q0, b, R
q2, b, R
q3, b, R
q0, b, R
___

___
___
___
qf, , L
___

Transition Graph:
b, b, R
q0

a, a, R
a, a, R

q1

a, a, R

, , L
b, b, R
b, b, R
q2
q3
q4
a, a, R
b, b, R

TM for L = (a + b )*abb
Problem: Design a TM for finding n mod 2.
Solution:
State
q0
q1
q2
q3
*qf

0
q0, 0 , R
q2, , L
q1, , L
__
__

q1, , L
qf, , L
q3, , R
qf, 0, L
__

Transition Graph For n mod 2

0, 0, L

, , L

0, , L

0, , L

, , L

, , R

, 0, L

The Encoding of a simple TM (The Encoding

function e): First we associate to each tape
symbol (including ), to each state (including
accepting and rejecting ) and to each of the three
directions, a string of 0;s. let
S() =0
S ( ai) = 0i+1
Result of String
S(A) = 0 Acceptance
S(R) = 00 Rejection
States
S(qi) = 0i+2 State on the TM
Direction
S(S) = 0 Stationary Direction on TM
S(L) = 00 Left Direction on TM
S(R) = 000 Right Direction on TM
Problem: Design a TM over = {1}
the language L = { 1m | m is odd }.
Solution:
State
1
q1, 1, R
q0
*q1
q0, 1, R

to accept

__
__

The asterisk (*) before q1 indicates that q1 is

a final state.
let consider the string 1111
q01111 1q1111 11q011
111q11 1111q0
Since the TM halts on q0, the string 1111 is
not accepted.
Transition Graph:
1, 1, R
q0

1, 1, R

*q1

Problem: Design TM over = {0, 1} to accept

the language L = {0m 1m | m > 0 }.
Solution: The example strings in the language L
are 01, 0011, 000111, 00001111, . . .
let the string be 000111
The string recognition process of the TM is:
1. Read the first symbol 0 of the string and
convert this 0 to blank().

2. The R/W head keeps moving towards the

right till the input string is crossed and the
first blank symbol after the string is
reached.
3. From this blank, turn one cell left and reach
the last symbol of the input string. If it is 1,
convert it into a blank.
4. Now, after converting the last 1 symbol to ,
the R/W head keeps moving towards the left
till a blank symbol is reached.
5. As the first blank is found move the head
toward right and repeat step 1 to step 4 till all
0s are cancelled by the corresponding 1s.
6. If the cancellation process is completed
successfully, then the string is accepted,
otherwise there are residual un-cancelled 0s
and 1s, then the string is not accepted.
Current
State
q0
q1
q2
q3
q4
*qf

0
(q1, , R )
(q1, 0, R )
__
(q3, 0, L )
(q1, , R )
__

Input Symbol
1

__
__
(q1, 1, R ) (q2, , L )
(q3, , L )
(q3, 1, L ) (q4, , R )
__
(qf, , R )
__
__

Design a Turing Machine over = { 0 } to accept

the language L = {0m | m is even}.

Solution: The problem is similar to the previous

one. The only change is that now q0 is a final
state and q1 is non-final state. The transition table
shown in table provides the complete set of
transition function.
Current
state
q0
q1

Input Symbol
0

(q1, 0 , R)
__
(q0, 0 , R)
__

Design a Turing machine over = {0} to accept

the language L = { 0m | m is multiple of 3}.

Solution: The example strings in the language L

are , 000, 000000, 000000000, Normally, the
R/W head points to the first 0 of the input string
in the state q0. If the length of the string ,
|| = 0, then it is a null string and the R/W

points to an arbitrary blank on the Turing tape

in the state q0. In this case, the Turing machine
halts. Since zero is a multiple of 3, the Turing
machine has to halt in the final state.
Therefore, q0 is declared as a final state.
Current
state
q0
q1
q2

Input Symbol
0
(q1, 0 , R)
(q2, 0 , R)
(q0, 0 , R)

__
__
__

Design a Turing machine over = { 0, 1} to

accept the language L = { 0m12m | m > 0}.
Solution: The example strings in the language L
are 011, 001111, 000111111, The r/w head
points to the first symbol of the input string in the
string in the state q0.
The recognition process of the string on the
Turing machine is as follows:

Current
State
q0
q1
q2
q3
q4
q5
q6
*qf

0
(q1, , R)
(q1, 0, R)
__
__
__
(q5, 0, L)
__
__

Input Symbol
1
__
(q1, 1, R)
(q3, , L)
(q4, , L)
(q5, 1, L)
(q5, 1, L)
__
__

__
(q2, , L)
__
__
(q6, , R)
(q0, , R)
(qf, , R)
__

Design a Turing machine to compute m n

where m and n are positive integers and m > n.
Current
State
q0
q1
q2
q3
q4
q5
q6
*qf

0
(q1, , R)
(q1, 0, R)
(q2, 0, R)
(q4, , L)
(q4, 0, L)
(q5, 0, L)
(q1, , R)
__

Input Symbol
1

__
__
(q1, 1, R)
__
__
(q3, , L)
__
(qf, 0, L)
(q5, 1, L)
__
__
(q6, , R)
__
__
__
__

1. The r/w head reads the first symbol 0 of the

input string and converts this 0 into a blank ().
2. The r/w head keeps moving towards the
Design a Turing machine to compute m n
right till the input string is crossed and the
where m and n are positive integers.
first blank after the string is reached.
3. From this blank, the r/w head turns one cell Curren
Input State
to the left and reaches the last symbol of the State
0
1
x
y

(q
,x,
R)
(q
,1,L
)
__
__
__
input string. If the last two symbols in the q0
1
9
q1
(q1,0,R) (q2,1,R)
__
__
__
string are 11, then the match occurs.
q
(q
,y,R)
(q
,1,L)
__
__
__
2
3
7
a. If the match occurs, then the r/w
q3
(q3,0,R) (q4,1,R)
__
__
__
head converts both 1 symbols to
q4
(q4,0,R)
__
__
__
(q5,0,L)
blanks one by one. The r/w head
traverses back to the beginning of the
q5
(q5,0,L) (q6,1,L)
__
__
__
remaining string and perform the
q
(q
,0,L)
__
__
(q
,y,R)
__
6
6
2
matching and cancellation of one 0 by
q7
__
(q8,1,L)
__
(q7,0,L)
__
11. This process is repeated till all 0s
q8
(q8,0,L)
__
(q0,x,R)
__
__
are matched by the corresponding 11
q9
__
__
(q9,0,L)
__
(qf. , R)
pair. If this occurs, then it indicates
the acceptance of the string.
b. If the match does not occur at any
*qf
__
__
__
__
__
stage, the process stops in a non-final
state and indicates the rejection of the
string.
The transition table is:

Design a TM over = {a, b} to accept the

language L = {wwR | w (a, b)* }
Solution:
Current
State
q0
q1
q2
q3
q4
q5
*qf

a
(q1, , R )
(q1, a, R )
(q3, , L )
(q3, a, L )
(q4, a, R )
__
__

Input Symbol
b

(q4, , R ) (qf, , R )
(q1, b, R ) (q2, , L )
(q3, b, L )
(q4, b, R )
(q3, , L )
__

(q0, , R )
(q5, , R )
__
__

Design a TM to compute m+n where m and n are

positive integers.
Sol: Initially two integers m and n are separated
by 1 symbol on the Turing tape.
0 0 0 1 0 0 0 0 0
The numbers to be added 3 and 5.
After the addition operation, the Turing tape
contains the result of addition.
0 0
Current
State
q0
q1
q2
*qf

0 0

0
(q0, 0, R )
(q1, 0, R )
(qf, , L )
__

0 0

0 0

Input Symbol
1

(q1, 0, R )
__
__
(q2, , R )
__
__
__
__

Post Correspondence Problem (PCP): Posts

correspondence problem is a combinatorial
problem formulated by Emil Post in 1946. This
problem has many applications in the field theory
of formal languages.
Definition: A correspondence system P is a finite
set of ordered pairs of no empty strings over
some alphabet.
Let be an alphabet, then P is finite subset of +
*. A match or solution P is any string w
such that pairs (u1, v1), (u2, v2), . . . , (un, vn)P

and w = u1 u2 u3. . . un = v1 v2 v3 . . . vn for some n

> 0. The selected pairs (u1, v1), (u2, v2), . . . , (un,
vn) are not necessary distinct.
Let string u1 u2 u3. . . un are in U and string v1 v2
v3 . . . vn are in V, then
U = { u1 u2 u3. . . um } and V = { v1 v2 v3 . . . vm}
for some m>0.
PCP is to determine whether there is any match
or not for a given correspondence system.
The PCP is to determine whether or not there
exist I, where 1 i m such that
ui1. . . uin = vi1. . . vin
Example: Does the PCP with two lists u = (b,
bab3, ba ) and v = (b3, ba, a ) have a solution.
bab3
u2

b
u1

b
u1

ba
u3

b3
v1

ba
v2

b3
v1

Example: Does the PCP given below have a

solution?
ui
vi

1
10
101

2
01
100

3
0
10

4
100
0

5
1
010

Solution:
10
101
1

1
010
5

01
100
2

0
10
3

100
0
4

100
0
4

0
10
3

100
0
4

Note: If the first substring used in PCP is always

xi and yi, then PCP is known as the modified Post
Correspondence Problem.
Unrestricted Grammars: An Unrestricted or
phrase-structure grammar is a 4-tuple G= (VN, T,
P, S) where VN and T are disjoint sets of variables
and terminals respectively, S is an element of V
called the start symbol; and P is a set of
productions of the form

where , (VN T )* and contains at least

one variable.

a
v3

Context-Sensitive Grammar and Languages:

). Also, when G1 has S , S does not

appear on the right-hand side of any production.
So G1 is context sensitive. this proves lcfl lcsl.

A Context-Sensitive grammar (CSG) is an

unrestricted grammar in which every production
has the from

Property 3: lrl lcfl lcsl l0. this follows from

properties 1 and properties 2.

A context-Sensitive language (CSL) is a language

that can generated by such a grammar.

Computability (Basic Concept):

with || | |

A slightly different characterization of these

language makes it easier to understand the phrase
context sensitive. A language is context-sensitive
if and only if it can be generated by a grammar in
which every production has the form
A X

Where , , and X are the strings of variables

and/or terminals, with X not null, and A is a
variable such a production may allow A to be
replaced by X. depending on the context.
The production of type S is allowed in type
1 if is in L(G), but S should not appear on right
hand side of any production.

For example, Productions S AB, S , A

c are type 1 productions, but the production of
type A Sc is not allowed. Atmost every
language can be thought as CSL.

Note: If left or right context is missing then we

assume that is the context.

Relation between Languages of Classes (

Languages And Their Relation): let l0, lcsl, lcfl, lrl
denote the family of type 0 languages, context
sensitive languages, context free languages and
regular languages respectively.
Property 1: From the definition, it follows that lrl
l0, lcfl l0.

Property 2: lcfl lcsl. The inclusion relation is not

immediate as we allow A in context free
grammar even when A S, but not in contextsensitive grammars ( we allow only S in
context sensitive grammars). a context free
grammar G with productions of the A is
equivalent to a context-free grammar G1 which
has no productions of the form A (except S

Property 4: lrl lclf lcsl l0.

we start with the definition of partial and total

functions.
A partial function f from X to Y is a rule
which assigns to every element of X atmost one
element of Y.
A total function from X to Y is a rule which
assigns to every element of X a unique element
of Y. for example:, If R denotes the set of all real
numbers, the rule f from R to itself given by f(r)
= +r is a partial function since f(r) is not defined
as a real number when r is negative. But g(r) = 2r
is a total function from R to itself.
Remarks: A partial or total function from Xk to
X is also called a function of k variables and
denoted by f(x1, x2, . . . , xn). for example, f(x1,
x2) = 2x1 + x2 is a function of two variables.
f(1,2) = 4, 1 and 2 are called arguments and 4 is
called a value. g(w1 , w2) = w1w2 is a function of
two variables ( w1, w2 * ); g(ab,aa) = abaa, ab
and aa are called arguments and abaa is a value.
Primitive Recursive Functions:
A function is primitive recursive if
1. It is an initial function
2. It is obtained from recursion
composition of initial functions.

or

Most Popular total functions are primitive

recursive functions; however some total
functions are not. for example, the ackerman
function is total but not primitive recursive.
Initial functions: the initial funvctions over N
are given below:
S(4) = 5, Z(7) = 0

U32 {2, 4, 7} = 4, U31 {2, 4, 7} = 2, U33 {2, 4,

7} = 7
Zero function Z defined by Z(x) = 0.
Successor function S defined by S(x) = x+1.
Projection function UNi{x1, x2, . . . ,xN) = xi
The initial functions over are given below.
nil(abab) =

cons a(abab) = aabab

cons b(abab) = babab
nil(x) =

cons a(x) = ax
cons b(x) = bx
Note: we note that cons a(x) and cons b(x)
simply denote the concatenation of the
constant string a and x, and concatenation of
the constat string b and x.
definition: If f1, f2, . . . , fn are partial
functions of n variables and g is a partial
function of k variables then the composition
of g with f1, f2, . . . , fk is a partial function of n
variables defined by g(f1(x1, x2, . . . ,xn),f2(x1,
x2, . . . ,xn), . . . , fk(x1, x2, . . . , xn)).
Example: let f1(x, y ) = x + y,
f2( x, y ) = 2x,
f3 ( x, y ) = xy and
g(x, y, z) = x + y + z be a function over N.
then g(f1(x, y ), f2(x, y ), f3(x, y) ) = g(x + y,
2x, xy ) = x + y + 2x + xy.
Example:
let f1 (x1, x2) = x1x2,
f2(x1, x2 ) =

f3 (x1, x2 ) = x1 and
g(x1, x2, x3 ) = x2x3 be the function over .

Then g(f1(x1, x2 ), f2(x1, x2 ), f3(x1, x2) )

= g(x1x2, , x1 ) = x1 = x1

Example:

Define n! by recursion

Solution:
f(0) = 1 and f(n+1) = h(n, f(n))
where h(x,y) = S(x) y.

Definition: A total function over N is called

primitive recursive.
1. If it is any one of the three initial functions,
or
2. If it can be obtained by applying composition
and recursion a finite number of times to the
set of initial functions.
Example: Show that the function f1(x, y) = x
+ y is primitive recursive OR
addition function of two integers are
primitive recursive.
Solution: f1 is a function of two variables.
If we want f1 to be defined by recursion, f1
for x and y (in equation).
f1(m, 0 ) = m
f1( m , n+1) = f(m, n ) + 1 = S(f1(m, n))
for example. consider f1(5, 2)
f1(5, 2) = S(f1(5, 1))
= f1(5, 1,) + 1
= S(f1(5, 0 )) + 1
= f1(5, 0 ) + 1 + 1
=5+1+1
= 7.
Hence f1 is a primitive recursive function.
Example: The function f2(x, y) x y is primitive
recursive.

Solution: As multiplication of Two natural

number is simply repeated addition, f2 has to be
primitive recursive. we prove this as follow
f2(x, 0 ) = 0
f2(x, y+1) = x (y + 1)
= f2(x, y ) + x

= f1( f2 ( x, y ), x)

Example: Show that the concatenation of two

string over {a, b} is primitive recursive.

solution:
we have defined concatenation as
f(, w2 ) = w2
f( a1, a2, . . . ,an, w2 ) = a1f1(a2, . . . ,an, w2 ) where
w1, w2 *.
we defined f using initial functions a follows:
f(, w1 ) = cons (w1) = w1 and

f( a1, a2, . . . ,an, w2 ) = cons a1 (f(a2, . . . ,an, w2 ))

for example, consider f(ab, cd),
f(ab, cd) = cons a f(b, cd)
= af(b, cd)
= acons bf(, cd)
= ab f(, cd)

= abcd (since f(a,w1) = w1 )

Hence concatenation is primitive recursive
function.
Application of FA:
1. NFA and DFA are used in passes parser
construction of Compliers.
2. Pattern Recognition
3. Programming language processing -in
scanning phase of compilation for
recognizing tokens.
4. Text pattern matching
5. Signal processing
6. Design Controllers for systems (Washing
Machines, Industrial processes).
Detail (Halting Problem): The halting problem
is a decision problem which is informally stated
as follows:
Given a description of an algorithm and a
description of its initial arguments, determine
whether the algorithm, when executed with these
arguments, ever halts. The alternative is that a
given algorithm runs forever without halting.
Alan Turing proved in 1936 that there is no
general method or algorithm which can solve the
halting problem for all possible inputs. An
infinite or finite in length depending on the input

and behavior of the algorithm usually depends on

the input size. Algorithm may consist of various
number of loops, nested or in sequence. The HP
asks the question:
Given a program and an input to the program,
determine if the program will eventually stop
when it is given that input?
One thing we can do here to find the solution of
HP. let the program run with the given input and
if the program stops and we conclude that
problem is solved. But, if the program does not
stop on a reasonable amount of time, we can not
conclude that it would not stop. The question is:
How long we can wait ?. The waiting time
may be long enough to exhaust whole life. So, we
can not take it as easier as it seems to be we want
specific answer either YES or NO, and hence
some algorithm to decide answer.
The importance of the halting problem lies in the
fact that it is the first problem which was proved
undecidable.
CHURCHS Thesis: A FA is a device having
finite states and operates on a string of symbols
with the fixed and finite set of rules. A PDA and
TM are more powerful machines than FA. A TM
captures behaviors of FA and PDA as well as
general-purpose computer system. We take TM
to be equivalent to an algorithm. Nothing will be
considered as algorithm if it can not be
implemented as a TM.
The principle that TMs are formal versions of
algorithms and no computational procedure will
be considered as an algorithm unless it can be
implemented as a TM is known as churchs
thesis.
According to the churchs thesis, behavior of a
general purpose computer can be simulated by
some TM. It is a thesis, not a theorem because it
is not a mathematical result. As we have
discussed that a TM can perform all the

computations (recognization and computation)

which are carried out by a general-purpose digital
computer.
Allan Turing also suggested in his Turings thesis
Any computation that can be performed by
mechanical means can also be performed by
some TM. Again, we have to define terms
mechanical means. If we consider this, then the
model of TM comes true.
Some arguments for accepting the churchs thesis
are as follows:
1. No one has been able to suggest a counter
example to disprove it till now.
2. Some TMs can also perform anything
that can be performed by digital
computer.
There are several alternate models of computation
like random access machine (RAM), Post
machine(PM) etc., but none is more powerful than
TM.

For more Notes Follow http://www.edutechlearners.com