Automata Doc

Unit – I
Introduction
 Definition of TOC
TOC describes the basic ideas and models underlying computing. TOC
suggests various abstract models of computation, represented mathematically.
 History of Theory of Computation

 1936 Alan Turing invented the Turing machine, and proved that there exists
an unsolvable problem.
 1940’s Stored-program computers were built.
 1943 McCulloch and Pitts invented finite automata.
 1956 Kleene invented regular expressions and proved the equivalence of
regular expression and finite automata
 1956 Chomsky defined Chomsky hierarchy, which organized languages
recognized by different automata into hierarchical classes.
 1959 Rabin and Scott introduced nondeterministic finite automata and proved
its equivalence to (deterministic) finite automata.
 1950’s-1960’s More works on languages, grammars, and compilers
 1965 Hartmantis and Stearns defined time complexity, and Lewis, Hartmantis
and Stearns defined space complexity.
 1971 Cook showed the first NP-complete problem, the satisfiability problem.
 1972 Karp Showed many other NP-complete problems.
 1976 Diffie and Helllman defined Modern Cryptography based on NP-
complete problems.
 1978 Rivest, Shamir and Adelman proposed a public-key encryption scheme,
RSA.
Finite State systems
A finite automaton can also be thought of as the device shown below consisting of a tape
and a control circuit which satisfy the following conditions:
 The tape has the left end and extends to the right without an end.
 The tape is dividing into squares in each of which a symbol can be written prior to the
start of the operation of the automaton.
 The tape has a read only head.
 The head is always at the leftmost square at the beginning of the operation.
 The head moves to the right one square every time it reads a symbol.
It never moves to the left. When it sees no symbol, it stops and the automaton
terminates its operation.
 There is a finite control which determines the state of the automaton and also controls
the movement of the head.
1 / 28
Unit – I
Basic Definitions
 Symbol :
Symbol is a character.
Example : a,b,c,… , 0,1,2,3,….9 and special characters.
 Alphabet :
An alphabet is a finite, nonempty set of symbol. It is denoted by ∑.
Example :
a) ∑ = {0,1}, the set of binary alphabet.
b) ∑ = {a,b… ..... z}, the set of all lowercase letters.
c) ∑ = {+, &,… .}, the set of all special characters.
 String or Word :
A string is a finite set sequence of symbols chosen from some alphabets.
Example :
a) 0111010 is a string from the binary alphabet ∑ = {0,1}
b) aabbaacab is a string from the alphabet ∑ = {a,b,c}
 Empty String :
The empty string is the string with zero occurrences of symbols (no symbols).
It is denoted by є.
 Length of String :
The length of a string is number of symbols in the string. It denoted by |w|.
Example :
w = 010110101 from binary alphabet ∑ = {0,1}
Length of a string |w| = 9
2 / 28
Unit – I
 Power of an Alphabet:
 If ∑ is an alphabet, we can express the set of all strings of certain length
from that alphabet by using an exponential notation. It is denoted by ∑ k is
the set of strings of length k, each of whose symbols is in ∑.
Example :
∑ = {0,1} has 2 symbols
i) ∑1 = {0,1} ( 21 = 2)
ii) ∑ = {00, 01, 10, 11} ( 22 = 4)
2
iii) ∑3 = {000,001,010,011,100,101,110,111} ( 23 = 8)
 The set of strings over an alphabet ∑ is usually denoted by ∑ *.

For instance, ∑* = {0,1}* = {є,0,1,00,01,10,11}
(∑*=∑0∑1∑2……) - with є symbol.
 The set of strings over an alphabet ∑ excluding є is usually denoted by ∑ +.

For instance, ∑+ = {0,1}+ = {0,1,00,01,10,11}
(∑+=∑*- {є} or ∑1∑2∑3 ......... )
- without є symbol.
 Concatenation of String
Join the two or more strings. Let x and y be two strings. Concatenation of
strings x and y is appending symbols of y to right end of x.
x = a1a2a3……………an and y = b1 b2b3 ................... bn
Concatenation of String xy = a1a2a3……an b1b2 b3 ........ bn
Example :
s = ababa and t = cdcddc
Concatenation st = ababacdcddc
 Languages:
If Σ is an alphabet, and L  Σ* then L is a language.
Examples:
o The set of legal English words
o The set of legal C programs
o The set of strings consisting of n 0's followed by n 1's
{ ϵ, 01,0011,000111, …}
 Operations on Languages
 Complementation
Let L be a language over an alphabet Σ. The complementation of L, denoted
byL, is Σ*–L.
 Union
Let L1 and L2 be languages over an alphabet Σ. The union of L1 and L2,
denoted by L1L2, is {x | x is in L1 or L2}.
 Intersection
Let L1 and L2 be languages over an alphabet Σ. The intersection of L1 and L2,
denoted by L1L2, is { x | x is in L1 and L2}.
3 / 28
Unit – I
 Concatenation
Let L1 and L2 be languages over an alphabet Σ. The concatenation of L1 and
L2, denoted by L1L2, is {w1 w2| w1 is in L1 and w2 is in L2}.
 Reversal
Let L be a language over an alphabet Σ. The reversal of L, denoted by Lr, is
{wr| w is in L}.
 Kleene’s closure
Let L be a language over an alphabet Σ. The Kleene’s closure of L, denoted by
L*, is {x | for an integer n  0 x = x1 x2 … xn and x1, x2 , …, xn are in L}.
∞
L = U Li
*
(e.g. a* ={,a,aa,aaa,……})
i=0
 Positive Closure
Let L be a language over an alphabet Σ. The closure of L, denoted by L+, is {
x |for an integer n  1, x = x1x2…xn and x1, x2 , …, xn are in L}
∞
L = U Li
+
(e.g. a* ={a,aa,aaa,……})
i=1
Finite Automata
Automaton is an abstract computing device. It is a mathematical model of a system,
with discrete inputs, outputs, states and set of transitions from state to state that occurs on
input symbols from alphabet Σ.
 It representations:
o Graphical (Transition Diagram or Transition Table)
o Tabular (Transition Table)
o Mathematical (Transition Function or Mapping Function)
 Formal Definition of Finite Automata
A finite automaton is a 5-tuples; they are M=(Q, Σ, δ, q0, F)
where
Q is a finite set called the states
Σ is a finite set called the alphabet
δ : Q ×Σ → Q is the transition function
q0 ∈ Q is the start state also called initial state
F ⊆ Q is the set of accept states, also called the final states
 Transition Diagram (Transition graph)

It is a directed graph associated with the vertices of the graph corresponds to
the states of the finite automata. (or) It is a 5-tuple graph used state and edges
represent the transitions from one state to other state.
Example: 0 1
1
1 0
q0 q1 q q22
Start or Initial State Final or Accepting State
4 / 28
Unit – I
 Transition Table.
It is the tabular representation of the DFA. For a transition table the transition
function is used.
Example:
0 Input 1
States
{q0} {q1} {q0}
{q1} - {q2}
*{q2} - -
 Transition Function.
- The mapping function or transition function denoted by δ.
- Two parameters are passed to this transition function: (i) current state and
(ii) input symbol.
- The transition function returns a state which can be called as next state.
δ ( current_state, current_input_symbol ) = next_state
Example:
δ ( q0, a ) = q1
 Computation of a Finite Automaton

o The automaton receives the input symbols one by one from left to right.
o After reading each symbol, M1 moves from one state to another along the
transition that has that symbol as its label.
o When M1 reads the last symbol of the input it produces the output: accept if
M1 is in an accept state, or reject if M1 is not in an accept state.
 Applications
o It plays an important role in complier design.
o In switching theory and design and analysis of digital circuits automata theory
is applied.
o Design and analysis of complex software and hardware systems.
o To prove the correctness of the program automata theory is used.
o To design finite state machines such as Moore and mealy machines.
o It is base for the formal languages and these formal languages are useful of the
programming languages.
 Types of Finite Automata

o Finite Automata without output
o Deterministic Finite Automata (DFA)
o Non-Deterministic Finite Automata (NFA or NDFA)
o Non-Deterministic Finite Automata with ε move (ε-NFA or ε-NDFA)
o Finite Automata with output
o Moore Machine
o Mealy Machine
5 / 28
Unit – I
Deterministic Finite Automata (DFA)
Deterministic Finite Automaton is a FA in which there is only one path for a specific
input from current state to next state. There is a unique transition on each input symbol.
 Formal Definition of Deterministic Finite Automata

where
δ : Q ×Σ → Q is the transition function
0
1 qS21
S0 1 1
0
S2
0
Non-Deterministic Finite Automata (NDFA or NFA)
Non-Deterministic Finite Automaton is a FA in which there many paths for a

specific input from current state to next state.
 Formal Definition of Non-Deterministic Finite Automata

where
δ : Q ×Σ → 2Q is the transition function
1
1
0
0 1 qq22
q0 q1
6 / 28
Unit – I
Finite Automaton with ε- moves

The finite automata is called NFA when there exists many paths for a specific input
or ε from current state to next state. The  is a character used to indicate null string.
 Formal Definition of Non-Deterministic Finite Automata

where
δ : Q ×(Σ  {ε}) → 2Q is the transition function
1
0
1

  qq22
q0 q1
Differentiate DFA and NFA

Sl. No DFA NFA
DFA is Deterministic Finite NFA is Non-Deterministic Finite
1.
Automata Automata
For given state, on a given input For given state, on a given input
2. we reach to deterministic and we reach to more than one state.
unique state.
DFA is a subset of NFA Need to convert NFA to DFA in
3.
the design of complier.
4. δ : Q ×Σ → Q δ : Q ×Σ → 2Q
Example: δ(q0, a) = {q1} Example : δ(q0, a) = {q1, q2}
Problems for Finite Automata

1. Design FA which accepts odd number of 1’s and any number of 0’s.
0
1 qS21
S0 1 1
0
S2
0
2. Design FA to accept the string that always ends with 00.

1 0
0 0
q0 q1 qq22
1
1
7 / 28
Unit – I
3. Design FA to check whether given unary number is divisible by three.
1 1 1 qq2
q0 q1 q1 2
1
4. Design FA to check whether given binary number is divisible by three.
0
0 qS21
S0 1 1
0
1 0
S2 S3
0
5. Obtain the  closure of states q0 and q1 in the following NFA with  transition.
a b c


q0 q1 q2
Solution:
 - CLOSURE {q0} = {q0, q1,q2}
 - CLOSURE {q1} = {q1,q2}
6. Obtain  closure of each state in the following NFA with  move.

2
0 1
 
q0 q1 qq22
Solution:
 - CLOSURE {q0} = {q0, q1,q2}
 - CLOSURE {q1} = {q1,q2}
 - CLOSURE {q2} = {q2}
Tutorial:
7. Design Finite Automata which accepts the only 0010 over the input Σ = {0, 1}.
8. Design Finite Automata which checks whether given binary number is even or
odd over the input Σ = {0, 1}.
9. Design Finite Automata which accepts only those strings which starts with ‘a’
and end with ‘b’ over the input Σ = {a, b}.
8 / 28
Unit – I
10. Design a DFA to accept the language L = {w | w has both an even number of 0’s
and an even number of 1’s.
11. Design a DFA to accept the language L = {w | w has both an odd number of 0’s
and an odd number of 1’s.
12. Obtain  closure of each state in the following NFA with  move.
b
a, b
ε ε a, b
q0 q1 qq22
Equivalence of NFA and DFA

For every NFA, there exists an equivalent DFA.
Theorem:
For every NFA, there exists a DFA which simulates the behavior of NFA. If L is the set
accepted by NFA, then there exists a DFA which also accepts L.
Or
Let L be a set accepted by NFA (L(M)), then there exists a DFA that accepts (L(Mʹ)).
Proof:
Let M = (Q, Σ, δ, q0, F) be an NFA for language L, then define DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ).
 The states of Mʹ are all the subset of M.
 The elements in Qʹ will be denoted by [q1, q2, q3, … , qi] and the elements in Q are
denoted by {q1, q2, q3, … , qi}.
 Initial state of NFA is q0, and also an initial state of DFA is q0ʹ =[q0].
 we define
δʹ ([q1, q2, q3, …, qi],a) = [p1, p2, p3, …, pi]
if only if
δ({q1, q2, q3, …, qi},a) = {p1, p2, p3, …, pi}
This means that whenever in NFA, at the current state {q1, q2, q3, …, qi} if we
get input ‘a’ and it goes to the next states {p1, p2, p3, …, pi} then while constructing
DFA for it the current state is assumed to be [q 1, q2, q3, …, qi]. At this state, the input
is ‘a’ and it goes to the next state is assumed to be [p 1, p2, p3, …, pi]. On applying
transition function on each of the state’s q1, q2, q3, …, qi the new state may be any of
the state’s from p1, p2, p3, …, pi.
Theorem can be proved with the induction method by assuming length of input string ‘x’.
δʹ(q0ʹ, x) = [q1, q2, q3, …, qi]

if only if
δ(q0, x) = {q1, q2, q3, …, qi}
9 / 28
Unit – I
Basis method:
If the input string length is 0. ie. |x|=0 where x = {ε}, then q0ʹ = [q0].
Induction method:
If we assume that the hypothesis is true for the length of input string is less than or
equal to ‘m’. Then if ‘xa’ is a length of string is m+1. Hence the transition function (δʹ) could
be written as,
δʹ (q0ʹ, xa) = δʹ (δʹ (q0ʹ, x),a)
By induction hypothesis,
δʹ(q0ʹ, x) = [p1, p2, p3, …, pi]

if only if
δ(q0, x) = {p1, p2, p3, …, pi}
By definition of δʹ
δʹ( [p1, p2, p3, …, pi], a) = [r1, r2, r3, …, ri]

if only if
δ({p1, p2, p3, …, pi}, a) = {r1, r2, r3, …, ri}
Thus,
δʹ (q0ʹ, xa) = [r1, r2, r3, …, ri]
if only if
δ (q0, xa) = {r1, r2, r3, …, ri}
Shown by induction hypothesis,
L(M) = L(Mʹ)
Extended Transition Function (δʹʹ or δ^)
This is used to represent transition functions with a string of input symbols ‘w’ and returns a
set of states. It is represented by δʹʹ or δ^
Suppose w = xa
δ (q, x) = {p1, p2, p3, …, pk}
then
∞
U δʹʹ(pi,a) = {r1, r2, r3, …, rm}
i=0
δʹʹ(pi, xa) = δʹʹ( δ(q,x) a))
10 / 28
Unit – I
Example Problems for Converting NFA into DFA
1. Obtain the DFA equivalent to the following NFA.
0, 1
0 1
q0 q1 qq22
Solution :
The transition table for given NFA can be drawn as follows
0 Input 1
States
{q0} {q0}{q1} {q0}
{q1} - {q2}
*{q2} - -
Let the DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ) then, transition function (δʹ) will be computed as,
δʹ([q0], 0) = [q0, q1] - a new state - A

