UNIT-I

Automata:
The term "Automata" is derived from the Greek word "αὐτό ματα" which
means "self-acting". An automaton (Automata in plural) is an abstract self-
propelled computing device which follows a predetermined sequence of
operations automatically.
An automaton with a finite number of states is called a Finite
Automaton(FA) or Finite State Machine (FSM).
Formal definition of a Finite Automaton:
An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where −
 Q is a finite set of states.
 ∑ is a finite set of symbols, called the alphabet of the automaton.
 δ is the transition function.
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).

Alphabet ,String and Language.

Alphabet
 Definition − An alphabet is any finite set of symbols.
 Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’
are symbols.
String
 Definition − A string is a finite sequence of symbols taken from ∑.
 Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}
Language
 Definition − A language is a subset of ∑* for some alphabet ∑. It can be
finite or infinite.
 Example − If the language takes all possible strings of length 2 over ∑
= {a, b}, then L = { ab, bb, ba, bb}
Types of Automata with an Example.

Finite Automaton can be classified into two types −

 Deterministic Finite Automaton (DFA)
 Non-deterministic Finite Automaton (NDFA / NFA)
Deterministic Finite Automaton (DFA)
In DFA, for each input symbol, one can determine the state to which the
machine will move. Hence, it is called Deterministic Automaton. As it has a
finite number of states, the machine is called Deterministic Finite
Machineor Deterministic Finite Automaton.
Formal Definition of a DFA
A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
 Q is a finite set of states.
  ∑ is a finite set of symbols called the alphabet.
 δ is the transition function where δ: Q × ∑ → Q
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
Graphical Representation of a DFA
A DFA is represented by digraphs called state diagram.

 The vertices represent the states.

 The arcs labeled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
Example
Let a deterministic finite automaton be →

 Q = {a, b, c},
 ∑ = {0, 1},
 q0 = {a},
 F = {c}, and
Transition function δ as shown by the following table −
Present State Next State for Input 0 Next State for Input 1

a a b

b c a

c b c
Its graphical representation would be as follows −

Non-deterministic Finite Automaton (NDFA / NFA):

In NDFA, for a particular input symbol, the machine can move to any combination
of the states in the machine. In other words, the exact state to which the machine
moves cannot be determined. Hence, it is called Non-deterministic Automaton. As
it has finite number of states, the machine is called Non-deterministic Finite
Machine or Non-deterministic Finite Automaton.
Formal Definition of an NDFA
An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
  Q is a finite set of states.
 ∑ is a finite set of symbols called the alphabets.
 δ is the transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from
a state, transition can occur to any combination of Q states)
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
Graphical Representation of an NDFA: (same as DFA)
An NDFA is represented by digraphs called state diagram.
 The vertices represent the states.
 The arcs labeled with an input alphabet show the transitions.
 The initial state is denoted by an empty single incoming arc.
 The final state is indicated by double circles.
Example
Let a non-deterministic finite automaton be →
 Q = {a, b, c}
 ∑ = {0, 1}
 q0 = {a}
 F = {c}
The transition function δ as shown below −
Present State Next State for Input 0 Next State for Input 1

a a, b b

b c a, c

c b, c c
Its graphical representation would be as follows −

Differences between NFA and DFA:

DFA vs NDFA
The following table lists the differences between DFA and NDFA.
DFA NDFA

The transition from a state is to a The transition from a state can

single particular next state for each be to multiple next states for
 input symbol. Hence it is each input symbol. Hence it is
called deterministic. called non-deterministic.

Empty string transitions are not seen NDFA permits empty

in DFA. string transitions.

Backtracking is allowed in DFA In NDFA, backtracking is not

always possible.

Requires more space. Requires less space.

A string is accepted by a DFA, if it A string is accepted by a NDFA, if

transits to a final state. at least one of all possible
transitions ends in a final state.

Acceptance of NFA/DFA:
Acceptability by DFA and NDFA:
A string is accepted by a DFA/NDFA iff the DFA/NDFA starting at the initial
state ends in an accepting state (any of the final states) after reading the
string wholly.
A string S is accepted by a DFA/NDFA (Q, ∑, δ, q0, F), iff δ*(q0, S) ∈
F The language L accepted by DFA/NDFA is {S | S ∈ ∑* and δ*(q0, S) ∈
F}
A string S′ is not accepted by a DFA/NDFA (Q, ∑, δ, q0, F), iff
δ*(q0, S′) ∉ F
The language L′ not accepted by DFA/NDFA (Complement of accepted
language L) is {S | S ∈ ∑* and δ*(q0, S) ∉ F}
Example
Let us consider the DFA shown in Figure 1.3. From the DFA, the acceptable
strings can be derived.
Strings accepted by the above DFA: {0, 00, 11, 010, 101,..................}
Strings not accepted by the above DFA: {1, 011, 111,.............}
Convert the following NFA to DFA.

q δ(q,0) δ(q,1)

a {a,b,c,d,e} {d,e}

b {c} {e}

c ∅ {b}

d {e} ∅

e ∅ ∅

we find its equivalent DFA. The state table of the DFA is shown in below.

q δ(q,0) δ(q,1)

[a] [a,b,c,d,e] [d,e]

[a,b,c,d,e] [a,b,c,d,e] [b,d,e]

[d,e] [e] ∅

[b,d,e] [c,e] [e]

[e] ∅ ∅

[c, e] ∅ [b]

[b] [c] [e]

 [c] ∅ [b]

The state diagram of the DFA is as follows −

Mealy and Moore Machines:

Finite automata may have outputs corresponding to each transition. There

are two types of finite state machines that generate 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.
It can be described by a 6 tuple (Q, ∑, O, δ, X, q0) where −
 Q is a finite set of states.
  ∑ is a finite set of symbols called the input alphabet.
 O is a finite set of symbols called the output alphabet.
 δ is the input transition function where δ: Q × ∑ → Q
 X is the output transition function where X: Q × ∑ → O
 q0 is the initial state from where any input is processed (q0 ∈ Q).
The state table of a Mealy Machine is shown below −
Present state Next state
input = 0 input = 1
State Output State Output
→a b x1 c x1
b b x2 d x3
c d x3 c x1
d d x3 d x2
The state diagram of the above Mealy Machine is −