δʹ([q0], 1) = [q0]
δʹ([q1], 0) = -
δʹ([q1], 1) = [q2]
δʹ([q2], 0) = -
δʹ([q2], 1) = -
δʹ([qo,q1],0) = [q0,q1]
δʹ([qo,q1],1) = [q0,q2] a new state - B
δʹ([qo,q2],0) = [q0,q1]
δʹ([qo,q2],0) = [q0]
The transition table for DFA

States 0 Input 1
[q0] [q0, q1] [q0]

[q1] - [q2]
*[q2] - -
[q0, q1] [q0, q1] [q0, q2]
*[q0, q2] [q0, q1] [q0]
The transition diagram for DFA
1 0
1 qq221
0 1 q1
q0 A qB2
0
1
11 / 28
Unit – I
2. Let M = ({q0, q1}, {0,1}, δ, q0, {q1}) be NFA. Where δ (q0, 0) = {q0, q1},
δ (q0, 1) = {q1}, δ (q1, 0) = {}, δ (q1, 1) = {q0, q1}. Construct its equivalent DFA.
Solution :
The transition table for NFA
0 Input 1
States
{q0} {q0}{q1} {q1}
*{q1}  {q0}{q1}
The transition diagram for NFA
1
0
0, 1
q0 qq21
Let the DFA Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ) then, transition function (δʹ) will be computed as,
δʹ ([q0], 0) = [q0, q1] -a new state A

δʹ([q0], 1) = [q1]
δʹ([q1], 0) = 
δʹ([q1], 1) = [q0]
δʹ([q0,q1],0) = [q0,q1]
δʹ([qo,q1],1) = [q0,q1]
States 0 Input 1
[q0] [q0, q1] [q1]

*[q1]  [q0]
*[q0, q1] [q0, q1] [q0, q1]

1
1
q0 q1
[q0,q1] 0, 1
12 / 28
Unit – I
Tutorial:
3. Obtain the DFA equivalent to the following NFA.

a, b
a, b
b a a, b
q0 q1 qq22
4. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be NFA. Where δ (q0, 0) = {q0, q1},
δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2},
δ (q2, 1) = {q0, q3}, δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, Construct its equivalent
DFA.
Equivalence of NDFA’s with and without ε-moves
Theorem:
If L is accepted by NFA with ε-moves, then there exists L which is accepted by NFA
without ε-moves.
Proof:
Let M = (Q, Σ, δ, q0, F) be an NFA with ε-moves for language L, then define NFA without
ε-moves Mʹ = (Qʹ, Σʹ, δʹ, q0ʹ, Fʹ).
 The elements in Qʹ will be denoted by [q1, q2, q3, … , qi] and the elements in Q are
denoted by {q1, q2, q3, … , qi}.
 Initial state of NFA with ε-moves is q0, and also an initial state of NFA without ε-moves
is q0ʹ =[q0].
 Fʹ =
 δʹ can be denoted by δʹʹ with some input.
Basis:
|X| = 1, where X is a symbol ‘a’.
δʹ(q0,a) = δʹʹ(q0,a)
Induction:
|X| > 1, Let X = wa
δʹ(q0,wa) = δʹ( δʹʹ(q0,w),a)
By induction hypothesis,
δʹ(q0,w) = δʹʹ(q0,w) = p
Now we will show that
δʹ(p,a) = δ(q0,wa)
But,
δʹ(p,a) = δʹ(q,a) = δʹʹ(q,a) as p = δʹʹ(q0,w)
We have
δʹʹ(q,a) = δʹʹ(q0,wa)
Thus by definition of δʹʹ
δʹ(q0,wa) = δʹʹ(q0,wa)
13 / 28
Unit – I
Example Problems for Converting NFA with  into NFA without 


1. Construct NFA without  from NFA with .
2
0 1
 
q0 q1 qq22
Solution:
Find the ε – closure function of all states:
ε – closure (q0) = {q0, q1, q2}
ε – closure (q1) = {q1, q2} ε – closure (q0)
ε – closure (q2) = {q2} = { q0,q1,q2}
Compute δʹ function:
δʹ(q0,0) = δʹʹ (q0,0) = ε – closure (δ(δʹ(q0,ε),0))
= ε – closure (δ({q0,q1,q2},0))
= ε – closure (q0) = {q0,q1,q2}
= ε – closure (δ({q0,q1,q2},1))
= ε – closure (q1) = {q1,q2}
= ε – closure (δ({q0,q1,q2},2))
= ε – closure (q2) = {q2}
= ε – closure (δ({q1,q2},0))
= ε – closure () = {}
= ε – closure (δ({q1,q2},1))
= ε – closure (q1) = {q1,q2}
= ε – closure (δ({q1,q2},2))
= ε – closure (δ({q2},0))
= ε – closure () = {}
= ε – closure () = {}
14 / 28
Unit – I

Input
States
0 1 2
q0 {q0,q1,q2} {q1,q2} {q2}
q1 {} {q1,q2} {q2}
*q2 {} {} {q2}
2
0 1
0,1 1,2
q0 q1 qq22
0,1,2
2. Construct NFA without  from NFA with .

0 1
ε
qq20 qq21
Solution:
Find the ε – closure function of all states:
ε – closure (q0) = {q0, q1}
ε – closure (q1) = {q1}
Compute δʹ function:
= ε – closure (δ({q0,q1},0))
= ε – closure (q0) = {q0,q1}
= ε – closure (δ({q0,q1},1))
= ε – closure () = {}
States 0 Input 1
*q0 {q0,q1} {q1}

*q1 {} {q1}
15 / 28
Unit – I

0 1
0,1
qq20 qq21
Tutorial:
1. Obtain the NFA equivalent to the following NFA with -move.

b
a, b
ε ε a, b
q0 q1 qq22
2. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be -NFA.

Where δ (q0, 0) = {q0, q1}, δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, ε) = {q1},
δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2}, δ (q2, ε) = {q3}, δ (q2, 1) = {q0, q3,},
δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, δ (q3, ε) = {q0}. Construct its equivalent
NFA.
Example Problems for Converting NFA with -move into DFA
1. Construct DFA from the following -NFA.

b
a, b
ε ε a, b
q0 q1 qq22
Solution:
ε – closure (q0) = {q0, q1, q2}  A new state in DFA
ε – closure (δ (A, a)) = ε – closure (q0,q2)

= {q0, q1, q2}  A
ε – closure (δ (A, b)) = ε – closure (q0,q1,q2)
= {q0, q1, q2}  A
Input
States a,b
A b
*A A A
The transition diagram for DFA qA2
16 / 28
Unit – I
2. Construct DFA from the following -NFA.