Moore Machine
Moore machine is an FSM whose outputs depend on only the present state.
A Moore machine can be described by a 6 tuple (Q, ∑, O, δ, X, q0) where −
 Q is a finite set of states.
 ∑ is a finite set of symbols called the input alphabet.
 O is a finite set of symbols called the output alphabet.
 δ is the input transition function where δ: Q × ∑ → Q
 X is the output transition function where X: Q → O
 q0 is the initial state from where any input is processed (q0 ∈ Q).
The state table of a Moore Machine is shown below −
Present state Next State Output
Input = 0 Input = 1
→a b c x2
b b d x1
c c d x2
d d d x3
The state diagram of the above Moore Machine is −
Explain the difference between Moore and Mealy Machine.

Mealy Machine Moore Machine

Output depends both upon the Output depends only upon the
present state and the present present state.
input

Generally, it has fewer states Generally, it has more states than

than Moore Machine. Mealy Machine.

The value of the output function The value of the output function
is a function of the transitions is a function of the current state
and the changes, when the input and the changes at the clock
logic on the present state is edges, whenever state changes
done. occur.

Mealy machines react faster to In Moore machines, more logic is

inputs. They generally react in required to decode the outputs
the same clock cycle. resulting in more circuit delays.
They generally react one clock
cycle later.

Moore machine to Mealy machine conversion.

Moore machine −
 Present State Next State Output

a=0 a=1

→a d b 1

b a d 0

c c c 0

d b a 1

Ans:
Step 1 & 2 −
Present State Next State

a=0 a=1

State Output State Output

→a d b

b a d

c c c

d b a

Step 3 −
Present State Next State

a=0 a=1

State Output State Output

=> a d 1 b 0

b a 1 d 1

c c 0 c 0

d b 0 a 1

Mealy machine to Moore machine conversion.

Mealy Machine −
 Present State Next State

a=0 a=1

Next State Output Next State Output

→a d 0 b 1

b a 1 d 0

c c 1 c 0

d b 0 a 1

Ans:
states ‘a’ and ‘d’ give only 1 and 0 outputs respectively, so we retain
states ‘a’ and ‘d’. But states ‘b’ and ‘c’ produce different outputs (1 and
0). So, we divide b into b0, b1 and c into c0, c1.
Present State Next State Output

a=0 a=1

→a d b1 1

b0 a d 0

b1 a d 1

c0 c1 C0 0

c1 c1 C0 1

d b0 a 0
Construction of minimized DFA for the following DFA.

Ans:
Step 1. P0 will have two sets of states. One set will contain q1, q2, q4
which are final states of DFA and another set will contain remaining
states. So P0 = { { q1, q2, q4 }, { q0, q3, 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.
Since, q1 and q2 are not distinguishable and q1 and q4 are also not
distinguishable, So q2 and q4 are not distinguishable. So, { q1, q2, q4 }
set will not be partitioned in P1.
For set { q0, q3, q5 } :
δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0
δ ( q0, 1) = q1 and δ ( q3, 1 ) = q4
Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which
are in same set in partition P0. Similarly, Moves of q0 and q3 on input
symbol 1 are q3 and q0 which are in same set in partition P0. So, q0 and
q3 are not distinguishable.
δ ( q0, 0 ) = q3 and δ ( q5, 0 ) = q5 and δ ( q0, 1 ) = q1 and δ ( q5, 1 ) = q5
Moves of q0 and q5 on input symbol 0 are q3 and q5 respectively which
are in different set in partition P0. So, q0 and q5 are distinguishable. So,
set { q0, q3, q5 } will be partitioned into { q0, q3 } and { q5 }. So,
P1 = { { q1, q2, q4 }, { q0, q3}, { q5 } }
To calculate P2, we will check whether sets of partition P1 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.
Since, q1 and q2 are not distinguishable and q1 and q4 are also not
distinguishable, So q2 and q4 are not distinguishable. So, { q1, q2, q4 }
set will not be partitioned in P2.
For set { q0, q3 } :
δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0
δ ( q0, 1 ) = q1 and δ ( q3, 1 ) = q4
Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which are
in same set in partition P1. Similarly, Moves of q0 and q3 on input symbol 1
are q3 and q0 which are in same set in partition P1. So, q0 and q3 are not
distinguishable.
For set { q5 }:
Since we have only one state in this set, it can’t be further partitioned. So,
P2 = { { q1, q2, q4 }, { q0, q3 }, { q5 } }
Since, P1=P2. So, this is the final partition. Partition P2 means that q1, q2
and q4 states are merged into one. Similarly, q0 and q3 are merged into one.
Minimized DFA corresponding to DFA is:

*********
 UNIT- II

Regular Languages and Regular Expression:

Regular Languages : In formal language theory, a regular language (also

called a rational language) is a formal language that can be expressed using
a regular expression. a regular language can be defined as a language
recognized by a finite automaton.
Regular Expression: Regular Expressions are used to denote regular
languages.
A Regular Expression can be recursively defined as follows −
 ε is a Regular Expression indicates the language containing an empty
string. (L (ε) = {ε})
 φ is a Regular Expression denoting an empty language. (L (φ) = { })
 x is a Regular Expression where L = {x}
 If X is a Regular Expression denoting the language L(X) and Y is a
Regular Expression denoting the language L(Y), then
o X + Y is a Regular Expression corresponding to the language L(X)
𝖴 L(Y) where L(X+Y) = L(X) 𝖴 L(Y).
o X . Y is a Regular Expression corresponding to the language L(X)
. L(Y) where L(X.Y) = L(X) . L(Y)
o R* is a Regular Expression corresponding to the
language L(R*)where L(R*) = (L(R))*
Conversion of RE 1 (0 + 1)* 0 into NFA.

We will concatenate three expressions "1", "(0 + 1)*" and "0"

Now we will remove the ε transitions. After we remove the ε transitions from
the NDFA, we get the following −
Regular Set and its properties:
Regular Set: Any set that represents the value of the Regular Expression
is called a Regular Set.
Properties of Regular Sets:
Property 1. The union of two regular set is regular.
Proof −
Let us take two regular expressions
RE1 = a(aa)* and RE2 = (aa)*
So, L1 = {a, aaa, aaaaa,.......} (Strings of odd length excluding Null)
and L2 ={ ε, aa, aaaa, aaaaaa,........} (Strings of even length including Null)
L1 𝖴 L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,........}
(Strings of all possible lengths including Null)
RE (L1 𝖴 L2) = a* (which is a regular expression itself)
Hence, proved.
Property 2. The intersection of two regular set is regular.
Proof −
Let us take two regular expressions
RE1 = a(a*) and RE2 = (aa)*
So, L1 = { a,aa, aaa, aaaa,........} (Strings of all possible lengths excluding Null)
L2 = { ε, aa, aaaa, aaaaaa,........} (Strings of even length including Null)
L1 ∩ L2 = { aa, aaaa, aaaaaa,.......} (Strings of even length excluding Null)
RE (L1 ∩ L2) = aa(aa)* which is a regular expression itself.
Hence, proved.
Property 3. The complement of a regular set is regular.
Proof −
Let us take a regular expression −
RE = (aa)*
So, L = {ε, aa, aaaa, aaaaaa,..........} (Strings of even length including Null)
Complement of L is all the strings that is not in L.
So, L’ = {a, aaa, aaaaa,.......} (Strings of odd length excluding Null)
RE (L’) = a(aa)* which is a regular expression itself.
Hence, proved.
Property 4. The difference of two regular set is regular.
Proof −
Let us take two regular expressions −
RE1 = a (a*) and RE2 = (aa)*
So, L1 = {a, aa, aaa, aaaa,.......} (Strings of all possible lengths excluding Null)
L2 = { ε, aa, aaaa, aaaaaa,........} (Strings of even length including Null)
L1 – L2 = {a, aaa, aaaaa, aaaaaaa,........}
(Strings of all odd lengths excluding Null)
RE (L1 – L2) = a (aa)* which is a regular expression.
Hence, proved.
Property 5. The reversal of a regular set is regular.
Proof −
We have to prove LR is also regular if L is a regular set.
Let, L = {01, 10, 11, 10}
RE (L) = 01 + 10 + 11 + 10
LR = {10, 01, 11, 01}
RE (LR) = 01 + 10 + 11 + 10 which is regular
Hence, proved.
Property 6. The closure of a regular set is regular.
Proof −
If L = {a, aaa, aaaaa, .......} (Strings of odd length excluding Null)
i.e., RE (L) = a (aa)*
L* = {a, aa, aaa, aaaa , aaaaa,…..............} (Strings of all lengths excluding Null)
RE (L*) = a (a)*
Hence, proved.
Property 7. The concatenation of two regular sets is regular.
Proof −
Let RE1 = (0+1)*0 and RE2 = 01(0+1)*
Here, L1 = {0, 00, 10, 000, 010,..........} (Set of strings ending in 0)
and L2 = {01, 010,011,.......} (Set of strings beginning with 01)
Then, L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,....................}
Set of strings containing 001 as a substring which can be represented by an
RE − (0 + 1)*001(0 + 1)*
Hence, proved.