0
1 0
r
q
ε
0 ε
1
p
ε ε
qs2
0
Solution:
ε – closure (p) = {p,q,r}  A new state in DFA
ε – closure (δ (A, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

= {p,q,r}  {r,s} = {p,q,r,s}  B new state in DFA
ε – closure (δ (A, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

= {q,r}  {p,q,r,s} = {p,q,r,s}  B
ε – closure (δ (B, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

= {p,q,r}  {r,s} = {p,q,r,s}  B
ε – closure (δ (B, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

= {q,r}  {p,q,r,s} = {p,q,r,s}  B
0 Input 1
States
A B B
*B B B
0,1
0,1
A qB
2
17 / 28
Unit – I
Tutorial:
1. Obtain the DFA equivalent to the following NFA with -move.

2
0 1
 
q0 q1 qq22
2. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be -NFA.

Where δ (q0, 0) = {q0, q1}, δ (q0, 1) = {q1}, δ (q1, 0) = {q2,q3}, δ (q1, ε) = {q1},
δ (q1, 1) = {q0, q1}, δ (q2, 0) = {q2}, δ (q2, ε) = {q3}, δ (q2, 1) = {q0, q3,},
δ (q3, 0) = {q3}, δ (q3, 1) = {q2, q3}, δ (q3, ε) = {q0}. Construct its equivalent
DFA.
Minimization of DFA
 DFA minimization stands for converting a given DFA to its equivalent DFA with
minimum number of states.
 Suppose there is a DFA M = (Q, ∑, q0, δ, F) which recognizes a language L. Then the
minimized DFA M = (Q’, ∑, q0, δ’, F’) can be constructed for language L as:
1. We will divide Q (set of states) into two sets. One set will contain all final states
and other set will contain non-final states. This partition is called P0.
2. Initialize k = 1
3. Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take
all possible pair of states. If two states of a set are distinguishable, we will split the
sets into different sets in Pk.
4. Stop when Pk = Pk-1 (No change in partition)
5. All states of one set are merged into one. No. of states in minimized DFA will be
equal to no. of sets in Pk.
Example:
Consider the following DFA into minimized DFA.
18 / 28
Unit – I
Solution:
Transition Table for DFA
0 Inputs 1
States
q0 q3 q1
*q1 q2 q5
*q2 q2 q5
q3 q0 q4
*q4 q2 q5
q5 q5 q5
Step 1: Divide into two sets. One set is containing final states and other set containing
non-final states.
Inputs Partition
States
0 1 (P0)
q0 q3 q1
Non-Final
q3 q0 q4
States
q5 q5 q5
*q1 q2 q5
*q2 q2 q5 Final States
*q4 q2 q5
Step 2: To calculate P1, we will check whether sets of partition P0 can be partitioned or
not:
For set { q1, q2, q4 } :

 δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are
not distinguishable.
 Similarly, δ ( q1, 0 ) = δ ( q4, 0 ) = q2 and δ ( q1, 1 ) = δ ( q4, 1 ) = q5, So q1
and q4 are not distinguishable.
 So, q2 and q4 are not distinguishable. So, {q1, q2, q4} set will not be
partitioned in P1.
Inputs Partition
States
0 1 (P0)
q0 q3 q1
Non-Final
q3 q0 q4
States
q5 q5 q5
*q1 q2 q5
*q2 q2 q5 Final States
*q4 q2 q5
19 / 28
Unit – I
Step 3: Remove q2 and q4 row from the table and replace q2 and q4 into q1 where
however present in the table.
Inputs Partition
States
0 1 (P0)
q0 q3 q1
Non-Final
q3 q0 q4 q1
States
q5 q5 q5
Final
*q1 q1 q5
States
Step 4:
 δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0 - Moves of q0 and q3 on input symbol 0
are q3 and q0 respectively which are in same set in partition P0.
 δ ( q0, 1) = δ ( q3, 1 ) = q1 - Moves of q0 and q3 on input symbol 1 is q1
which are in same set in partition P0.
 So, q0 and q3 are not distinguishable.
Step 5: Remove q3 row from the table and replace q3 into q0 where however present in
the table.
Inputs Partition
States
0 1 (P0)
q0 q3 q0 q1
Non-Final
q3 q0 q1
States
q5 q5 q5
Final
*q1 q1 q5
States
Step 6: Final Transition Table for DFA (no more not distinguishable)
Inputs Partition
States
0 1 (P0)
q0 q0 q1 Non-Final
q5 q5 q5 States
Final
*q1 q1 q5
States
Step 7: Transition Diagram for minimized DFA

0,1
0 0
1 1
q0 qq21 q5
20 / 28
Unit – I
Tutorial:
1. Consider the following DFA into minimized DFA.
2. Consider the following DFA into minimized DFA.
Finite automata with Output

 Finite automata may have outputs corresponding to each transition. There are two model
or machine for finite automata with output.
Finite Automata
with Output
Mealy Machine Moore Machine
Mealy Machine
 A Mealy Machine is an FSM whose output depends on the present state as well as the
present input.
 The value of the output function z(t) depends only on the present state q(t) and present
input λ (t), i.e. z(t) = λ (q(t), x(t))
 The length of output for a mealy machine is equal to the length of input. If input string ,
the output string is also .
21 / 28
Unit – I
 It can be described by a 6 tuples M = (Q, ∑, Δ, δ, λ, q0)

where
 Q is a finite set of states.
 ∑ is a finite set of input symbols
 Δ is a finite set of output symbols
 δ is the input transition function where δ: Q × ∑ → Q
 λ is the output transition function where λ : Q × ∑ → Δ
 q0 is the initial state
 Transition table of mealy machine:

Input = 0 Input = 1
Present State
Next State Output Next State Output
q0 q1 0 q2 0
q1 q1 0 q2 1
q2 q1 1 q2 0
 Transition diagram of mealy machine:
Moore Machine
 Moore machines are FSM whose output depends on the present state as well as the
previous state.
 The value of the output function z(t) depends only on the present state q(t) and
independent of the current input x(t), i.e. z(t) = λ (q(t))
 The length of output for a moore machine is greater than input by 1. If input string , the
output string is Δ= λ (q(t)).
 It can be described by a 6 tuples M = (Q, ∑, Δ, δ, λ, q0)
where
 Q is a finite set of states.
 ∑ is a finite set of input symbols
 Δ is a finite set of output symbols
 δ is the input transition function where δ: Q × ∑ → Q
 λ is the output transition function where λ : Q → Δ
 q0 is the initial state
22 / 28
Unit – I
 Transition table of moore machine:
Next State
Present State Output
Input = Input =
0 1
q0 q1 q2 0
q1 q1 q3 0
q2 q4 q2 0
q3 q4 q2 1
q4 q1 q3 1
 Transition diagram of moore machine:
Mealy Machine vs. Moore Machine

Mealy Machine Moore Machine
Output depends both upon the present state Output depends only upon the present state.
and the present input
Generally, it has fewer states than Moore Generally, it has more states than Mealy
Machine. Machine.
The value of the output function is a The value of the output function is a function
function of the transitions and the changes, of the current state and the changes at the
when the input logic on the present state is clock edges, whenever state changes occur.
done.
Mealy machines react faster to inputs. They In Moore machines, more logic is required to
generally react in the same clock cycle. decode the outputs resulting in more circuit
delays. They generally react one clock cycle
later.
23 / 28
Unit – I
Transforming Mealy Machine into Moore Machine
 Transform Mealy Machine into Moore Machine for the given input string and the output
string as same (except for the first symbol).
 Algorithm:
 Step 1: Look into the next state column for any state (example q0,q1, …. qi) and
determine the number of different outputs associated with qi in that column
(output column values are same or different).
 Step 2: qi into several different states. The number of such states being equal to
the number of outputs associated with qi.
 Step 3: qi replaced by qi0 for output 0 and qi1 for output 1
 Step 4: Convert Mealy Structure to Moore Structure
 Step 5: Add new start state with output 0 and next states same as the next states of
first state.
 Example:
Consider the Mealy machine described by the transition table given below. To
construct a Moore machine, this is equivalent to mealy machine.
a=0 a=1
Present State
q1 q3 0 q2 0
q2 q1 1 q4 0
q3 q2 1 q1 1
q4 q4 1 q3 0
Solution:
Step 1: Look into the next state column for any state (example q0,q1, …. qi) and
determine the number of different outputs associated with qi in that column (output column
values are same or different).
Determine same or
a=0 a=1
different output
Present State
q1 q3 0 q2 0 same
q2 q1 1 q4 0 different
q3 q2 1 q1 1 same
q4 q4 1 q3 0 different
24 / 28
Unit – I
Step 2: q2 split into q20 and q21 states. Similarly q4 split into q40 and q41.
a=0 a=1
Present State
q1 q3 0 q2 0
q20
q2 q1 1 q4 0
q21
q3 q2 1 q1 1
q40
q4 q4 1 q3 0
q41
a=0 a=1
Present State
q1 q3 0 q2 0
q20 q1 1 q4 0
q21 q1 1 q4 0
q3 q2 1 q1 1
q40 q4 1 q3 0
q41 q4 1 q3 0
Step 3: q2 replaced by q20 for output 0 and q21 for output 1, similarly q4 replaced by q40
for output 0 and q41 for output 1
a=0 a=1
Present State
q1 q3 0 q20 0
q20 q1 1 q40 0
q21 q1 1 q40 0
q3 q21 1 q1 1
q40 q41 1 q3 0
q41 q41 1 q3 0
25 / 28
Unit – I
Step 4: Convert Mealy Structure to Moore Structure
Next State
a=0 a=1
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1 0
q40 q41 q3 0
q41 q41 q3 1
Step 5: Add new start state with output 0 and next states same as the next states of first state.
Next State
a=0 a=1
q0 q3 q20 0
q1 q3 q20 1
q20 q1 q40 0
q21 q1 q40 1
q3 q21 q1 0
q40 q41 q3 0
q41 q41 q3 1
Transition Diagram for Moore Machine

0
0 q3/ 1
0
q41/
0 1 1
q0/ 0 1
0 1
q1/ q21/
1 1
1
1
0 1 0
q20/
0 q40/
0
1
26 / 28
Unit – I
Transforming Moore Machine into Mealy Machine

 Transform Mealy Machine into Moore Machine for the given input string and the output
string as same.
 Algorithm:
 Step 1: Remove output column from moore table and add output column to
mealy table
 Step 2: Fill the output column from moore table.
Example:
Consider the Moore machine described by the transition diagram given below. To
construct a Mealy machine, which is equivalent to moore machine.
1
q3/
1
0
1
q0/ 0
0
0
0 q2/
0
1
q1/ 1
1
Transition Table for Moore Machine

Next State
a=0 a=1
q0 q3 q1 0
q1 q1 q2 1
q2 q2 q3 0
q3 q3 q0 1
Solution:
Step 1: Remove output column from moore table and add output column to mealy table
Transition Table for Mealy:
a=0 a=1
Present State
q0 q3 1 q1 1
q1 q1 1 q2 0
q2 q2 0 q3 1
q3 q3 1 q0 0
27 / 28
Unit – I
Transition Diagram for Mealy:

0/1
0/1 q3
1/1 0/0
q0
1/0
0/1 q2
1/1
q1 1/0
Tutorial Problems:
1. Construct the moore machine from the given mealy machine.
2. Construct the moore machine from the given mealy machine.
28 / 28
Unit – II
Equivalence of finite Automaton and regular expressions
Regular Languages
A language is called regular language if there exists a finite automaton that recognizes
it. For example finite automaton M recognizes the language L if L = {w | M accepts w}.
 Operations on Regular Languages

Let A and B be languages. We define regular operations union, concatenation,
and star as follows:
- Union : A 𝖴 B = {x | x ∈ A ∨ x ∈ B}
- Concatenation : A ◦ B = {xy | x ∈ A 𝖠 y ∈ B}
- Star : A* = {x1x2 . . . xk | k ≥ 0 𝖠 xi ∈ A, 1 ≤ i ≤ k}
Regular Expression
Let Σ be an alphabet. The regular expressions over Σ and the sets that they denote are
defined recursively as follows:
a. Ø is a regular expression and denotes the empty set.
b.  is a regular expression and denotes the set {}
c. For each ‘a’ Σ, ‘a’ is a regular expression and denotes the set {a}.
d. If ‘r’ and ‘s’ are regular expressions denoting the languages L1 and L2
respectively then
 Union : r + s is equivalent to L1 U L2
 Concatenation : rs is equivalent to L1L2
 Closure : r* is equivalent to L1*
Problems for Regular Expression
1. Write the regular expression for the language accepting all combinations of a’s
over the set  = {a}.
L = { a,aa,aaa,… ....................... }
R= a* (i.e. kleen closure)
2. Write regular expression for the language accepting the strings which are
starting with 1 and ending with 0, over the set  = {0,1}.
L = { 10,1100,1010,100010… ....................... }
R= 1(0+1)*0
1/2
Unit – II
3. Show that (0*1*)* = (0+1)*.
LHS : (0*1*)* = { , 0,1,00,11,0011,011,0011110… .................... }

RHS : (0+1)* = { , 0,1,00,11,0011,011,0011110… ................... }
Hence
LHS = RHS is proved
4. Show that (r+s)*  r* + s*.
LHS : (r+s)* = { , r,s,rs,rr,ss,rrrsssr, ....................... }

RHS : r* + s* = { , r,rr,rrr………….}U { , s,ss,sss,… ............}
= { , r,rr,rrr,s,ss,ssss .................... }
Hence
LHS ≠ RHS is proved
5. Describe the following by regular expression

a. L1 = the set of all strings of 0’s and 1’s ending in 00.
b. L2 = the set of all strings of 0’s and 1’s beginning with 0 and ending with .
r1 = (0+1)*00
r2 = 0(0+1)*1
6. Show that (r*)* = r* for a regular expression r.

LHS = r* = { ε, r,rr,rrr, .................... )
(r*)* = { ε, r,rr,rrr, .................... )*
(r*)* = { ε, r,rr,rrr, .................... ) = r*
LHS = RHS
7. If L = {The language starting and ending with ‘a’ and having any combinations
of b’s in between, that what is r?
r1 = a b*a
8. Give regular expression for L= L1  L2 over alphabet {a,b}

where L1 = all strings of even length,
L2 = all strings starting with ‘b’.
r = r1 + r2
r = anbn + b (a+b)*
2/2
Unit – III
Introduction
 Language: “A language is a collection of sentences of finite length all constructed
from a finite alphabet of symbols.”
 Grammar: “A grammar can be regarded as a device that enumerates the sentences of
a language.”
 A formal grammar is a quad-tuple G = (N, T, P, S)

where
N is a finite set of non-terminals
T is a finite set of terminals and is disjoint from N
P is a finite set of production rules of the form w (NT)∗ → w (NT)∗
S  N is the start symbol
 Chomsky Hierarchy (Types of grammars)
Class Grammars Languages Automaton Rules

Type-0 Unrestricted Recursively Turing Rules are of the form:
Grammar enumerable machine α → β,
Language where α and β are arbitrary strings
over a vocabulary V and α ≠ ε
Type-1 Context- Context- Linear- Rules are of the form:
sensitive sensitive bounded αAβ → αBβ
Grammar Language automaton S→ε
where
A, S  N
α, β, B (N T)∗ B ≠ ε
Type-2 Context-free Context-free Pushdown Rules are of the form:
Grammar Language automaton A→ α
where A  N
α  (N  T)∗
Type-3 Regular Regular Finite Rules are of the form:
Grammar Language automaton A→ε
A→α
A → αB
where A, B N and α T
1 / 35
Unit – III
 Scope of each type of grammar

A figure shows the scope of each type of grammar:
 Type - 3 Grammar
 Type-3 grammars generate regular languages. Type-3 grammars must have a
single non-terminal on the left-hand side and a right-hand side consisting of a
single terminal or single terminal followed by a single non-terminal.
 The productions must be in the form
X→a
X → aY
where X, Y ∈ N (Non terminal) and a ∈ T (Terminal)

 The rule S → ε is allowed if S does not appear on the right side of any rule.
 Example
X→ε
X → a | aY
Y→b
 Type-2 grammars generate context-free languages. These languages generated by
these grammars are be recognized by a non-deterministic pushdown automaton.
A→γ
where A ∈ N (Non terminal) and γ ∈ (T 𝖴 N)* .
 Example
S→Xa
X→ a
X → aX
X → abc
X→ε
 Type-1 grammars generate context-sensitive languages.
αAβ→αγβ
Where A ∈ N (Non-terminal) and α, β, γ ∈ (T 𝖴 N)*
2 / 35
Unit – III
 The strings α and β may be empty, but γ must be non-empty.

 The rule S → ε is allowed if S does not appear on the right side of any rule. The
languages generated by these grammars are recognized by a linear bounded
automaton.
 Example
AB → AbBc
A → bcA
B→b
 Type-0 grammars generate recursively enumerable languages. The productions
have no restrictions. They are any phase structure grammar including all formal
grammars.
 They generate the languages that are recognized by a Turing machine.
 The productions can be in the form of
α→β
where α is a string of terminals and non-terminals with at least one non-
terminal and α cannot be null. β is a string of terminals and non-terminals.
 Example
S → ACaB
Bc → acB
CB → DB
aD → Db
Regular grammars
 Formal Definition of Regular Grammars
 A regular grammar is a mathematical object, G, with four components,
G = (N, T, P, S)
Where
N is a nonempty, finite set of non-terminal symbols
T is a finite set of terminal symbols
P is a set of grammar rules, each of one having one of the forms
A → aB
A→a
A → ε, for A, B  N, a  T, and ε the empty string
S is the start symbol S ∈ N
 Definition: The Language Generated by a Regular Grammar

 Let G = (N, T, P, S) be a regular grammar. We define the language generated by
G to be L(G)
 L(G) = {w | S ⇒ * w, where w T*}
Linear grammar
 A linear grammar is a context-free grammar that has at most one non-terminal symbol
on the right hand side of each grammar rule.
S → aA
A → aB
B → Bb
3 / 35
Unit – III
Left Linear grammars

 A left linear grammar is a linear grammar in which the non-terminal symbol always
occurs on the left side.
 In a grammar if all productions are in the form
A→ B α
A→ α where A,B  V and α  T*
 Example
A → Aa / Bb / b
Right Linear grammars

 A right linear grammar is a linear grammar in which the non-terminal symbol always
occurs on the right side.
 In a grammar if all productions are in the form
A→ α B
A→ α where A,B  V and α  T*
 Example
A → aA / bB / b
Converting Left Linear grammars into Right Linear grammars

 Algorithm:
1. If the left linear grammar has a rule S → a, then make that a rule in the right
linear grammar
2. If the left linear grammar has a rule A → a, then add the following rule to the
right linear grammar: S → aA
3. If the left linear grammar has a rule B → Aa, add the following rule to the
right linear grammar: A → aB
4. If the left linear grammar has a rule S → Aa, then add the following rule to the
right linear grammar: A → a
 Example 1:
Left Linear Grammar Right Linear Grammar
S → Aa S → abA
A → ab A→ a
 Example 2:
Left Linear Grammar
S → Ab
S → Sb
A → Aa
A→a
Step 1: Make new non-terminal
S0 → S
S → Ab
S → Sb
A → Aa
A→a
4 / 35
Unit – III
Step 2: If the left linear grammar has this rule A → p, then add the following
rule to the right linear grammar: S → pA
Left Linear Grammar Left Linear Grammar
S0 → S S0 → aA
S → Ab
S → Sb
A → Aa
A→a
Step 3: If the left linear grammar has a rule B → Ap, add the following rule
to the right linear grammar: A → pB
S0 → S S0 → aA
S → Ab A → bS
S → Sb A → aA
A → Aa S → bS
A→a
Step 4: If the left linear grammar has S → Ap, then add the following rule to
the right linear grammar: A → p
S0 → S S0 → aA
S → Ab A → bS
S → Sb A → aA
A → Aa S → bS
A→a S→ε
Step 5: Equivalent Right Linear Grammar:

S0 → aA
A → bS
A → aA
S → bS
S→ε
Equivalence of regular grammar and Finite Automata
 Conversion of Finite Automata to Right Linear Regular Grammar

1. Algorithm:
1. Repeat the process for every state.
2. Begin the process from start state.
3. Write the production as the output followed by the state on which the
transition is going.
4. And at the last add ε because that’s required to end the derivation.
5 / 35
Unit – III
 Problems for Finite Automata to Right Linear Regular Grammar:
1. Construct Right Linear Grammar from the given Finite Automata
1) Pick start state and output is on symbol 'a' we are going on state B
So, we will write as :
A → aB
2) Then we will pick state B and then we will go for each output.
So, we will get the below production.
B→aB/bB/ε
3) So, final we got right linear grammar as:
A → aB
B → aB/bB/ε
1) Pick start state and output is on symbol 'ab' we are going on state A
S → abA
2) Pick start state and output is on symbol 'ba' we are going on state B
S → baA
3) Pick start state and output is on symbol 'ε ' we are going on state B and C
S → B and S → ε (C is final state)
4) Then we will pick state A and then we will go for each output.
A→ bS and A→ b ( C is final state)
B→ aS
6) Then we will pick state C and then we will go for each output.
C→ ε
S → abA / baA / B / ε
A→ bS / b
B → aS
C→ε
6 / 35
Unit – III
 Conversion of Regular language to Right Linear Regular Grammar

Algorithm:
1. Construct Finite automata from regular language.
 Problems for Regular language to Right Linear Regular Grammar:
3. Construct Regular language from the given Finite Automata

L = {All strings start with ‘a’ over  = (a+b)*}.
1) Construct Finite automata from given regular language.
A → aB
B→aB/bB/ε
A → aB
B → aB/bB/ε
 Conversion of Regular expression to Right Linear Regular Grammar