Identities Related to Regular Expressions:

Given R, P, L, Q as regular expressions, the following identities hold −
 ∅* = ε
 ε* = ε
 RR* = R*R
 R*R* = R*
 (R*)* = R*
 RR* = R*R
 (PQ)*P =P(QP)*
 (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
 R + ∅ = ∅ + R = R (The identity for union)
 R ε = ε R = R (The identity for concatenation)
 ∅ L = L ∅ = ∅ (The annihilator for concatenation)
 R + R = R (Idempotent law)
 L (M + N) = LM + LN (Left distributive law)
 (M + N) L = LM + LN (Right distributive law)
 ε + RR* = ε + R*R = R*
 Arden's Theorem:

Statement −
Let P and Q be two regular expressions.
If P does not contain null string, then R = Q + RP has a unique solution that
is R = QP*
Proof −
R = Q + (Q + RP)P [After putting the value R = Q + RP]
= Q + QP + RPP
When we put the value of R recursively again and again, we get the following
equation −
R = Q + QP + QP2 + QP3…..
R = Q (ε + P + P2 + P3 + …. )
R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]
Hence, proved.
Construct of regular expression corresponding to the automata given
below −

Here the initial state is q1 and the final state is q2

Now we write down the equations −
q1 = q10 + ε
q2 = q11 + q20
q3 = q21 + q30 + q31
Now, we will solve these three equations −
q1 = ε0* [As, εR = R]
So, q1 = 0*
q2 = 0*1 + q20
So, q2 = 0*1(0)* [By Arden’s theorem]
Hence, the regular expression is 0*10*.
Pumping Lemma Applications:
Let L be a regular language. Then there exists a constant ‘c’ such that for every
string w in L −|w| ≥ c
We can break w into three strings, w = xyz, such that −
 |y| > 0
 |xy| ≤ c
 For all k ≥ 0, the string xykz is also in L.
Applications of Pumping Lemma
Pumping Lemma is to be applied to show that certain languages are not
regular. It should never be used to show a language is regular.
 If L is regular, it satisfies Pumping Lemma.
 If L does not satisfy Pumping Lemma, it is non-regular.

Proving that L = {aibi | i ≥ 0} is not regular.

At first, we assume that L is regular and n is the number of states.
Let w = anbn. Thus |w| = 2n ≥ n.
By pumping lemma, let w = xyz, where |xy| ≤ n.
Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus
|y| ≠ 0.
Let k = 2. Then xy2z = apa2qarbn.
Number of as = (p + 2q + r) = (p + q + r) + q = n + q
Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
Thus, xy2z is not in L. Hence L is not regular.

Closure properties of Regular sets.

Let L and M be regular languages. Then the following languages are all
regular:
• Union: L 𝖴 M
• Intersection: L ∩ M
• Complement: N
• Difference: L \ M
• Reversal: LR = {wR : w ∈ L}
• Closure: L∗ .
• Concatenation: L.M
• Homomorphism: h(L) = {h(w) : w ∈ L, h is a homom. }
• Inverse homomorphism: h −1(L) = {w ∈ Σ : h(w) ∈ L, h : Σ → ∆ is a homom. }

*******
 UNIT-III
CFG:
A context free grammar G can be formally written as a 4-tuple (N, T, S, P) where
−

N or VN is a set of variables or non-terminal symbols.

T or ∑ is a set of Terminal symbols.

S is a special variable called the Start symbol, S ∈ N

P is Production rules for Terminals and Non-terminals. A production
rule has the form α → β, where α is VN and β are strings on
(VN 𝖴 ∑) *.
Example
Grammar G −
({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})
Here,

S, A, and B are Non-terminal symbols;

a and b are Terminal symbols

S is the Start symbol, S ∈ N

Productions, P : S → AB, A → a, B → b

Derivation:

Derivation: Deriving a string from grammar

Leftmost and Rightmost Derivation of a String

Leftmost derivation − A leftmost derivation is obtained by applying
production to the leftmost variable in each step.

Rightmost derivation − A rightmost derivation is obtained by applying
production to the rightmost variable in each step.
Example
Let any set of production rules in a CFG be
X → X+X | X*X |X| a
over an alphabet {a}.
The leftmost derivation for the string "a+a*a" may be −
X → X+X → a+X → a + X*X → a+a*X → a+a*a
The stepwise derivation of the above string is shown as below −
The rightmost derivation for the above string "a+a*a" may be −
X → X*X → X*a → X+X*a → X+a*a → a+a*a
The stepwise derivation of the above string is shown as below −

Left and Right Recursive Grammars:

In a context-free grammar G, if there is a production in the form X →

Xawhere X is a non-terminal and ‘a’ is a string of terminals, it is called a left
recursive production. The grammar having a left recursive production is
called a left recursive grammar.
 And if in a context-free grammar G, if there is a production is in the form X
→ aX where X is a non-terminal and ‘a’ is a string of terminals, it is called
a right recursive production. The grammar having a right recursive
production is called a right recursive grammar.
Ambiguous Grammar:
If a context free grammar G has more than one 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.

Checking whether the grammar G with production rules −

X → X+X | X*X |X| a is ambiguous or not.

Let’s find out the derivation tree for the string "a+a*a". It has two leftmost
derivations.
Derivation 1 − X → X+X → a +X → a+ X*X → a+a*X → a+a*a
Parse tree 1 −

Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

Parse tree 2 −

Since there are two parse trees for a single string "a+a*a", the grammar G is
ambiguous.
 Closure properties of CFL:

Context-free languages are closed under −


Union

Concatenation

Kleene Star operation
Union:
Let L1 and L2 be two context free languages. Then L1 𝖴 L2 is also context
free. Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have
P: S1 → aAb|ab
Let L2 = { cmdm , m ≥ 0}.Corresponding grammar G2 will have
P: S2 → cBb| ε
Union of L1 and L2, L = L1 𝖴 L2 = { anbn } 𝖴 { cmdm }
The corresponding grammar G will have the additional production S → S1 |
S2
Concatenation
If L1 and L2 are context free languages, then L1L2 is also context free.
Example
Union of the languages L1 and L2, L = L1L2 = { anbncmdm }
The corresponding grammar G will have the additional production S → S1
S2
Kleene Star
If L is a context free language, then L* is also context free.
Example
Let L = {anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε
Kleene Star L1 = { anbn }*
The corresponding grammar G1 will have additional productions S1 → SS1 |
ε
Context-free languages are not closed under −

Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is
not necessarily context free.

Intersection with Regular Language − If L1 is a regular language and
L2 is a context free language, then L1 ∩ L2 is a context free language.

Complement − If L1 is a context free language, then L1’ may not be
context free.
 Simplification of CFGs:

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 and unit productions. Elimination of these productions and
symbols is called simplification of CFGs. Simplification essentially
comprises of the following steps −

Reduction of CFG

Removal of Unit Productions

Removal of Null Productions
Reduction of CFG
CFGs are reduced in two phases −
Phase 1 − Derivation of an equivalent grammar, G’, from the CFG, G, such
that each variable derives some terminal string.
Derivation Procedure −
Step 1 − Include all symbols, W1, that derive some terminal and initialize
i=1. Step 2 − Include all symbols, Wi+1, that derive Wi.
Step 3 − Increment i and repeat Step 2, until Wi+1 = Wi.
Step 4 − Include all production rules that have Wi in it.
Phase 2 − Derivation of an equivalent grammar, G”, from the CFG, G’, such
that each symbol appears in a sentential form.
Derivation Procedure −
Step 1 − Include the start symbol in Y1 and initialize i = 1.
Step 2 − Include all symbols, Yi+1, that can be derived from Yi and include all
production rules that have been applied.
Step 3 − Increment i and repeat Step 2, until Yi+1 = Yi.

Removal of Unit Productions

Any production rule in the form A → B where A, B ∈ Non-terminal is
called unit production..

Removal Procedure −
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.
Removal of Null Productions
In a CFG, a non-terminal symbol ‘A’ is a nullable variable if there is a
production A → ε or there is a derivation that starts at A and finally ends up
with
ε: A →.............→ ε
 Removal Procedure
Step 1 − Find out nullable non-terminal variables which derive ε.
Step 2 − For each production A → a, construct all productions A →
x where x is obtained from ‘a’ by removing one or multiple non-terminals
from Step 1.
Step 3 − Combine the original productions with the result of step 2 and
remove ε - productions.

Removing null production from the following −

S → ASA | aB | b, A → B, B → b | ∈
There are two nullable variables − A and B
At first, we will remove B → ε.
After removing B → ε, the production set becomes −
S→ASA | aB | b | a, A ε B| b | &epsilon, B → b
Now we will remove A → ε.
After removing A → ε, the production set becomes −
S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b
This is the final production set without null transition.

Chomsky Normal Form:

A CFG is in Chomsky Normal Form if the Productions are in the following
forms −

A→a

A → BC
where A, B, and C are non-terminals and a is terminal
Algorithm to Convert into Chomsky Normal Form :
Step 1 − If the start symbol S occurs on some right side, create a new start
symbol S’ and a new production S’→ S.
Step 2 − Remove Null productions. (Using the Null production removal
algorithm discussed earlier)
Step 3 − Remove unit productions. (Using the Unit production removal
algorithm discussed earlier)
Step 4 − Replace each production A → B 1…Bn where n > 2 with A → B 1C
where C → B2 …Bn. Repeat this step for all productions having two or more
symbols 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.
Converting the CFG into CNF:
S → ASA | aB, A → B | S, B → b | ε

(1)
Since S appears in R.H.S, we add a new state S0 and S0→S is added to
the production set and it becomes −
S0→S, S→ ASA | aB, A → B | S, B → b | ∈
(2)
Now we will remove the null productions −
B → ∈ and A → ∈
After removing B → ε, the production set becomes −
S0→S, S→ ASA | aB | a, A → B | S | ∈, B → b
After removing A → ∈, the production set becomes
−
S0→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b
(3)
Now we will remove the unit productions.
After removing S → S, the production set becomes −
S0→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b
After removing S0→ S, the production set becomes −
S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → B | S, B → b
After removing A→ B, the production set becomes −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → S | b, B → b
After removing A→ S, the production set becomes −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS |
SA A → b |ASA | aB | a | AS | SA, B → b
(4)
Now we will find out more than two variables in the R.H.S
Here, S0→ ASA, S → ASA, A→ ASA violates two Non-terminals in R.H.S.
Hence we will apply step 4 and step 5 to get the following final production
set which is in CNF −
S0→ AX | aB | a | AS | SA
S→ AX | aB | a | AS | SA
A → b |AX | aB | a | AS | SA
B → b, X → SA
(5)
We have to change the productions S0→ aB, S→ aB, A→ aB
And the final production set becomes −
S0→ AX | YB | a | AS | SA
S→ AX | YB | a | AS | SA
A → b A → b |AX | YB | a | AS | SA
B→b
X → SA
Y→a
 Griebach Normal Form:

A CFG is in Greibach Normal Form if the Productions are in the following

forms −
A→b
A → bD1…Dn
where A, D1,....,Dn are non-terminals and b is a terminal.
Algorithm to Convert a CFG into Greibach Normal Form:
Step 1 − If the start symbol S occurs on some right side, create a new start
symbol S’ and a new production S’ → S.
Step 2 − Remove Null productions. (Using the Null production removal
algorithm discussed earlier)
Step 3 − Remove unit productions. (Using the Unit production removal
algorithm discussed earlier)
Step 4 − Remove all direct and indirect left-recursion.
Step 5 − Do proper substitutions of productions to convert it into the
proper form of GNF.

Example: Convert the following CFG into CNF

S → XY | Xn | p
X → mX | m
Y → Xn | o
Ans:
Here, S does not appear on the right side of any production and there are no
unit or null productions in the production rule set. So, we can skip Step 1 to
Step 3.
Step 4
Now after replacing
X in S → XY | Xo |
p with mX | m
we obtain
S → mXY | mY | mXo | mo |
p. And after replacing
X in Y → Xn | o
with the right side
of X → mX | m
we obtain
Y → mXn | mn | o.
Two new productions O → o and P → p are added to the production set and
then we came to the final GNF as the following −
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O→o
P→p
Pumping Lemma for CFL and its Application:

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.

Example: Find out whether the language L = {xnynzn | n ≥ 1} is context

free or not.
Ans:
Let L is context free. Then, L must satisfy pumping lemma.
At first, choose a number n of the pumping lemma. Then, take z as 0n1n2n.
Break z into uvwxy, where |vwx| ≤ n and vx ≠ ε.
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 −
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.
Case 2 − vwx has no 0s.
Here contradiction occurs.
Hence, L is not a context-free language.

**********
 UNIT-IV

Basic Structure of PDA:

A pushdown automaton is a way to implement a context-free grammar in

a similar way we design DFA for a regular grammar. A DFA can remember a
finite amount of information, but a PDA can remember an infinite amount of
information.
Basically a pushdown automaton is −
"Finite state machine" + "a stack"
A pushdown automaton has three components −
 an input tape,
 a control unit, and
 a stack with infinite size.
The stack head scans the top symbol of the stack.
A stack does two operations −
 Push − a new symbol is added at the top.
 Pop − the top symbol is read and removed.
A PDA may or may not read an input symbol, but it has to read the top of
the stack in every transition.

A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −

 Q is the finite number of states
 ∑ is input alphabet
 S is stack symbols
 δ is the transition function: Q × (∑ 𝖴 {ε}) × S × Q × S*
 q0 is the initial state (q0 ∈ Q)
 I is the initial stack top symbol (I ∈ S)
 F is a set of accepting states (F ∈ Q)
The following diagram shows a transition in a PDA from a state q1 to state
q2, labeled as a,b → c −
This means at state q1, if we encounter an input string ‘a’ and top symbol of
the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to
state q2.

Instantaneous Description of PDA:

Instantaneous Description:

The instantaneous description (ID) of a PDA is represented by a triplet (q, w,

s) where
 q is the state
 w is unconsumed input
 s is the stack contents

Acceptance of Language by PDA:

There are two different ways to define PDA acceptability:

Final State Acceptability:
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.
For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the set of final states
F is − L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F}
for any input stack string x.
Empty Stack Acceptability:
Here a PDA accepts a string when, after reading the entire string, the PDA
has emptied its stack.
For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the empty stack is
L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}
Example: Construction of PDA that accepts L = {0n 1n | n ≥ 0}