Algorithm:
1. Construct Finite automata from regular expression.
 Problems for Regular language to Right Linear Regular Grammar:
4. Construct Regular Expression from the given Finite Automata

r = a(a+b)*
1) Construct Finite automata from given regular expression.
7 / 35
Unit – III
A → aB
B→aB/bB/ε
A → aB
B → aB/bB/ε
Tutorial Questions:
1 0
0 A 1
S qB2
0
1
a, b
a, b
b a a, b
q0 q1 qq22
8. Construct Right Linear Grammar from the following Regular Languages.

a. L = {All the strings starting and ending with ‘a’ and having any
combinations of b’s in between over  = (a, b)}.
b. L = {The set of all strings of 0’s and 1’s ending in 00 over  = (0, 1)}.
c. L = {The set of all strings of 0’s and 1’s beginning with 0 and ending with
1 over  = (0, 1)}.
9. Construct Right Linear Grammar from the following Regular Expressions.

a. r = (0+1)*11
b. r = a(a+b)*b
8 / 35
Unit – III
 Conversion of Right Linear Regular Grammar to Finite Automata

Algorithm:
Given a regular grammar G, a finite automata accepting L(G) can be obtained as
follows:
1. The number of states in the automata will be equal to the number of non-
terminals plus one. Each state in automata represents each non-terminal in the
regular grammar. The additional state will be the final state of the automata.
The state corresponding to the start symbol of the grammar will be the initial
state of automata. If L(G) contains ϵ that is start symbol is grammar devices to
ϵ, then make start state also as final state.
2. The transitions for automata are obtained as follows:
 For every production A → aB, then make δ(A, a) = B that is make an
are labeled ‘a’ from A to B.
 For every production A → a, then make δ(A, a) = final state.
 For every production A → ϵ, then make δ(A, ϵ) = A and A will be final
state.
 Problems for Right Linear Regular Grammar to Finite Automata

1. Construct a Finite Automata from the given Right Linear Grammar
A → aB/bA/b
B → aC/bB
C → aA/bC/a
Solution:
Step 1: Take the ‘A’ productions, then will make transition functions
A → aB  δ(A, a) = B
A → bA  δ(A, b) = A
A→ b  δ(A, b) = Final State
Step 2: Take the ‘B’ productions, then will make transition functions
B → aC  δ(B, a) = C
B → bB  δ(B, b) = B
Step 3: Take the ‘C’ productions, then will make transition functions
C → aA  δ(C, a) = A
C → bC  δ(C, b) = C
C→b  δ(C, b) = Final State
Step 4: Construct Finite Automata

a
b b b
a a
A B C
b a
D * State D is a new final State
9 / 35
Unit – III

S→A/B/ε
A → 0S/1B/0
B → 0S/1A/1
Solution:
Step 1: Take the ‘S’ productions, then will make transition functions
S→ A  δ(S, ε) = A
S→ B  δ(S, ε) = B
S→ ε  δ(S, ε) = S and S is make Final State
A → 0S  δ(A, 0) = S
A → 1B  δ(A, 1) = B
A→ 0  δ(A, 0) = Final State
B → 0S  δ(B, 0) = S
B → 1A  δ(B, 1) = A
B→1  δ(B, 1) = Final State

0
ε
0 1
ε 1
S A B
0 1
C
* State C is a new final State
Step 5: Reconstructed Finite Automata (after removing state C)

0,1
ε
0 1
ε 1
S A B
10 / 35
Unit – III
Tutorial Questions:

A→ bS / b
B → aS
C→ε

A → aB
B → aB/bB/ε
5. Give the Finite Automata from the given Right Linear Grammar
S → 0S/1A/1/0B/0
A → 0A/1B/0/1
B → 0B/1A/0/1
 Conversion of Finite Automata to Left Linear Regular Grammar

Algorithm:
1. Take reverse of the finite automata
2. Remove unreachable state.
3. Then write right linear grammar using the following steps
i. Repeat the process for every state.
ii. Begin the process from start state.
iii. Write the production as the output followed by the state on which
the transition is going.
iv. And at the last add ε because that’s required to end the derivation.
4. Then take reverse of the right linear grammar
5. And you will get the final left linear grammar
 Problems for Finite Automata to Left Linear Regular Grammar:
1. Construct Left Linear Grammar from the given Finite Automata
1) Take reverse of the finite automata (make final state as initial state and vice-
versa) a,b
a
qA2 B
2) Remove unreachable state.

There is no unreachable state
11 / 35
Unit – III
3) Then write right linear grammar

a. Pick start state and output is on symbol 'a' we are going on state A and
B. So, we will write as :
B → aA / aB
b. Pick start state and output is on symbol 'b' we are going on state B. So,
we will write as :
B → bB
c. Then we will pick state A and then we will go for each output.
A→ ε
d. So, final we got right linear grammar as:
B→ aA / aB / bB
A→ε
4) Then take reverse of the right linear grammar
B→ Aa / Ba / Bb
A→ε
5) Final left linear grammar
B→ Aa / Ba / Bb
A→ε
1) Take reverse of the finite automata (make final state as initial state and vice-
versa)
2) Remove unreachable state.

State C is unreachable state, So remove state from the above FA
12 / 35
Unit – III
3) Then write right linear grammar

a. Pick start state and output is on symbol 'a' we are going on state A and
B. So, we will write as :
B → aA / aB
b. Pick start state and output is on symbol 'b' we are going on state B. So,
we will write as :
B → bB
c. Then we will pick state A and then we will go for each output.
A→ ε
d. So, final we got right linear grammar as:
B→ aA / aB / bB
A→ε
4) Then take reverse of the right linear grammar
B→ Aa / Ba / Bb
A→ε
5) Final left linear grammar
B→ Aa / Ba / Bb
A→ε
Tutorial Questions:
1 0
0 1
S A qB2
0
1
a, b
a, b
b a a, b
q0 q1 qq22
13 / 35
Unit – III
 Conversion of Left Linear Regular Grammar to Finite Automata

Algorithm:
Given a regular grammar G, a finite automata accepting L(G) can be obtained as
follows:
1. Take reverse of CFG
2. The number of states in the automata will be equal to the number of non-
terminals plus one. Each state in automata represents each non-terminal in the
regular grammar. The additional state will be the final state of the automata.
The state corresponding to the start symbol of the grammar will be the initial
state of automata. If L(G) contains ϵ that is start symbol is grammar devices to
ϵ, then make start state also as final state.
3. The transitions for automata are obtained as follows:
 For every production A → aB, then make δ(A, a) = B that is make an
are labeled ‘a’ from A to B.
 For every production A → a, then make δ(A, a) = final state.
 For every production A → ϵ, then make δ(A, ϵ) = A and A will be final
state.
4. Then again take reverse of the FA and that will be our final output
5. Start State: It will be the first production's state
6. Final State: Take those states which end up with input alphabets.
 Problems for Finite Automata to Left Linear Regular Grammar
1. Construct a Finite Automata from the given Left Linear Grammar

A → Ba/Ab/b
B → Ca/Bb
C → Aa/Cb/a
Solution:
Step 1: Take reverse of CFG
A → aB/bA/b
B → aC/bB
C → aA/bC/a
A → aB  δ(A, a) = B
A → bA  δ(A, b) = A
A→ b  δ(A, b) = Final State
B → aC  δ(B, a) = C
B → bB  δ(B, b) = B
Step 4: Take the ‘C’ productions, then will make transition functions
C → aA  δ(C, a) = A
C → bC  δ(C, b) = C
C→b  δ(C, b) = Final State
14 / 35
Unit – III

a
b b b
a a
A B C
b a
D * State D is a new final State
Step 6: Again take reverse of the FA, this is final output.

a
b b b
a a
A B C
b a

S →A/B/ε
A → S0/B1/0
B → S0/A1/1
Solution:
Step 1: Take reverse of CFG
S→A/B/ε
A → 0S/1B/0
B → 0S/1A/1
Step 2: Take the ‘S’ productions, then will make transition functions
S→ A  δ(S, ε) = A
S→ B  δ(S, ε) = B
S→ ε  δ(S, ε) = S and S is make Final State
A → 0S  δ(A, 0) = S
A → 1B  δ(A, 1) = B
A→ 0  δ(A, 0) = Final State
B → 0S  δ(B, 0) = S
B → 1A  δ(B, 1) = A
B→ 1  δ(B, 1) = Final State
15 / 35
Unit – III

0
ε
0 1
ε 1
S A B
0 1
C * State C is a new final State
Step 6: Reconstructed Finite Automata (remove state C)

0,1
ε
0 1
ε 1
S A B
Step 7: Again take reverse of the FA, this is final output.

0,1
ε
0 1
ε 1
S A B
Tutorial Questions:
S → Aab / Aba / B / ε
A→ Sb / b
B → Sa
C→ε
A → Ba
B → Ba/Bb/ε
5. Give the Finite Automata from the given Left Linear Grammar
S → S0/A1/1/B0/0
A → A0/B1/0/1
B → B0/A1/0/1
16 / 35
Unit – III
Context free Grammars

 Motivation and introduction
 A Context Free Grammar is a “machine” that creates a language.
 A language created by a CF grammar is called A Context Free Language.
 The class of Context Free Languages Properly Contains the class of Regular
Languages.
 Definition:
A Context Free Grammar is consists of four components. They are finite set of
non-terminals, finite set of terminals, set of productions and start symbol.
 Formal Definition of Context Free Grammars (CFG)

 A CFG is a mathematical object, G, with four components,
G = (N, T, P, S)
Where
N is a nonempty, finite set of non-terminal symbols
T is a finite set of terminal symbols
P is a set of grammar rules, each of one having one of the forms
A→α
Where A  N and α  (N  T)*
S is the start symbol S ∈ N
 Example
Let G = ({S},{0,1,},P,S) be a CFG, where productions are S→ 0S0/1S1/

 Context Free Language: The Language Generated by a Regular Grammar
 Let G = (N, T, P, S) be a regular grammar. We define the language generated by
G to be L(G).
∗
 L(G) = {w | w can be derived from G (or) S ⇒ w, where w T*}
 Conversion of Context Free Language (CFL) into Context Free Grammar (CFG)
1. Construct a CFG representing the set of palindromes over (0+1)*.

The possible strings are
{,0,1,00,11,000,111,010,101,0000,1111,00100,11011, 01110,10101,....}
The CFG for a palindrome is given by
S → 0 / 1 / 
S → 0S0 / 1S1
2. Construct a CFG for the language L = {𝑎 ; n is odd}. The

possible strings are {, a, aaa, aaaaa, aaaaaaa, ........... }
The productions are
G: S → a / aaS
3. Construct a CFG for the language L = { ; n ≥ 0}.

The possible strings are {, ab, aabb, aaabbb, aaaabbbb, .... }
The productions are
G: S → ab / aSb / 
17 / 35
Unit – III
4. Construct a CFG for the language L = {0n1n ; n ≥ 1}.

The possible strings are {01, 0011, 000111, 00001111, .... }
The productions are
G: S → 01 / 0S1
5. Construct a CFG for the language L = {ancbn ; n ≥ 0}.

The possible strings are {c, acb, aacbb, aaacbbb, aaaacbbbb, .... }
The productions are
G: S → c / aSb
6. Construct a CFG for the language L = {wcwr ; w  (a+b)*}.

The possible strings are {c, aca, bcb, abcba, aacaa, bbcbb, bacab, abacaba,
bbacabba,….}
The productions are
G: S → aSa / bSb / c
7. Construct a CFG for the language L = {𝑎𝑎(𝑏𝑏a)nbab(aab)n ; n ≥ 0}.

The possible strings are {aabbab, aabbbababaab, aabbbabbababaabaab,….}
The productions are
G: S → ABCD
A → aab
B → bba / bbaB
C → bab
D → aab / aabD
Tutorial Questions:
8. Construct a CFG for the language L = {anbcm ; n, m ≥ 0}.
9. Construct a CFG for the language L = {0n1011n ; n ≥ 1}.
10. Construct a CFG for the language L = {1n0m ; n ≥ 0, m = n+2}.
 Conversion of Context Free Grammar (CFG) into Context Free Language (CFL)
1. Construct a CFL from the given grammar
G = ({S}, {0,1, } , P, S)
Where
S → 0 / 1 / 
S → 0S0 / 1S1
Solution:
If String Length = 1, The Strings are , 0, 1
If String Length = 2, The Strings are 00, 11
If String Length = 3, The Strings are 000, 111, 010, 101
If String Length = 4, The Strings are 0000,1111
If String Length = 5, The Strings are 00000,11111, 01010, 10101,
11011, 00100, 01110, 10001
.....
If String Length > 5, The Strings are 0000 … .001111 … 11
So, The CFL is
L = { w; All strings are palindrome over {0,1}}
18 / 35
Unit – III

G = ({S}, {0,1, } , P, S)
Where
S → a / aaS
Solution:
If String Length = 1, The String is a
If String Length = 2, The String is aaa
If String Length = 3, The String is aaaaa
If String Length = 4, The String is aaaaaaa
.....
If String Length > n, The String is aaa ..... aaaa, n is odd
So, The CFL is
L = {an ; n is odd}.

G = ({S}, {a, b, c} , P, S)
Where
S → aSa / bSb / c
Solution:
If String Length = 1, The String is c
If String Length = 3, The Strings are aca, bcb
If String Length = 5, The Strings are aacaa, bbcbb, abcba, bacab
.....
If String Length > n, The Strings are aaa...c...aaa, bb...c...bb,
aba..c..aba, bba....c...bba, ...
So, The CFL is
L = {wcwr ; w  (a+b)*}.
Tutorial Questions:
4. Construct a the CFL from the following grammar

S → c / aSb
5. Construct a the CFL from the following grammar

S → ABCD
A → aab
B → bba / bbaB
C → bab
D → aab / aabD
6. Construct a the CFL from the grammar G = ({S},{a,b},P,S)}, with productions

S → aSa,
S → bSb,
S→ε
19 / 35
Unit – III
Derivations
 A derivation of a string for a grammar is a sequence of grammar rule applications that
transform the start symbol into the string. A derivation proves that the string belongs
∗
to the grammar's language. ie. S ⇒ w, where w T* and w  L(G)
 A derivation is fully determined by giving, for each step:
o The rule applied in that step
o The occurrence of its left-hand side to which it is applied
 Example
Consider G whose productions are S → aAS / a, A→ SbA / SS / ba,
show that S ⇒ aabbaa.
Solution:
S ⇒ aAs
⇒ aSbAs [A → SbA]
⇒ aabAS [S → a]
⇒ aabbaS [A → ba]
⇒ aabbaa [S → a]
∗
S ⇒ aabbaa
Leftmost derivation (LMD)

 A leftmost derivation is obtained by applying production to the leftmost variable or
non-terminal in each step.
∗
ie. S ⇒ w, where w T* and w  L(G)
𝑙𝑚
 Problems for LMD

1. Consider G whose productions are S → aAS / a, A→ SbA / SS / ba,
Show that S ⇒ aabbaa.
Solution:
S ⇒ aAS
⇒ aSbAS [A→ SbA]
⇒ aabAS [S→ a]
⇒ aabbaS [A→ ba]
⇒ aabbaa [S→ a]
∗
S ⇒ aabbaa
𝑙𝑚
20 / 35
Unit – III
2. Find a left most derivation for “aaabbabbba” with the productions.

P : S → aB / bA, A → a /S / bAA, B → b / bS / aBB
Solution:
S ⇒ aB
⇒ aaBB [B→ aBB]
⇒ aaaBBB [B→ aBB]
⇒ aaabBB [B→ b]
⇒ aaabbB [B→ b]
⇒ aaabbaBB [B→ aBB]
⇒ aaabbabB [B→ b]
⇒ aaabbabbS [B→ bS]
⇒ aaabbabbbA [S→ bA]
⇒ aaabbabbba [A→ a]
∗
S ⇒ aaabbabbba
𝑙𝑚
Rightmost derivation
 A rightmost derivation is obtained by applying production to the rightmost variable or
non-terminal in each step.
∗
ie. S ⇒ w, where w T* and w  L(G)
𝑟𝑚
 Problems for RMD

1. Consider G whose productions are S → aAS / a, A→ SbA / SS / ba,
Show that S ⇒ aabbaa.
Solution:
S ⇒ aAS
⇒ aAa [S→ a]
⇒ aSbAa [S→ SbA]
⇒ aSbbaa [A→ ba]
⇒ aabbaa [S→ a]
∗
S ⇒ aabbaa
𝑟𝑚
21 / 35
Unit – III
2. Find a right most derivation for “aaabbabbba” with the productions.

P : S → aB / bA, A → a /S / bAA, B → b / bS / aBB
Solution:
S ⇒ aB
⇒ aaBB [B→ aBB]
⇒ aaBbS [B→ bS]
⇒ aaBbbA [S→ bA]
⇒ aaBbba [A→ a]
⇒ aaaBBbba [B→ aBB]
⇒ aaaBbbba [B→ b]
⇒ aaabSbbba [B→ bS]
⇒ aaabbAbbba [S→ bA]
⇒ aaabbabbba [A→ a]
∗
S ⇒ aaabbabbba
𝑟𝑚
 Sentential Form or Partial Derivation

o A partial derivation is a part of a derivation. The strings are derived from the
start symbol is called as Sentential form.
o If G =(V,T,P,S) is a CFG, then α (V  T)*
∗
S ⇒ α, where α (V  T)* - Sentential Form
𝐺
∗
S ⇒ α, where α (V  T)* - Left Sentential Form
𝑙𝑚
∗
S ⇒ α, where α (V  T)* - Right Sentential Form
𝑟𝑚
Derivation Tree or Parse Tree - (Pictorial representation of derivation)

 A derivation tree or parse tree is an ordered rooted tree that graphically represents the
semantic information a string derived from a context-free grammar.
 Representation Technique
o Root vertex − Must be labelled by the start symbol.
o Vertex − Labelled by a non-terminal symbol.
o Leaves − Labelled by a terminal symbol or ε.
A B a
a 
22 / 35
Unit – III
 Types of Derivation Tree

o Leftmost derivation tree
 A leftmost derivation tree is obtained by applying production to the
leftmost vertex in each step.
 Example: S → ABa, A → a, B → 


 S
 S S


A B a A B a A B a
...
a a a 

o Rightmost derivation tree

 A rightmost derivation tree is obtained by applying production to the
rightmost vertex in each step.
 Example: S → ABa, A → a, B → 


 S

S S


...
A B a A B a A B a
a 
 a 
23 / 35
Unit – III
Ambiguity
 If a context free grammar G has more than one derivation tree (leftmost or rightmost
derivation tree) for some string wL(G), it is called an ambiguous grammar. There
exist multiple right-most or left-most derivations for some string generated from that
grammar.
 Problems for Ambiguity in Context-Free Grammars

1. Check whether the grammar G with production rules S → S+S / S*S / S / a is
ambiguous or not.
Solution:
Let’s assume a string w = a+a*a
Parse Tree 1 : Parse Tree 2 :
S
S
S + S
S * S
a S * S
S + S a
a a
a a
Thus we have two parse trees, So the given grammar is ambiguous.

2. Check whether the grammar G with production rules S → E+E / E*E / (E) / id is
ambiguous or not.
Solution:
Let’s assume a string w = (id*id+id)
Parse Tree 1 : Parse Tree 2 :
E E
( E ) ( E )
E * E E + E
id E + E E * E id
id id id id
Thus we have two parse trees, so the given grammar is ambiguous.
24 / 35
Unit – III
Tutorial Questions:
1. Show that the grammar defined by the productions

S → SS / a /b is ambiguous.
2. If G is the grammar S → SbS / a, Show that G is ambiguous.
3. Prove that the grammar defined by the productions

S → A1B, A → 0A / , B → 0B / 1B /  is unambiguous.
4. Let the production of the grammar be S → 0B / 1A, A → 0 / 0S / 1AA,

B → 1 / 1S / 0BB and the string 0110.
a. Find the left most derivation and associated derivation tree.
b. Find the right most derivation and associated derivation tree.
c. Find the G is ambiguous or not.
d. Find a L(G).
5. G denotes the context-free grammar defined by the following rules.

S→ASB / ab / SS
A→aA / A
B→bB / A
a. Give a left most derivation of “aaabb” in G. Draw the associated parse
tree.
b. Give a right most derivation of “aaabb” in G. Draw the associated parse
tree.
c. Show that G is ambiguous.
d. Find a L(G).
Simplification of CFG’s
 In a CFG, it may happen that all the production rules and symbols are not needed for
the derivation of strings. Besides, there may be some null productions, useless
symbols and unit productions. Elimination of these productions and symbols is
called simplification of CFGs.
 Simplification essentially comprises of the following steps
o Elimination of Useless Symbols or Productions
o Elimination of Null Productions (ie. )
o Elimination of Unit Productions
25 / 35
Unit – III
 Elimination of Useless Symbols or Productions

o The productions that can never take part in derivation of any string are called
useless productions. Similarly, a symbol that can never take part in derivation
of any string is called a useless symbol or variable.
o Example
1. Eliminate the useless symbols or productions from the given grammar
G: S → abS / abA / abB
A → cd
B → aB
C → dc
Solution:
Step 1:
The production ‘B →aB’ is useless because there is no way it
will ever terminate. If it never terminates, then it can never
produce a string, then remove all the productions in which
variable ‘B’ occurs.
After eliminating B production and B symbols:
G1: S → abS / abA
A → cd
C → dc
Step 2:
The production ‘C → dc’ is useless because the variable ‘C’
will never occur in derivation of any string, then remove all the
productions in which variable ‘C’ occurs.
After eliminating C production:
G2: S → abS / abA
A → cd
Step 3: Resultant Grammar
G’: S → abS / abA
A → cd
Tutorial Questions:
S → AC / B, A → a, C → c / BC, E → aA / 
3. Remove the useless symbol from the given context free grammar:
S → aB / bX
A → Bad / bSX / a
B → aSB / bBX
X → SBD / aBx / ad
26 / 35
Unit – III
 Elimination of Null Productions (ie. )

o The productions A →  are called  productions (also null productions). These
productions can only be removed from those grammars that do not generate 
(an empty string).
o To remove null productions, we first have to find all the nullable variables. A
variable A is called nullable if  can be derived from A.
 For all the productions A→  , A is a nullable variable.
 For all the productions of type B → A1A2…An, where all ’Ai’s are
nullable variables, B is also a nullable variable.
o If all the variables on the RHS of the production are nullable , then we do not
add A →  to the new grammar.
o Example:
1. Eliminate the  productions from the given grammar

G: S → ABCd
A → BC
B → bB / 
C → cC / 

Solution:
Step 1: Remove the productions B→ and C→
G: S → ABCd / ACd / ABd / Ad
A → BC / C / B / 
B → bB / b
C → cC / c
Step 2: Remove the production A→
G: S → ABCd / ACd / ABd / Ad / BCd / Cd / Bd / d
A → BC / C / B
B → bB / b
C → cC / c
G’: S → ABCd / ACd / ABd / Ad / BCd / Cd / Bd / d
A → BC / C / B
B → bB / b
C → cC / c
27 / 35
Unit – III
Tutorial Questions:
2. Eliminate the  productions from the given grammar
S → ABAC
A → aA / 
B → bB / 
C→c
3. Remove the  productions from the given grammar
S → ASA / aB / b, A → B, B → b / 

 Elimination of Unit Productions
o Any production rules in the form A → B where A, B ∈ Non-terminal is
called unit production.
o Steps for eliminate unit productions:
 Step 1: To remove A → B, add production A → x to the grammar rule
whenever B → x occurs in the grammar. [x ∈ Terminal, x can be Null]
 Step 2: Delete A → B from the grammar.
 Step 3: Repeat from step 1 until all unit productions are removed.
o Example
1. Eliminate the unit production from the given grammar
G: S → Aa / B
A →b / B
B→A/a
Solution:
Step 1: Remove the production B→ A
G: S → Aa / B
A →b / A / a
B→A/a
Step 2: Remove the production A→A
G: S → Aa / B
A →b / a
B→A/a
Step 3: Remove the production B→A
G: S → Aa / B
A→b/a
B→b/a
28 / 35
Unit – III
Step 4: Remove the production S→B

G: S → Aa / b / a
A→b/a
B→b/a
G’: S → Aa / b / a
A→b/a
B→b/a
Tutorial Questions:

S → XY, X → a, Y → Z / b, Z → M, M → N, N → a
3. Remove the useless symbol from the given context free grammar:
S → AB
A→ a
B→ C/b
C→ D
D→E
E→ a
4. Consider the grammar

S→ 0A0 / 1B1 / BB
A→ C
B→ S / A
C→ S / ε and simplify using the same order
a. Eliminate ε-Productions
b. Eliminate unit productions
c. Eliminate useless symbols
Normal Form
 A CFG is convert into a specific form is called as Normal forms.
 There are two types of Normal Norms.
o Chomsky Normal Form (CNF)
o Greibach Normal Form (GNF)
29 / 35
Unit – III
Chomsky Normal Form (CNF)

 A CFG is said to be in Chomsky Normal Form if every production is of one of these
two forms:
1. Non-Terminal → Non-Terminal . Non-Terminal
Example: A → BC where A,B,CV (right side is two Non-Terminal).
2. Non-Terminal → Terminal
Example: A → a where a  T (right side is a single Terminal).
 Algorithms for converting CFG into CNF:
Step 1: Eliminate Null productions.
Step 2: Eliminate Unit productions.
Step 3: Eliminate Useless Symbols or Productions.
Step 4: Replace each production A → B1…Bn where n > 2 with A → B1C.
Where C → B2 …Bn. Repeat this step for all productions having more than
two non-terminals in the right side.
Step 5: If the right side of any production is in the form A → aB where a is a terminal
and A, B are non-terminal, then the production is replaced by A → XB and
X → a. Repeat this step for every production which is in the form A → aB.
 Problems for converting CGF into CNF:

1. Consider the Grammar G = ({S,A,B},{a,b}, P, S} as the productions
S → bA / aB
A → bAA / aS / a
B → aBB / bS / b.
Convert it into CNF.
Solution:
Step 1: Eliminate Null productions.
There is no Null production.
There is no Unit production.
There is no Useless Symbols or Productions.
Step 4: Find the productions which are already in CNF.
A→a
B→b
Step 5: Replace all remaining productions into CNF.
Non-Terminal → Non-Terminal . Non-Terminal
Non-Terminal → Terminal
i) S → bA
S → CbA
Cb → b
30 / 35
Unit – III
ii) S → aB
S → CaB
Ca → a
iii) A → bAA
A → CbD1
D1 → AA
Cb → b
iv) A → aS
A → CaS
Ca → a
v) B → aBB
B → Ca D2
D2 → BB
Ca → a
v) B → bS
B → CbS
Cb → b
Step 3: Final Resultant Grammar

G: S → CbA / CaB
A → CbD1 / CaS / a
B → Ca D2 / CbS / b
D1 → AA
D2 → BB
Ca → a
Cb → b
2. Convert the given grammar into CNF.

G = ({S,A,B},{a,b}, P, S}
The Productions are
S→ 0A0 / 1B1 / BB
A→ C
B→ S / A
C→ S / ε.
Solution:
Step 1: Eliminate ε-Productions
1.1 Remove the production C→ ε
S→ 0A0 / 1B1 / BB
A→ S / ε
B→ S / A
C→ S
1.2 Remove the production A→ ε
S→ 0A0 / 00 / 1B1 / BB
A→ S
B→ S / ε
C→ S
31 / 35
Unit – III
1.3 Remove the production B→ ε

S→ 0A0 / 00 / 1B1 / 11 / BB / B
A→ S
B→ S
C→ S

2.1 Remove the production C→ S
S→ 0A0 / 00 / 1B1 / 11 / BB / B
A→ S
B→ S
2.2 Remove the production B→ S
S→ 0A0 / 00 / 1S1 / 11 / SS / S
A→ S
2.3 Remove the production A→ S
S→ 0S0 / 00 / 1S1 / 11 / SS / S
2.4 Remove the production S→ S
S→ 0S0 / 00 / 1S1 / 11 / SS
Step 3: Eliminate useless symbols

Resultant Grammar (after simplifications)
G’ : S→ 0S0 / 00 / 1S1 / 11 / SS
Step 4: Find the productions which are already in CNF.
S→ SS
Step 5: Replace all productions into CNF.