This language accepts L = {ε, 01, 0011, 000111,.....................................}

Here, in this example, the number of ‘a’ and ‘b’ have to be same.
 Initially we put a special symbol ‘$’ into the empty stack.
 Then at state q2, if we encounter input 0 and top is Null, we push 0
into stack. This may iterate. And if we encounter input 1 and top is 0,
we pop this 0.
 Then at state q3, if we encounter input 1 and top is 0, we pop this 0.
This may also iterate. And if we encounter input 1 and top is 0, we
pop the top element.
 If the special symbol ‘$’ is encountered at top of the stack, it is popped
out and it finally goes to the accepting state q4.
Example: Construction of PDA that accepts L = { wwR | w = (a+b)* }

Initially we put a special symbol ‘$’ into the empty stack. At state q2, the w
is being read. In state q3, each 0 or 1 is popped when it matches the input. If
any other input is given, the PDA will go to a dead state. When we reach that
special symbol ‘$’, we go to the accepting state q4.
Procedure to convert CFG to PDA:

Algorithm to find PDA corresponding to a given CFG

Input − A CFG, G = (V, T, P, S)
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)
 Step 1 − Convert the productions of the CFG into GNF.
Step 2 − The PDA will have only one state {q}.
Step 3 − The start symbol of CFG will be the start symbol in the PDA.
Step 4 − All non-terminals of the CFG will be the stack symbols of the PDA
and all the terminals of the CFG will be the input symbols of the PDA.
Step 5 − For each production in the form A → aX where a is terminal and A,
X are combination of terminal and non-terminals, make a transition δ (q, a,
A).
Example: Construct a PDA from the following CFG.
G = ({S, X}, {a, b}, P, S)
where the productions are −
S → XS | ε , A → aXb | Ab | ab
Ans:
Let the equivalent PDA,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
where δ −
δ(q, ε , S) = {(q, XS), (q, ε )}
δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}
δ(q, a, a) = {(q, ε )}
δ(q, 1, 1) = {(q, ε )}

Procedure to convert PDA to CFG:

Algorithm to find CFG corresponding to a given PDA:

Input − A CFG, G = (V, T, P, S)
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non-
terminals of the grammar G will be {X wx | w,x ∈ Q} and the start state will be
Aq0,F.
Step 1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains
(y, m) and (z, b, m) contains (x, ε), add the production rule X wx → a Xyzb in
grammar G.
Step 2 − For every w, x, y, z ∈ Q, add the production rule X wx → XwyXyx in
grammar G.
Step 3 − For w ∈ Q, add the production rule Xww → ε in grammar G.
Example: Converting a PDA into an equivalent CFG PDA={ a n bn/n=0 }.
Ans:
S → [q0 Z0 q2]
[q1 Z0 q2] → ε
[q1 X q1] → b
[q0 Z0 q0] → [q1 Z0 q0]
[q0 Z0 q1] → [q1 Z0 q1]
[q0 Z0 q2] → [q1 Z0 q2]
[q0 X q0] → [q1 X q0]
[q0 X q1] → [q1 X q1]
[q0 X q2] → [q1 X q2]
[q0 Z0 q0] → a [q0 X q0] [q0 Z0 q0] | a [q0 X q1] [q1 Z0 q0] | a [q0 X q2] [q2 Z0 q0]
[q0 Z0 q1] → a [q0 X q0] [q0 Z0 q1] | a [q0 X q1] [q1 Z0 q1] | a [q0 X q2] [q2 Z0 q1]
[q0 Z0 q2] → a [q0 X q0] [q0 Z0 q2] | a [q0 X q1] [q1 Z0 q2] | a [q0 X q2] [q2 Z0 q2]
[[q0 X q0] → a [q0 X q0] [q0 X q0] | a [q0 X q1] [q1 X q0] | a [q0 X q2] [q2 X q0]
[q0 X q1] → a [q0 X q0] [q0 X q1] | a [q0 X q1] [q1 X q1] | a [q0 X q2] [q2 X q1]
[q0 X q2] → a [q0 X q0] [q0 X q2] | a [q0 X q1] [q1 X q2] | a [q0 X q2] [q2 X q]

The NPDA:

„ M = (Q, Σ, Γ, δ, q0, z, F) „ Q, Σ, δ, q0, and F are the same as they are in

FA „ Γ is a finite set of symbols called the stack alphabet „ z ∈ Γ is the stack
start symbol „ δ: Q×(Σ → Q 𝖴 {λ}) × Γ → finite subset of Q × Γ*.
Ex: δ (q1, a, b) = {(q2, cd), (q3, λ)} Two things can happen when in q1, read
a, and top of the stack is b 1. Move to q2, and the string cd replaces b 2.
Move to q3, and pop b.
*********
 UNIT-V

Turing Machine:

A Turing Machine (TM) is a mathematical model which consists of an

infinite length tape divided into cells on which input is given. It consists of a
head which reads the input tape. A state register stores the state of the
Turing machine. After reading an input symbol, it is replaced with another
symbol, its internal state is changed, and it moves from one cell to the right
or left. If the TM reaches the final state, the input string is accepted,
otherwise rejected.
A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −
 Q is a finite set of states
 X is the tape alphabet
 ∑ is the input alphabet
 δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
 q0 is the initial state
 B is the blank symbol
 F is the set of final states
Ex: Turing machine M = (Q, X, ∑, δ, q0, B, F) with
 Q = {q0, q1, q2, qf}
 X = {a, b}
 ∑ = {1}
 q0 = {q0}
 B = blank symbol
 F = {qf }
δ is given by −
Tape alphabet Present State Present State Present State
symbol ‘q0’ ‘q1’ ‘q2’
a 1Rq 1 1Lq 0 1Lq f
b 1Lq2 1Rq1 1Rqf
Here the transition 1Rq1 implies that the write symbol is 1, the tape moves
right, and the next state is q 1. Similarly, the transition 1Lq 2 implies that the
write symbol is 1, the tape moves left, and the next state is q2.
Example: TM to recognize all strings consisting of an odd number of
α’s.
Ans:
The Turing machine M can be constructed by the following moves −
 Let q1 be the initial state.
 If M is in q1; on scanning α, it enters the state q2 and writes B(blank).
 If M is in q2; on scanning α, it enters the state q1 and writes B(blank).
  From the above moves, we can see that M enters the state q1 if it scans
an even number of α’s, and it enters the state q2 if it scans an odd
number of α’s. Hence q2 is the only accepting state.
Hence,
M = {{q1, q2}, {1}, {1, B}, δ, q1, B, {q2}}
where δ is given by −
Tape alphabet symbol Present State ‘q1’ Present State ‘q2’
α BRq2 BRq1

Example: Design a Turing Machine that reads a string representing a

binary number and erases all leading 0’s in the string. However, if the
string comprises of only 0’s, it keeps one 0.
Ans:
Let us assume that the input string is terminated by a blank symbol, B, at
each end of the string.
The Turing Machine, M, can be constructed by the following moves −
 Let q0 be the initial state.
 If M is in q0, on reading 0, it moves right, enters the state q1 and erases
0. On reading 1, it enters the state q2 and moves right.
 If M is in q1, on reading 0, it moves right and erases 0, i.e., it replaces
0’s by B’s. On reaching the leftmost 1, it enters q2 and moves right. If
it reaches B, i.e., the string comprises of only 0’s, it moves left and
enters the state q3.
 If M is in q2, on reading either 0 or 1, it moves right. On reaching B, it
moves left and enters the state q4. This validates that the string
comprises only of 0’s and 1’s.
 If M is in q3, it replaces B by 0, moves left and reaches the final state qf.
 If M is in q4, on reading either 0 or 1, it moves left. On reaching the
beginning of the string, i.e., when it reads B, it reaches the final
state qf.
Hence,
M = {{q0, q1, q2, q3, q4, qf}, {0,1, B}, {1, B}, δ, q0, B, {qf}}
where δ is given by −
Tape Present Present Present Present Present
alphabet State State State State State
symbol ‘q 0 ’ ‘q 1 ’ ‘q 2 ’ ‘q 3 ’ ‘q4’
0 BRq1 BRq1 ORq2 - OLq4
1 1Rq 2 1Rq 2 1Rq 2 - 1Lq4
B BRq1 BLq3 BLq4 OLqf BRqf

Example: Explain about the Multi-tape Turing Machines and Multi-track

Turing Machines.
Ans:
Multi-tape Turing Machines have multiple tapes where each tape is
accessed with a separate head. Each head can move independently of the
other heads. Initially the input is on tape 1 and others are blank. At first, the
first tape is occupied by the input and the other tapes are kept blank. Next,
the machine reads consecutive symbols under its heads and the TM prints a
symbol on each tape and moves its heads.

A Multi-tape Turing machine can be formally described as a 6-tuple (Q, X, B,

δ, q0, F) where −
 Q is a finite set of states
 X is the tape alphabet
 B is the blank symbol
 δ is a relation on states and symbols where
δ: Q × Xk → Q × (X × {Left_shift, Right_shift, No_shift })k
where there is k number of tapes
 q0 is the initial state
 F is the set of final states
Multi-track Turing machines, a specific type of Multi-tape Turing
machine, contain multiple tracks but just one tape head reads and writes on
all tracks. Here, a single tape head reads n symbols from n tracks at one
step. It accepts recursively enumerable languages like a normal single-track
single-tape Turing Machine accepts.
A Multi-track Turing machine can be formally described as a 6-tuple (Q, X,
∑, δ, q0, F) where −
 Q is a finite set of states
 X is the tape alphabet
 ∑ is the input alphabet
 δ is a relation on states and symbols where
δ(Qi, [a1, a2, a3,....]) = (Qj, [b1, b2, b3,....], Left_shift or Right_shift)
 q0 is the initial state
  F is the set of final states

Linear bounded automaton:

A linear bounded automaton is a multi-track non-deterministic Turing

machine with a tape of some bounded finite length.
Length = function (Length of the initial input string, constant c)
Here,
Memory information ≤ c × Input information
The computation is restricted to the constant bounded area. The input
alphabet contains two special symbols which serve as left end markers and
right end markers which mean the transitions neither move to the left of
the left end marker nor to the right of the right end marker of the tape.
A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q 0, ML,
MR, δ, F) where −
 Q is a finite set of states
 X is the tape alphabet
 ∑ is the input alphabet
 q0 is the initial state
 ML is the left end marker
 MR is the right end marker where MR ≠ ML
 δ is a transition function which maps each pair (state, tape symbol) to