Non-Terminal → Non-Terminal . Non-Terminal
Non-Terminal → Terminal
i) S→ 0S0
S → AB
B→ SA
A→ 0
ii) S→ 00
S → AA
A→0
iii) S→ 1S1
S → DC
C → SD
D→1
iv) S→ 11
S → DD
D→1
32 / 35
Unit – III

G’: S → AB / AA / DC / DD
B→ SA
A→ 0
C → SD
D→1
Tutorial Questions:
3. Convert the following CFG to CNF
S → ASA / aB
A→ B/S
B→b/ε
4. Convert the following CFG to CNF
S → AB / Aa
A→ aAA / a
B→ bBB / b
5. Find a grammar in Chomsky Normal form equivalent to
S→aAD
A→aB / bAB
B→b
D→d
6. Consider G = ({S,A}, {a,b}, P, S} where P consists of
S→aAS / a
A→ SbA / SS / ba
Convert it to its equivalent CNF
Greibach Normal Form (GNF)

 A CFG is said to be in Greibach Normal Form if every production is of one of these
two forms:
1. Non-Terminal → Terminal . Any no. of Non-Terminal
Example: A → aBC or
2. Non-Terminal → Terminal
Example: A → a (right side is a single Terminal).
(Or)
A → aα , where aT and αV*
 Algorithms for converting CFG into GNF:

Step 1: Eliminate Null productions.
Step 4: Check whether the CFG is already in CNF and convert it to CNF if it is not.
33 / 35
Unit – III
Step 5: Rename the variables like A1, A2, ...An starting with S = A1. (Ai in ascending
order of i)
Step 6: No need to modify the productions like Ai → Aj where i < j
Step 7: Modify the productions like Ai → Aj where i ≥ j
(a) If Ai → Aj  where i > j, then substitute for Aj productions.
Suppose Aj → Ak / AL, then the new set of productions are
Ai → Ak  / AL
(b) It Ai → Aj  where i = j, then do the following steps:
Introduce a new variable Bi
Then
Bi → Ak
Bi →  Bi
and remove the production Ai → Aj 
(c) For each production Ai →  where  does not begin with Ai , then add the
production
Ai →  Bi
Step 7: Convert all the productions into GNF form. A → aα where aT and αV*
 Problems for converting CFG into GNF:

1. Consider the Grammar G = ({S,A,B},{a,b}, P, S} as the productions
S → AB
A → BS / b
B → SA / a
Convert it into CNF.
Solution:
Step 1: Eliminate Null productions.
There is no Null production.
There is no Useless Symbols or Productions.
Step 4: All production rules are already in CNF form.
Step 5: Rename the variables S, A, B as A1, A2, A3 respectively.
A1 → A2 A3 -------------------------- (1)
A2 → A3 A1 / b ---------------------- (2)
A3 → A1 A2 / a----------------------- (3)
In (1), i < j, no need to modify the production.

In (2), i < j, no need to modify the production.
In (3), i > j, substitute A1 productions in (3)
A3 → A2 A3 A2 / a -------------------- (4)
In (4), i > j, substitute A2 productions in (4)

A3 → A3 A1 A3 A2 / b A3 A2 / a (5)
34 / 35
Unit – III
In (5), i = j, introduce new non-terminal B3, then B3 productions are

B3 → A1 A3 A2 / A1 A3 A2 B3 and
A3 → b A3 A2 / a has been modified to
A3 → b A3 A2 / a / b A3 A2 B3 / a B3
Step 6: Resultant productions are

A1 → A2 A3 ------------------------------------- (1)
A2 → A3 A1 / b --------------------------------- (2)
B3 → A1 A3 A2 / A1 A3 A2 B3 ----------------- (3)
A3 → b A3 A2 / a / b A3 A2 B3 / a B3 --------- (4)
Step 7: Convert into GNF form
Non-Terminal = Terminal .any no. of Non-Terminals
Non-Terminal = Terminal
Substitute A2 in (1)
A1 → A3 A1 A3 / b A3 -------------------------- (5)
A1 → b A3 A2 A1 A3 / a A1 A3 / b A3 A2 B3 A1 A3 /
a B3 A1 A3 / b A3
A2 → b A3 A2 A3 A1 / a A3 A1/ b A3 A2 B3 A3 A1 /
a B3 A3 A1 / b
B3 → b A3 A2 A3 A2 / a A3 A2 / b A3 A2 B3 A3 A2 / a B3 A3 A2 /
b A3 A2 A3 A2 B3 / a A3 A2 B3 / b A3 A2 B3 A3 A2 B3 /
a A3 A2 B3B3
Step 8: The equivalent GNF productions are

A1 → b A3 A2 A1 A3 / a A1 A3 / b A3 A2 B3 A1 A3 / a B3 A1 A3 / b A3
A2 → b A3 A2 A3 A1 / a A3 A1/ b A3 A2 B3 A3 A1 / a B3 A3 A1 / b
A3 → b A3 A2 / a / b A3 A2 B3 / a B3
B3 → b A3 A2 A3 A2 / a A3 A2 / b A3 A2 B3 A3 A2 / a B3 A3 A2
B3 → b A3 A2 A3 A2 B3 / a A3 A2 B3 / b A3 A2 B3 A3 A2 B3
B3 → a A3 A2 B3B3
Tutorial Questions:
2. Convert the following CFG to GNF
S → AA / a
A → SS / b
(or)
Convert the following CFG to GNF
A1 → A2 A2 / a
A2→ A1A1 / b
S → AB / Aa
A→ aAA / a
B→ bBB / b
S → ABA A→ aA /  B→ bB / 
35 / 35
Unit – IV



Definition for Push Down Automata

 Formal Definition of Pushdown Automaton
A pushdown automaton consists of seven tuple
M = (Q, Σ, Γ, δ, q0, Z0, F),
Where
Q - Finite set of states
Σ - Finite input alphabet
Γ - Finite alphabet of pushdown symbols
δ - Transition function Q × (Σ 𝖴 {ε}) × Γ → Q×Γ
q0 - start / initial state q0  Q
Z0 - start symbol on the pushdown Z0  Γ
F - set of final states F  Q
Model of PDA
 Pushdown Automata is a finite automaton with extra memory called stack which helps
Pushdown automata to recognize Context Free Languages.
 A DFA can remember a finite amount of information, but a PDA can remember an
infinite amount of information.
 The PDA consists of a finite set of states, a finite set of input symbols and a finite set of
push down symbols.
 The finite control has control of both the input tape and the push down store.
 The stack head scans the top symbol of the stack.
 A pushdown automaton has three components:
o input tape
o control unit, and
o stack with infinite size.
 A stack does two operations:
o Push − a new symbol is added at the top.
o Pop − the top symbol is read and removed.
1 / 20
Unit – IV
Acceptance by PDA
 There are two different ways to Acceptance by PDA
o Acceptance by Final State
 In final state acceptability, a PDA accepts a string when, after reading the
entire string, the PDA is in a final state. From the starting state, we can
make moves that end up in a final state with any stack values. The stack
values are irrelevant as long as we end up in a final state.
 Let M = (Q, ∑, Γ, δ, q0, Z0, F) be a PDA, then the language accepted by
the set of final states F is
L(M) = {w ; (q0, w, z0) ⊢* (p, ε, ), p ∈ F,  ∈ ⊢*}
o Acceptance by Empty Stack
 In empty stack acceptability, a PDA accepts a string when, after reading
the entire string and also stack is empty, the PDA is in any state.
 Let M = (Q, ∑, Γ, δ, q0, Z0, {q}) be a PDA, then the language accepted by
the empty stack is:
N(M) = {w ; (q0, w, z0) ⊢* (q, ε, ε), q ∈ Q}
Instantaneous Description (ID)

 The ID must record the state and stack contains
If M = (Q, ∑, Γ, δ, q0, Z0, F) be a PDA
then
(q0, aw, zα) ⊢ (q0, w, α) if (q, a, z) = (p, )
Equivalence of Acceptance of PDA from Empty Stack to Final state

If L is N(M1) (the language accepted by empty stack) for some PDA M1, then L is L(M2)
(language accepted by final state) for some PDA M2 i.e. L = N(M1) = L(M2)
(or)
Prove that if L=N(PN) for some PDA PN = (Q, Ʃ, Г, δ, q0, Z0, F), then there is a PDA PF such
that L=L(PF).
(or)
If L is L(M2) for some PDA M2 then N(M1)=L(M2),L is N(M1) for some PDA M1.
Theorem:
If M1 = (Q, Ʃ, Г, δ, q0, Z0, ∅) is a PDA accepting L by empty store, then construct a
PDA M2 = (Q’, Ʃ’, Г’, δ’, q0’, Z0’, F) which accepts L by final state i.e., L = N(M1) =
L(M2).
Proof:
M2 is constructed in such a way that
a) by the initial state moves M2 of , it reaches an initial id of M1
b) by the final move of B, it reaches its final state.
c) all intermediate moves of B are in A.
2 / 20
Unit – IV
ɛ, Z0’ / ɛ
ɛ, Z0’ / ɛ
ɛ, Z0’ / ɛ
p0 q0 M1 pf
ɛ, Z0’ / Z0Z0’ ɛ, Z0’ / ɛ
ɛ, Z0’ / ɛ
Let us define M2 as follows
M2 = (Q’, Ʃ’, Г’, δ’, q0’, Z0’, F)
Where
Q’= Q 𝖴 {p0, pf}
Ʃ’ = Ʃ
= Г {Z0’}
F’ = {pf} - New final state (not in Q)
q0’ = p0 - New start state
Z0’ = New start symbol for stack.
δ' is given by rules:
R1 : δ’(p0, ɛ, Z0’) = {(q0, Z0Z0’)}
R2: δ’(q, a, Z) = δ(q, a, Z) for all q in Q, a in (Ʃ 𝖴 ɛ) and Z in .
R3: δ’ (q, ɛ, Z0’) = {(pf, ɛ)}.
 By Rule R1, the PDA M2 moves from initial ID of M2 to an initial ID of M1.
R1 gives a ‘ɛ’ move. As a result of R1, M2 moves to the initial state of A with
the start symbol z0 on top of the stack.
 By Rule R2 is used to simulate M1. Once M2 reaches an initial ID of M1, R2 is
used to simulate moves of M1. We can repeatedly apply R2 until Z0’ is pushed
to the top of the stack.
 By Rule R3 is also a ‘ɛ’ move. Using R3, M2 moves to new final state pf by
erasing Z0’ in stack.
We have to show N(M1) = L(M2).

Let w ϵ N(M1) then by definition of N(M1),
M1 : (q0, w, Z0) ⊢* (q, ɛ, ɛ) for some q  Q
By theorem
(q, x, α) ⊢* (p, y, β)  (q, xw, αy) ⊢* (p, yw, βγ)
we get
M1 : (q0, w, Z0Z0’) ⊢* (q, ɛ, Z0’)
Since empty store (δ) is a subset of δ’ i.e. δ⊂ δ’
we have
M2 : (q0, w, Z0Z0’) ⊢* (q, ɛ, Z0’)
Therefore we conclude that
M2 : (p0, w, z0’) ⊢ (q0, w, zz0’)
⊢* (q, ɛ, z0’)
⊢ (pf, ɛ, ɛ)
3 / 20
Unit – IV
Equivalence of Acceptance of PDA from final state to empty stack

If L is N(M1) for some PDA M1,then L if L(M2) for some PDA M2.
(or)
If A= (Q, Ʃ, Г, δ, q0, Z0, F) accept by final state, we can find a PDA B, accepting L by
empty store i.e., L = T(A) = N(B).
If M1 = (Q, Ʃ, Г, δ, q0, Z0, F) accept by final state, we can find a PDA M2, accepting L
by empty store i.e., L = L(M1) = N(M2).
Theorem:
If M1 = (Q, Ʃ, Г, δ, q0, Z0, F) is a PDA accepting L by final state, then construct a
PDA M2 = (Q’, Ʃ’, Г’, δ’, q0’, Z0’, ) which accepts L by empty store.
i.e., L = L(M1) = N(M2).
Proof:
M2 is constructs from M1 in such a way that
a) by the initial move of M2 as initial ID of M1 is reached.
b) once M2 reaches an initial ID of M1, it behaves like M1 until a final state of M1
is reached.
c) when M2 reaches final state of M1, it checks whether the input string is
exhausted. Then M2 simulates M1 or it erases all the symbols in stack.
qf
ɛ, Z0’ / ɛ
p0 q0 M1
qf
ɛ, Z0’ / Z0Z0’ ɛ, Z0’ / ɛ
Let us define M2 as follows

M2 = (Q’, Ʃ’, Г’, δ’, q0’, Z0’, )
Where
Q’= Q 𝖴 {p0, p}
Ʃ’ = Ʃ
= Г {Z0’}
F’ = {p} - New final state (not in Q)
q0’ = p0 - New start state
Z0’ = New start symbol for stack.
δ' is given by rules:
R1 : δ’(p0, ɛ, Z0’) = {(q0, Z0Z0’)}
R2 : δ’(q0, ɛ, Z) = {(qf, ɛ)} for all Z  Г 𝖴 {Z0’}.
R3 : δ’(q, a, Z) = δ(q, a, Z) for all a  Z, q  Q, Z  Г.
R4 : δ’(q, ɛ, Z) = δ(q, ɛ, z) 𝖴 {(p, ɛ )} for all Z  Г 𝖴 {Z0’} and q  F.
4 / 20
Unit – IV
 Using R1, M2 enters an initial ID of M1 and start symbol Z0 is placed on top of

stack.
 R2 is a ɛ move, using this M2 erases all the symbols on stack.
 R3 is used to make M2 simulate M1 until it reaches the final state of M1.
We have to show that L(M1) = N(M2)

Let w  L(M1) then
M1: (q0, w, z0) ⊢* (q, ɛ, α) for some q F, α  ˫*
Since δ’ ⊆ δ and by theorem
M1: (q, x, α) ⊢* (p, y, β)  (q, xw, αy) ⊢* (p, yw, βγ)
We can write has
M2: (q0, w, Z0Z0’) ⊢* (q, ɛ, αz0’)
Then M2 can be computed has
M2: (p0, w, Z0’) ⊢ (q0, w, ZZ0’)
⊢* (q, ɛ, Z0’)
⊢ (pf, ɛ, ɛ)
Design of PDA
1. Construct a PDA that accepts L = {an bn ; n ≥ 1} accepted by Final State.
Solution:
Let M = (Q, ∑, Γ, δ, q0, Z0, F) be a PDA
The productions are:

1. (q0, a, z0) = {(q0, az0)} Push operations
2. (q0, a, a) = {(q0, aa)}
3. (q0, b, a) = {(q1, )} Pop operations

4. (q1, b, a) = {(q1, )}
5. (q1, , z0 ) = {(q2, z0)} - Accept the Final State
Transition Diagram:
a, z0 / az0
a, a / aa b, a / 
b, a /  , z0 / z0
q0 q1 qq22
5 / 20
Unit – IV
2. Construct a PDA that accepts L = {an bn ; n ≥ 1} accepted by empty stack.
Solution:

1. (q0, a, z0) = {(q0, az0)} Push operations
2. (q0, a, a) = {(q0, aa)}
3. (q0, b, a) = {(q1, )} Pop operations

4. (q1, b, a) = {(q1, )}
5. (q1, , z0 ) = {(q2, )} - Accept the empty stack
Transition Diagram:
a, z0 / az0
a, a / aa b, a / 

 b, a / 

, z0 / 
q0 q1 qq22




3. Construct a PDA that accepts L = {0n 1n ; n ≥ 0} accepted by Final State.
Solution:

1. (q0, 0, z0) = {(q0, 0z0)} Push operations
2. (q0, , z0) = {(q2, z0)}
3. (q0, 0, 0) = {(q0, 00)}
4. (q0, 1, 0) = {(q1, )} Pop operations

5. (q1, 1, 0) = {(q1, )}
Transition Diagram:
0, z0 / 0z0
0, 0 / 00 1, 0 / 
1, 0 /  , z0 / z0
q0 q1 qq22
, z0 / z0
6 / 20
Unit – IV
4. Construct a PDA that accepts L = {0n 1n ; n ≥ 0} accepted by empty stack.
Solution:

1. (q0, 0, z0) = {(q0, 0z0)} Push operations
2. (q0, , z0) = {(q2, )}
3. (q0, 0, 0) = {(q0, 00)}
4. (q0, 1, 0) = {(q1, )} Pop operations

5. (q1, 1, 0) = {(q1, )}
6. (q1, , z0 ) = {(q2, )} - Accept the empty stack
Transition Diagram:
0, z0 / 0z0
0,0 / 00 1, 0 / 

 1, 0 / 
 , z0 / 
q0 q1 qq22


 , z0 / 



5. Construct a PDA that accepts L = {wcwR ; w  (a+b)*} accepted by Final State.
Solution:

1. (q0, a, z0) = {(q0, az0)
2. (q0, b, z0) = {(q0, bz0)
3. (q0, a, a) = {(q0, aa) Push operations
4. (q0, b, b) = {(q0, bb)
5. (q0, a, b) = {(q0, ab)
6. (q0, b, a) = {(q0, ba)
7. (q0, c, a) = {(q1, a)} Accept the

8. (q0, c, b) = {(q1, b)} separator ‘c’
9. (q1, a, a) = {(q1, )}

Pop operations
10. (q1, b, b) = {(q1, )}
7 / 20
Unit – IV
Transition Diagram:
a, z0 / az0
b, z0 / bz0
a, a / aa
b, b / bb
a, b / ab a, a / 
b, a / ba b, b / 

c, a / a
c, b / b , z0 / z0
q0 q1 qq22
c, z0 / z0



6. Construct a PDA that accepts L = {wcwR ; w  (a+b)*} accepted by empty stack.
Solution:

1. (q0, a, z0) = {(q0, az0)
2. (q0, b, z0) = {(q0, bz0)
3. (q0, a, a) = {(q0, aa) Push operations
4. (q0, b, b) = {(q0, bb)
5. (q0, a, b) = {(q0, ab)
6. (q0, b, a) = {(q0, ba)
7. (q0, c, a) = {(q1, a)} Accept the

8. (q0, c, b) = {(q1, b)} separator ‘c’
9. (q1, a, a) = {(q1, )}

Pop operations
10. (q1, b, b) = {(q1, )}
11. (q1, ,  ) = {(q2, )} - Accept the empty stack
Transition Diagram:
a, z0 / az0
b, z0 / bz0
a, a / aa
b, b / bb
a, b / ab a, a / 
b, a / ba b, b / 
c, a / a
c, b / b , z0 / 
q0 q1 qq22
8 / 20
Unit – IV
7. Design a PDA that accepts L = {wwR ; w  (0+1)*} accepted by final state.

(or)
Design a PDA for even length palindrome.
Solution:

1. (q0, 0, z0) = {(q0, 0z0)
2. (q0, 1, z0) = {(q0, 1z0)
3. (q0, 0, 0) = {(q0, 00) Push operations
4. (q0, 1, 1) = {(q0, 11)
5. (q0, 0, 1) = {(q0, 01)
6. (q0, 1, 0) = {(q0, 10)
7. (q0, , 0) = {(q1, 0)} Accept the

8. (q0, , 1) = {(q1, 1)} separator ‘’
9. (q1, 0, 0) = {(q1, )}

Pop operations
10. (q1, 1, 1) = {(q1, )}
Transition Diagram:
0, z0 / 0z0
1, z0 / 1z0
0, 0 / 00
1, 1 / 11
0, 1 / 01 0, 0 / 
1, 0 / 10 1, 1 / 

, 0 / 0
, 1 / 1 , z0 / z0
q0 q1 qq22

8. Construct a PDA that accepts L = {a b a ; m, n ≥1} accepted by empty store.
n m n
Solution:
1. (q0, a, z0) = {(q0, az0)
2. (q0, a, a) = {(q0, aa)
3. (q0, b, a) = {(q1, a)
4. (q1, b, a) = {(q1, a)
5. (q1, a, a) = {(q2, )
6. (q2, a, a) = {(q2, )
7. (q2, , z0) = {(q2, )
9 / 20
Unit – IV
Transition Diagram:
a, z0 / az0
a, a / aa b, a / a a, a / 

, z0 / 
b, a / a a, a /  qq23
q0 q1 q2


9. Design a PDA that accepts L = {anbmcmdn; n, m ≥ 1} accepted by empty store and

check whether the string w = aaabcddd is accept or not.
Solution:

1. (q0, a, z0) = {(q0, az0)
2. (q0, a, a) = {(q0, aa)
3. (q0, b, a) = {(q1, ba)
4. (q0, b, b) = {(q1, bb)
5. (q0, c, b) = {(q1, )
6. (q1, c, b) = {(q1, )
7. (q1, d, a) = {(q2, )
8. (q2, d, a) = {(q2, )
9. (q2, , z0) = {(q3, )
Transition Diagram: 
a, z0 / az0 
a, a / aa 
b, a / ba
b, b / bb

c, b /  d, a / 

, z0 / 
c, b /  d, a / 
q0 q1 q2 qq23

String w = aaabcddd
(q0, aaabcddd, z0) ⊢ (q0, aabcddd, az0)
⊢ (q0, abcddd, aaz0)
⊢ (q0, bcddd, aaaz0)
⊢ (q0, cddd, baaaz0)
⊢ (q1, ddd, aaaz0)
⊢ (q2, dd, aaz0)
⊢ (q2, d, az0)
⊢ (q2, , z0)
⊢ (q3, , ) - Hence the string is accepted.
10 / 20
Unit – IV
Tutorial Problems:
10. Construct a PDA that accepts L = {anb2n ; n ≥1} accepted by empty stack.
11. Construct a PDA that accepts L = {anban ; n > 0} accepted by final state.
12. Design a PDA that accepts L = {anban ; n > 0} accepted by final state.
13. Construct a PDA that accepts L = {anbman ; n > 0 and m = n+1} accepted by empty
store.
14. Construct a PDA that accepts L = {anbm; n > 0 and m ≥ n} accepted by empty store.
15. Construct a PDA that accepts L = {anbmcm-n ; m, n ≥ 0 and m ≥ n} and check whether
the given string is accepted or not. (a) aabbbbcc (b) aabbc
Equivalence of PDA’s and CFL’s

i) Conversion of CFG to PDA
Theorem:
For any CFG L, there exists an PDA M such that L=L(M).
Proof:
Let G = (V, T, P, S) be a CFG.
Construct the PDA M that accepts L(G) by empty stack as follows:
M = ({q}, T, V 𝖴 T, δ, q, S)
Where transition function δ is defined by:
1. For each variable A, make δ(q, , A) = {(q, α) if A → α is a production
of P}.
2. For each terminal a, make δ(q, a, a) = {(q, )}.
 Problems for CFG to PDA
1. Construct a PDA from the following CFG.

G = ({S, A}, {a, b}, P, S) where the productions are
S → AS / ε
A → aAb / Sb / a
Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, A, S}, δ, q, S)
where δ:
δ(q, ε , S) = {(q, AS), (q, ε )}
δ(q, ε , A) = {(q, aAb), (q, Sb), (q, a)}
δ(q, a, a) = {(q, ε )}
δ(q, b, b) = {(q, ε )}
11 / 20
Unit – IV
2. Consider the grammar G = (V, T, P, S) with V = {S}, T = {a, b, c}, and P = {S →

aSa, S → bSb, S → c}
Solution:
Let the equivalent PDA, M = ({q}, {a, b, c}, {a, b, c, S}, δ, q, S)
where δ:
δ(q, ε , S) = {(q, aSa), (q, bSb ), (q, c )}
δ(q, a, a) = {(q, ε )}
δ(q, b, b) = {(q, ε )}
δ(q, c, c) = {(q, ε )}
3. Consider the grammar G = (VN, VT, P, S) with P = { S → abA / baA / B / ε

A→ bS / b, B → aS, C → ε}
Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, S, A, B, C}, δ, q, S)
where δ:
δ(q, ε , S) = {(q, abA), (q, baA ), (q, B ), (q, ε )}
δ(q, ε , A) = {(q, bS), (q, b)}
δ(q, ε , B) = {(q, aS)}
δ(q, ε , C) = {(q, ε )}
δ(q, a, a) = {(q, ε )}
δ(q, b, b) = {(q, ε )}
4. Consider the grammar G = (VN, VT, P, S)

Where P :
S→A/B/ε
A → 0S/1B/0
B → 0S/1A/1
Solution:
Let the equivalent PDA, M = ({q}, {0, 1}, {0, 1, S, A, B}, δ, q, S)
where δ:
δ(q, ε , S) = {(q, A), (q, B ), (q, ε )}
δ(q, ε , A) = {(q, 0S), (q, 1B), (q, 0)}
δ(q, ε , B) = {(q, 0S), (q, 1A), (q, 1)}
δ(q, 0, 0) = {(q, ε )}
δ(q, 1, 1) = {(q, ε )}
12 / 20
Unit – IV
5. Construct a PDA that will accept the language generated by the grammar G = ({S,
A}, {a, b}, P, S) with the productions S → AA / a, A → SA / b and test whether
“abbabb” is in N(M).
Solution:
Let the equivalent PDA, M = ({q}, {a, b}, {a, b, S, A}, δ, q, S)
where δ:
δ(q, ε , S) = {(q, AA), (q, a }
δ(q, ε , A) = {(q, SA), (q, b)}
δ(q, a, a) = {(q, ε )}
δ(q, b, b) = {(q, ε )}
Test whether “abbabb” is in N(M):

δ(q, abbabb , S) ⊢ δ(q, abbabb , AA) by δ(q, ε , S) = {(q, AA)}
⊢ δ(q, abbabb , SAA) by δ(q, ε , A) = {(q, SA)}
⊢ δ(q, abbabb , aAA) by δ(q, ε , S) = {(q, a)}
⊢ δ(q, abbabb , aAA) by δ(q, a, a) = {(q, ε)}
⊢ δ(q, bbabb , SAA) by δ(q, ε , A) = {(q, SA)}
⊢ δ(q, bbabb , AAAA) by δ(q, ε , S) = {(q, AA)}
⊢ δ(q, bbabb , bAAA) by δ(q, ε , A) = {(q, b)}
⊢ δ(q, babb , AAA) by δ(q, b , b) = {(q, ε)}
⊢ δ(q, babb , bAA) by δ(q, ε , A) = {(q, b)}
⊢ δ(q, abb , AA) by δ(q, b , b) = {(q, ε)}
⊢ δ(q, abb , SAA) by δ(q, ε , A) = {(q, SA)}
⊢ δ(q, abb , aAA) by δ(q, ε , S) = {(q, a)}
⊢ δ(q, bb , AA) by δ(q, a, a) = {(q, ε)}
⊢ δ(q, bb , bA) by δ(q, ε , A) = {(q, b)}
⊢ δ(q, b , A) by δ(q, b , b) = {(q, ε)}
⊢ δ(q, b , b) by δ(q, ε , A) = {(q, b)}
⊢ δ(q, ε , ε) by δ(q, b , b) = {(q, ε)}
Tutorial Problems:
6. Consider the grammar G = (VN, VT, P, S) and test whether “abbabb” is in N(M).
Where P :
A→ bS / b
B → aS
C→ε
13 / 20
Unit – IV
7. Consider the grammar G = (V, T, P, S)

Where P :
A → aB
B → aB/bB/ε
8. Consider the grammar G = (V, T, P, S) and test whether “0101001” is in N(M).
Where P :
S → 0S/1A/1/0B/0
A → 0A/1B/0/1
B → 0B/1A/0/1
Where P :
A → Ba/Ab/b
B → Ca/Bb
C → Aa/Cb/a
Where P :
A → aB/bA/b
B → aC/bB
C → aA/bC/a
Where P :
S → ABCD
A → aab
B → bba / bbaB
C → bab
D → aab / aabD
ii) Conversion of PDA to CFG
Theorem:
If L is N(M) for some PDA M then L is CFL.
Proof:
Let M = (Q, ∑, Γ, δ, q0, Z0, Ø) be a PDA
Construct the CFG G that accepts L(M) by empty stack as follows:
G = (V, T, P, S)
Where production P is defined by:
 The productions in P are induced by moves of PDA as follows:
Step 1: Rules for start symbol:

S productions are given by S → [q0 Z0 q] for every qQ
For example:
We have two states (q0, q1), so two rules for starting variable.
S → [q0 Z0 q0]
S → [q0 Z0 q1]
14 / 20
Unit – IV
Step 2: Rules for POP operations:

Each erasing move δ(q, a, Z) = (q1, ) induces production [q Z q’] → a
For example:
δ(q, a, Z) = (q1, )
[q Z q1] → a
δ(q, , Z) = (q1, )
[q Z q1] → 
Step 3: Rules for PUSH operations:

Each non-erasing move δ(q, a, Z) = (q’, Z1 Z2 Z3 …. Zn) induces many
productions of form.
[q Z q’] → a [q1 Z1 q2] [q2 Z2 q3]....................... [qn Zn q’]
Where each state q’, q1, q2, …. qn can be any state in Q
General Format 1:
δ(q0, a, Z) = (q0, Z1Z2)
[q0 Z ] → a [q0 Z1 ] [ Z2 ]
same
same
Filled with other states
Example: δ(q0, a, Z0) = (q0, XZ0) with two states (q0,q1)
[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0]

[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1]
[q0 Z0 q0] → a [q0 X q1] [q1 Z0 q0]
[q0 Z0 q1] → a [q0 X q1] [q1 Z0 q1]
General Format 2:
δ(q0, a, Z) = (q0, Z1)
[q0 Z ] → a [q0 Z1 ]
same Filled with others states

15 / 20
Unit – IV
Example: δ(q0, a, Z0) = (q0, X) with two states (q0,q1)
[q0 Z0 q0] → a [q0 X q0]

[q0 Z0 q1] → a [q0 X q1]
 Problems for CFG to PDA
1. Convert the PDA P= ({p, q},{0,1},{X,Z0}, δ, q, Z0) to a CFG , if is given by

1. δ(q, 1, Z0) ={(q, XZ0)}
2. δ(q, 1, X) = {(q, XX)}
3. δ(q, 0, X) = {(p, X)}
4. δ(q, ε, X) = {(q, ε)}
5. δ(p, 1, X) = {(p, ε)}
6. δ(p, 0, Z0) = {(q, Z0)}
Solution:
Step 1: Find the push and pop operations:

1. δ(q, 1, Z0) ={(q, XZ0)} - Push
2. δ(q, 1, X) = {(q, XX)} - Push
3. δ(q, 0, X) = {(p, X)} - Push
4. δ(q, ε, X) = {(q, ε)} - Pop
5. δ(p, 1, X) = {(p, ε)} - Pop
6. δ(p, 0, Z0) = {(q, Z0)} - Push

We have two states q and p.
So, S productions are
1. S → [q Z0 q]
2. S → [q Z0 p]

2. 1 Rules for δ(q, ε, X) = {(q, ε)} --- (4)
3. [q X q] → ε
2. 2 Rules for δ(p, 1, X) = {(p, ε)} --- (5)

4. [p X p] → 1

3. 1 Rules for δ(q, 1, Z0) ={(q, XZ0)} --- (1)
5. [q Z0 q] → 1 [q X q] [q Z0 q]
6. [q Z0 p] → 1 [q X q] [q Z0 p]
7. [q Z0 q] → 1 [q X p] [p Z0 q]
8. [q Z0 p] → 1 [q X p] [p Z0 p]
16 / 20
Unit – IV
3. 2 Rules for δ(q,1, X) = {(q,XX)} --- (2)

9. [q X q] → 1 [q X q] [q X q]
10. [q X p] → 1 [q X q] [q X p]
11. [q X q] → 1 [q X p] [p X q]
12. [q X p] → 1 [q X p] [p X p]
3. 3 Rules for δ(q,0, X) = {(p,X)} --- (3)

13. [q X q] → 0 [q X q]
14. [q X p] → 0 [q X p]
3. 4 Rules for δ(p, 0, Z0) = {(q, Z0)} --- (6)

15. [p Z0 q] → 0 [q Z0 q]
16. [p Z0 p] → 0 [q Z0 p]
2. Convert the PDA P= ({q, p}, {0,1},{Z0, X}, δ, q, Z0,{p}) to a Context free grammar.
1. δ(q,0, Z0) ={(q, XZ0)}
2. δ(q,0, X) = {(q, XX)}
3. δ(q,1, X) = {(q, X)}
4. δ(q, ε, X) = {(p, ε)}
5. δ(p, ε, X) = {(p, ε)}
6. δ(p,1, X) = {(p, XX)}
7. δ(p,1, Z0) = {(p, ε)}
Solution:
Step 1: Find the push and pop operations:
1. δ(q, 0, Z0) ={(q, XZ0)} - Push
2. δ(q, 0, X) = {(q, XX)} - Push
3. δ(q, 1, X) = {(q, X)} - Push
4. δ(q, ε, X) = {(p, ε)} - Pop
5. δ(p, ε, X) = {(p, ε)} - Pop
6. δ(p,1, X) = {(p, XX)} - Push
7. δ(p,1, Z0) = {(p, ε)} - Pop

We have two states q and p.
So, S productions are
1. S → [q Z0 q]
2. S → [q Z0 p]

2. 1 Rules for δ δ(q, ε, X) = {(p, ε)} --- (4)
3. [q X p] → ε
2. 2 Rules for δ(p, ε, X) = {(p, ε)} --- (5)

4. [p X p] → ε
2. 3 Rules for δ(p,1, Z0) = {(p, ε)} --- (7)

5. [p Z0 p] → 1
17 / 20
Unit – IV

3. 1 Rules for δ(q, 0, Z0) ={(q, XZ0)}--- (1)
6. [q Z0 q] → 0 [q X q] [q Z0 q]
7. [q Z0 p] → 0 [q X q] [q Z0 p]
8. [q Z0 q] → 0 [q X p] [p Z0 q]
9. [q Z0 p] → 0 [q X p] [p Z0 p]
3. 2 Rules for δ(q, 0, X) = {(q, XX)}--- (2)

10. [q X q] → 0 [q X q] [q X q]
11. [q X p] → 0 [q X q] [q X p]
12. [q X q] → 0 [q X p] [p X q]
13. [q X p] → 0 [q X p] [p X p]
3. 3 Rules for δ(q, 1, X) = {(q, X)} --- (3)

14. [q X q] → 1 [q X q]
15. [q X p] → 1 [q X p]
3. 4 Rules for δ(p,1, X) = {(p, XX)} ---- (6)

16. [p X q] → 1 [p X q] [q X q]
17. [p X p] → 1 [p X q] [q X p]
18. [p X q] → 1 [p X p] [p X q]
19. [p X p] → 1 [p X p] [p X p]
Tutorial Problems:
1. Construct a Context free grammar G which accepts N(M), where

M=({q0,q1},{a,b},{z0,z},δ,q0,z0,Φ) and where δ is given by
δ(q0,b,z0) = {(q0,zz0)}, δ(q0, ε,z0) = {(q0, ε)}
δ(q0,b,z) = {(q0,zz)}, δ(q0,a,z) = {(q1,z)}
δ(q1,b,z) = {(q1, ε)}, δ(q1,a,z0) = {(q0,z0)}
2. Construct the grammar from the given PDA.

M=({q0, q1},{0,1},{X,Z0},δ,q0,Z0,Φ) and where δ is given by
δ(q0,0,z0) = {(q0,XZ0)}, δ(q0,0,X) = {(q0,XX)},
δ(q0,1,X) = {(q1, ε)}, δ(q1,1,X) = {(q1, ε)},
δ(q1, ε,X) = {(q1, ε)}, δ(q1, ε, Z0 ) = {(q1, ε)}.
3. Let M =({q0,q1}, {0,1}, {S,A}, δ, q0, Z0, } to be a PDA

Where  is given by
 (q0, 0, S) = {(q0 , AS)}
 (q0, 0, A) = {(q0, AA), (q1, S)}
 (q0, 1, A) = {(q1, )}
 (q1, 1, A) = {(q1, )}
 (q1, , A) = {(q1, )}
 (q1, , S) = {(q1, )} Construct a CFG G = (V, T, P, S) generating N (M).
18 / 20
Unit – IV
Deterministic PDA
 In general terms, a deterministic PDA is one in which there is at most one possible
transition from any state based on the current input.
 A deterministic pushdown automaton (DPDA) is a 7-tuple
M = (Q, Σ, Γ, δ, q0, Z0, F),

Where
δ - Transition function δ : Q × Σ *× Γ* → (Q × Γ*)  {∅}
Example: Describe a DPDA that can recognize the language {w ; w contains more
a’s than b’s}.
Non-Deterministic PDA
 In general terms, a non-deterministic PDA is one in which there is more than two
possible transition from any state based on the current input.
 A non-deterministic pushdown automaton (NPDA) is a 7-tuple
M = (Q, Σ, Γ, δ, q0, Z0, F),

Where
δ - Transition function δ : Q × Σ *× Γ *→ 2(Q × Γ*)
Example: Define a NPDA that recognizes the language {wwR ; w  Σ*}.
Pumping Lemma
If L is a context-free language, there is a pumping length p such that any string w ∈
L of length ≥ p can be written as w = uvxyz, where vy ≠ ε, |vxy| ≤ p, and for all i ≥ 0,
uvixyiz ∈ L.
Applications of Pumping Lemma
Pumping lemma is used to check whether a grammar is context free or not. Let us
take an example and show how it is checked.
19 / 20
Unit – IV
Problem
1. Find out whether the language L = {xnynzn | n ≥ 1} is context free or not.
Solution
1. Let L is context free. Then, L must satisfy pumping lemma.
2. At first, choose a number n of the pumping lemma. Then, take z as 0n1n2n.
3. Break z into uvwxy, where |vwx| ≤ n and vx ≠ ε.
4. Hence vwx cannot involve both 0s and 2s, since the last 0 and the first 2 are at
least (n+1) positions apart. There are two cases:
5. Case 1 − vwx has no 2s. Then vx has only 0s and 1s. Then uwy, which would
have to be in L, has n 2s, but fewer than n 0s or 1s.
6. Case 2 − vwx has no 0s.
7. Here contradiction occurs.
8. Hence, L is not a context-free language.
2. The text uses the pumping lemma to show that {ww | w in ( 0 + 1)*} is not a CFL.
1. Suppose L were a CFL.
2. Let n be L’s pumping-lemma constant.
3. Consider z = 0n10n10n.
4. We can write z = uvwxy, where |vwx| < n, and |vx| > 1.
5. Case 1: vx has no 0’s.
6. Then at least one of them is a 1, and uwy has at most one 1, which no string in
L does.
7. Still considering z = 0n10n10n.
8. Case 2: vx has at least one 0.
9. vwx is too short (length < n) to extend to all three blocks of 0’s in 0n10n10n.
10. Thus, uwy has at least one block of n 0’s, and at least one block with fewer
than n 0’s.
11. Thus, uwy is not in L.
Closure properties of CFL (Without proof)

1. CFLs are closed under union
If L1 and L2 are CFLs, then L1 𝖴 L2 is a CFL.
2. CFLs are closed under concatenation
If L1 and L2 are CFLs, then L1L2 is a CFL.
3. CFLs are closed under Kleene closure
If L is a CFL, then L ∗ is a CFL.
4. CFLs are not closed under intersection
If L1 and L2 are CFLs, then L1 ∩ L2 may not be a CFL.
5. CFLs are not closed under complement
If L is a CFL, then L may not be a CFL.
20 / 20
21 / 19
22 / 19

Automata Doc

Uploaded by

Copyright:

Available Formats

Automata Doc

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Automata Doc

Uploaded by

Copyright:

Available Formats

Unit – I

 History of Theory of Computation

Finite State systems

 The set of strings over an alphabet ∑ is usually denoted by ∑ *.

 The set of strings over an alphabet ∑ excluding є is usually denoted by ∑ +.

 Transition Diagram (Transition graph)

Start or Initial State Final or Accepting State

 Computation of a Finite Automaton

 Types of Finite Automata

Deterministic Finite Automata (DFA)

 Formal Definition of Deterministic Finite Automata

Non-Deterministic Finite Automata (NDFA or NFA)

Non-Deterministic Finite Automaton is a FA in which there many paths for a

 Formal Definition of Non-Deterministic Finite Automata

Finite Automaton with ε- moves

 Formal Definition of Non-Deterministic Finite Automata

Differentiate DFA and NFA

Problems for Finite Automata

2. Design FA to accept the string that always ends with 00.

3. Design FA to check whether given unary number is divisible by three.

6. Obtain  closure of each state in the following NFA with  move.

Equivalence of NFA and DFA

δʹ(q0ʹ, x) = [q1, q2, q3, …, qi]

δʹ (q0ʹ, xa) = δʹ (δʹ (q0ʹ, x),a)

δʹ(q0ʹ, x) = [p1, p2, p3, …, pi]

δʹ( [p1, p2, p3, …, pi], a) = [r1, r2, r3, …, ri]

Shown by induction hypothesis,

Extended Transition Function (δʹʹ or δ^)

δʹʹ(pi, xa) = δʹʹ( δ(q,x) a))

Example Problems for Converting NFA into DFA

1. Obtain the DFA equivalent to the following NFA.

δʹ([q0], 0) = [q0, q1] - a new state - A

The transition table for DFA

[q0] [q0, q1] [q0]

δʹ ([q0], 0) = [q0, q1] -a new state A

The transition table for DFA

[q0] [q0, q1] [q1]

The transition diagram for DFA

3. Obtain the DFA equivalent to the following NFA.

Equivalence of NDFA’s with and without ε-moves

Example Problems for Converting NFA with  into NFA without 

The transition table for NFA

2. Construct NFA without  from NFA with .

The transition table for NFA

*q0 {q0,q1} {q1}

The transition diagram for NFA

1. Obtain the NFA equivalent to the following NFA with -move.

2. Let M = ({q0, q1,q2,q3}, {0,1}, δ, q0, {q2,q3}) be -NFA.

Example Problems for Converting NFA with -move into DFA

1. Construct DFA from the following -NFA.

ε – closure (δ (A, a)) = ε – closure (q0,q2)

The transition table for DFA

The transition diagram for DFA qA2

2. Construct DFA from the following -NFA.

ε – closure (δ (A, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

ε – closure (δ (A, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

ε – closure (δ (B, 0)) = ε – closure (p,r) = ε – closure (p)  ε – closure (r)

ε – closure (δ (B, 1)) = ε – closure (q,s) = ε – closure (q)  ε – closure (s)

The transition table for DFA

The transition diagram for DFA

3. Show that (01)* = (0+1)*.

LHS : (01)* = { , 0,1,00,11,0011,011,0011110… .................... }

6. Show that (r) = r* for a regular expression r.