(state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1
 F is the set of final states

A deterministic linear bounded automaton is always context-sensitive and

the linear bounded automaton with empty language is undecidable..
Decidable and Undecidable Language:

A language is called Decidable or Recursive if there is a Turing machine

which accepts and halts on every input string w. Every decidable language
is Turing-Acceptable.
A decision problem P is decidable if the language L of all yes instances to P is
decidable.
For a decidable language, for each input string, the TM halts either at the
accept or the reject state as depicted in the following diagram −

An Undecidable language, there is no Turing Machine which accepts the

language and makes a decision for every input string w (TM can make
decision for some input string though). A decision problem P is called
“undecidable” if the language L of all yes instances to P is not decidable.
Undecidable languages are not recursive languages, but sometimes, they
may be recursively enumerable languages.
Example

 The halting problem of Turing machine

 The mortality problem
 The mortal matrix problem
 The Post correspondence problem, etc.

PCP with Example:

The Post Correspondence Problem (PCP), introduced by Emil Post in

1946, is an undecidable decision problem. The PCP problem over an
alphabet ∑ is stated as follows −
Given the following two lists, M and N of non-empty strings over ∑
− M = (x1, x2, x3,………, xn)
N = (y1, y2, y3,………, yn)
We can say that there is a Post Correspondence Solution, if for some i1,i2,
………… ik, where 1 ≤ i j ≤ n, the condition x i1 …….xik = yi1
…….yik satisfies.
Example
Find whether the lists M = (abb, aa, aaa) and N = (bba, aaa, aa) have a Post
Correspondence Solution?
Solution
x1 x2 x3
M Abb aa aaa
N Bba aaa aa

Here,
x2x1x3 = ‘aaabbaaa’ and y2y1y3 = ‘aaabbaaa’
We can see that
x2x1x3 = y2y1y3
Hence, the solution is i = 2, j = 1, and k = 3.

Chomsky Hierarchy of Languages:

According to Noam Chomosky, there are four types of grammars − Type 0,
Type 1, Type 2, and Type 3. The following table shows how they differ from
each other

Grammar Grammar Language Automaton

Type Accepted Accepted
Type 0 Unrestricted Recursively Turing Machine
grammar enumerable
language
Type 1 Context- Context-sensitive Linear-bounded
 sensitive language automaton
grammar
Type 2 Context-free Context-free Pushdown
grammar language automaton
Type 3 Regular Regular language Finite state
grammar automaton
Take a look at the following illustration. It 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 or 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.

The productions must be in the form A → γ
where A ∈ N (Non terminal)
and γ ∈ (T 𝖴 N)* (String of terminals and non-terminals).
These languages generated by these grammars are be recognized by a non-
deterministic pushdown automaton.
Example
S→Xa
X → a
X → aX
X → abc
X→ε
Type-1 grammars generate context-sensitive languages. The productions
must be in the form
αAβ→αγβ
where A ∈ N (Non-terminal)
and α, β, γ ∈ (T 𝖴 N)* (Strings of terminals and non-terminals)
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 nonterminals 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
 P and NP Problem:

The class P consists of all those decision problems that can be solved on a
deterministic sequential machine in an amount of time that is polynomial in
the size of the input; the class NP consists of all those decision problems
whose positive solutions can be verified in polynomial time.

Universal Turing Machine:

In computer science, a universal Turing machine (UTM) is a Turing

machine that can simulate an arbitrary Turing machine on arbitrary input.
The universal machine essentially achieves this by reading both the
description of the machine to be simulated as well as the input there of
from its own tape.
 A Turing machine is said to be universal Turing machine if it can
accept:
 The input data, and
 An algorithm (description) for computing.
 This is precisely what a general purpose digital computer does. A
digital computer accepts a program written in high level language.
Thus, a general purpose Turing machine will be called a universal
Turing machine if it is powerful enough to simulate the behavior of
any digital computer, including any Turing machine itself.
 More precisely, a universal Turing machine can simulate the behavior
of an arbitrary Turing machine over any set of input symbols. Thus, it
is possible to create a single machine that can be used to compute any
computable sequence.
If this machine is supposed to be supplied with the tape on the
beginning of which is written the input string of quintuple separated
with some special symbol of some computing machine M, then the
 universal Turing machine U will compute the same strings as those by
M.
 The model of a Universal Turing machine is considered to be a
theoretical breakthrough that led to the concept of stored
programmer computing device.
 Designing a general purpose Turing machine is a more complex task.
Once the transition of Turing machine is defined, the machine is
restricted to carrying out one particular type of computation.
 Digital computers, on the other hands, are general purpose machines
that cannot be considered equivalent to general purpose digital
computers until they are designed to be reprogrammed.
 By modifying our basic model of a Turing machine we can design a
universal Turing machine. The modified Turing machine must have a
large number of states for stimulating even a simple behaviour. We
modify our basic model by:
 Increase the number of read/write heads
 Increase the number of dimensions of input tape
 Adding a special purpose memory
 All the above modification in the basic model of a Turing machine will
almost speed up the operations of the machine can do.
 A number of ways can be used to explain to show that Turing machines
are useful models of real computers. Anything that can be computed by
a real computer can also be computed by a Turing machine. A Turing
machine, for example can simulate any type of functions used in
programming language. Recursion and parameter passing are some
typical examples. A Turing machine can also be used to simplify the
statements of an algorithm.
 A Turing machine is not very capable of handling it in a given finite
amount of time. Also, Turing machines are not designed to receive
unbounded input as many real programmers like word processors,
operating system, and other system software.

********
 Unit Wise Question Bank

UNIT I Bloom’s
S.No. Questions COs Taxonomy
Level
What is Automata? Give Formal definition of a CO1 Understanding
1. Finite Automaton.
a)
Define Alphabet ,String and Language. CO1 Understanding

b)
Explain Different types of Automata with an CO1 Understanding
2. Example.
a)
CO1 Understanding
Explain the Difference between NFA and DFA.
b)
Explain Acceptance of NFA/DFA. CO1 Apply
3.
a)
Convert the following NFA to DFA. CO1 Create

b)

Explain Mealy and Moore Machines. CO1 Understanding

4.
a)
Explain the difference between Moore and CO1 Understanding
Mealy Machine.
b)

Convert following Moore machine to Mealy CO1 Create

5. machine.
a)
Present State Next State Output

a=0 a=1

→a d b 1

b a d 0

c c c 0

d b a 1

Construct the minimized DFA following DFA. CO1 Create

b)
 UNIT II Bloom’s
S.No Questions CO Taxonomy
. s Level
Define Regular Languages and Regular CO2 Understandin
1. a) Expression. g
Construct Following RE 1 (0 + 1)* 0 into NFA. CO2 Create

b)
What is a Regular Set? Explain its properties. CO2 Understandin
2. g
a)
Write the Identities Related to Regular Expressions. CO2 Understandin
g
b)
State and Prove Arden's Theorem. CO2 Analyze
3.
a)
Construct a regular expression corresponding CO2 Create
to the automata given below −
b)

CO2 Analyze
State and Explain Pumping Lemma
4.
Applications.
a)
Prove that L = {aibi | i ≥ 0} is not regular. CO2 Analyze

b)
CO2 Understandin
List the Closure properties of Regular sets.
5. g
 UNIT III Bloom’s
S.No. Questions COs Taxonomy
Level
1. a) What is CFG? CO3 Understanding
What is a Derivation? Explain the two CO3 Understanding
b) sentential forms.
2. Explain about Left and Right Recursive CO3 Understanding
a) Grammars.
What is Ambiguous Grammar? CO3 Understanding
b)
3. Check whether the grammar G with CO3 Analyze
a) production rules −
X → X+X | X*X |X| a is ambiguous or not.
Explain about closure properties of CFL. CO3 Analyze
b)
4. Explain about the simplification of CFGs. CO3 Analyze
a)
emove null production from the following − CO3 Analyze
S → ASA | aB | b, A → B, B → b | ∈
b)

Explain Chomsky Normal Form? CO3 Understanding

5. a)
Convert the following CFG into CNF. CO3 Create
b) S → ASA | aB, A → B | S, B → b | ε

6.a) Explain Griebach Normal Form? CO3 Understanding

b) Convert the following CFG into CNF CO3 Analyze
S → XY | Xn | p
X → mX | m
Y → Xn | o

7.a) State Pumping Lemma for CFL and its CO3 Understanding
Applications.

b) Find out whether the language L = {xnynzn | n CO3 Analyze

≥ 1} is context free or not.
 UNIT IV Bloom’s
S.No. Questions COs Taxonomy
Level
1. a) Explain the Basic Structure of PDA. CO4 Understanding

Explain the Instantaneous Description of PDA. CO4 Understanding

b)
2. Explain the Acceptance of Language by PDA. CO4 Analyze
a)
Construct a PDA that accepts L = {0n 1n | n ≥ 0}. CO4 Create
b)
3. Construct a PDA that accepts L = { wwR | w = CO4 Create
a) (a+b)* }

Explain the procedure to convert CFG to PDA. CO4 Understanding

b)
4. Construct a PDA from the following CFG. CO4 Create
a) G = ({S, X}, {a, b}, P, S)
where the productions are −
S → XS | ε , A → aXb | Ab | ab

CO4 Understanding
Explain the procedure to convert PDA to CFG.
b)
Convert a PDA into an equivalent CFG PDA={ CO4 Analyze
5. an bn/n=0}.
a)
Explain about the NPDA. CO4 Understanding
b)
 UNIT V Bloom’s
S.No. Questions COs Taxonomy
Level
1. a) Explain about the Turing Machine CO5 Understanding
Design a TM to recognize all strings consisting of an odd CO5 Create
b) number of
α’s.

2. Design a Turing Machine that reads a string CO5 Create

a) representing a binary number and erases all
leading 0’s in the string. However, if the string
comprises of only 0’s, it keeps one 0.

Explain about the Multi-tape Turing Machines and CO5 Understanding

b) Multi-track Turing Machines.

3. CO5 Understanding
Explain about Linear bounded automaton.
a)

Explain about the Decidable and Undecidable CO5 Understanding

b) Language.
4. Explain PCP with Example? CO5 Analyze
a)
Explain Chomsky Hierarchy of Languages. CO5 Understanding

b)
CO5 Understanding
5. Define P and NP Problem?
a)
Explain about the Universal Turing Machine. CO5 Understanding
b)