Cse Flat Digital Notes Full 2020 21

lOMoARcPSD|23777972
CSE-FLAT Digital Notes-FULL (2020-21)
Computer Science (Jawaharlal Nehru Technological University, Hyderabad)
Studocu is not sponsored or endorsed by any college or university

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)
lOMoARcPSD|23777972
LECTURE NOTES
ON
FORMAL LANGUAGES AND AUTOMATA THEORY
(1805PC07)
III B. Tech I semester (1805PC07)
Prepared by
Dr. SUBBA REDDY Mr. K.V. RAJESH

Professor Assistant Professor
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

MALLAREDDY ENGINEERING COLLEGE FOR WOMEN
(Autonomous Institution-UGC, Govt. of India)
Accredited by NBA & NAAC with ‘A’ Grade, UGC, Govt. of India
NIRF Indian Ranking, Accepted by MHRD, Govt. of India
Rank Band (6th-25th) by ARIIA, Accepted by MHRD, Govt. of India
Approved by AICTE, Affiliated to JNTUH, ISO 9001:2015 Certified Institution
Platinum Rated by AICTE-CII Survey, AAAA+ Rated by Digital Learning Magazine,
AAA+ Rated by Careers 360, National Ranking-Top 100 Rank band by Outlook Magazine,
3rd Rank by CSR, National Ranking-Top 100 Rank band by Times News Magazine,
141 Rank by India Today-Best Engineering Colleges of India Rankings-2020.
Maisammaguda, Dhulapally, Secunderabad, Kompally-500100.
2021 – 2022

lOMoARcPSD|23777972

lOMoARcPSD|23777972
Course Objectives:
The purpose of this course is to acquaint the student with an overview of the theoretical
foundations of computer science from the perspective of formal languages.
• Classify machines by their power to recognize languages.
• Employ finite state machines to solve problems in computing.
• Explain deterministic and non-deterministic machines.
• Comprehend the hierarchy of problems arising in the computer sciences.
Course Outcomes:
• Graduate should be able to understand the concept of abstract machines and their power
to recognize the languages.
• Attains the knowledge of language classes & grammars relationship among them with the
help of Chomsky hierarchy.
• Graduate will be able to understanding the pre - requisites to the course compile

lOMoARcPSD|23777972

lOMoARcPSD|23777972
FORMAL LANGUAGES & AUTOMATA THEORY

(1805PC07)
B. Tech III Year I (Computer Science and Engineering)
UNIT - I
Introduction to Finite Automata: Structural Representations, Central Concepts of Automata

Theory and it’s Applications. Deterministic Finite Automata, Nondeterministic Finite Automata,
Finite Automata with Epsilon-Transitions. Moore and Mealy machine. Equivalence and
minimization of FSM.
UNIT - II
Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular

Expressions, Algebraic Laws for Regular Expressions, Pumping Lemma for Regular Languages,
Applications of the Pumping Lemma, Closure Properties of Regular Language. Equivalence of
FA and Regular expression.
UNIT - III
Context-Free Grammars: Definition , Derivations Using a Grammar, Leftmost and Rightmost

Derivations, the Language of a Grammar, Sentential Forms, Parse Trees, Minimization of
Context-Free Grammar, Ambiguity in Grammars and Languages.
Push Down Automata: Construction of Pushdown Automaton, the Languages of a PDA,

Equivalence of PDA's and CFG's, Deterministic Pushdown Automata.
UNIT - IV
Normal Forms for Context- Free Grammars, Closure Properties of Context-Free Languages.
Types of Normal Forms and it’s conversations.
Introduction to Turing Machines: Turing Machine, Programming Techniques for Turing
Machines, Extensions to the basic Turing Machine, Restricted Turing Machines, Universal
Turing Machine(UTM).

lOMoARcPSD|23777972
UNIT - V
Undecidability: A Language that is Not Recursively Enumerable, An Undecidable Problem

That is RE, Undecidable Problems about Turing Machines, Post's Correspondence Problem,
Intractable Problems: The Classes P and NP, NP- Complete Problem. Rice’s Theorem.
TEXT BOOKS:
1. Introduction to Automata Theory, Languages, and Computation, 3nd Edition, John E.

Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Pearson Education.
2. Introduction to the Theory of Computation, Michael Sipser, 3rd edition, Cengage Learning.
3. Kamala Krithivasan and Rama R, Introduction to Formal Languages, Automata Theory
and Computation, Pearson Education, 2009.
REFERENCE BOOKS:
1. Introduction to Languages and the Theory of Computation, John C Martin, TMH.

2. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
3. A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge Universit

lOMoARcPSD|23777972
INDEX
S.NO
TOPIC NAME PAGE.NO
UNIT – I : Introduction to Finite Automata 1
1.1 Structural Representations 3
1.2 The Central Concepts of Automata Theory 4
1.2.1 Alphabet 4
1.2.2 Strings 4
1.2.3 Languages, Problems 5
1.3 Deterministic Finite Automata 6
1.4 Nondeterministic Finite Automata (NFA) 9
1.5 An Application: Text Search 11
1.6 Finite Automata with Epsilon-Transitions 12
1.7 Equivalence of DFAs and NFAs : 16
1.8 Moore and Mealy Machine 20
1.8.1 Moore Machine to Mealy Machine Algorithm 22
1.8.2 Mealy Machine to Moore Machine Algorithm 23
UNIT-II : Regular Expressions 25
2.1 Finite Automata and Regular Expressions 25
2.2 Applications of Regular Expressions 26
2.3 Algebraic Laws for Regular Expressions 27
2.4 Properties of Regular Languages 28
2.5 Pumping Lemma for Regular Languages 31
2.6 Closure Properties of Regular Languages 33
2.7 Decision Properties of Regular Languages 34
2.8 Equivalence and minimization of automata 35
UNIT-III : CFG 45
3.1 Context-Free Grammars 45
3.2 Definition 47
3.3 Derivations Using a Grammar 47
3.4 Leftmost and rightmost derivations 48
3.5 The language of a grammar 49
3.6 Derivation (or Parse) Tree 49
3.7 Sentential Form 52
3.8 Ambiguity in Context Free Grammar 54
3.9 Pushdown Automata (PDA) 59
3.9.1 Instantaneous Description (ID) of PDA 61
3.9.2 Construction of PUSH DOWN AUTOMATA 61
3.9.3 PDA Acceptance 64
3.10 The Languages of a PDA 66
3.11 Equivalence of PDA's and CFG's 67
3.11.1 CFG to PDA Conversion 67
3.11.2 PDA to CFG Conversion 71

lOMoARcPSD|23777972
3.12 Deterministic PDAs and DCFLs 71

Unit IV: TURING MACHINE & NORMAL FORMS
4.1 Normal form 74
4.2 Simplifying Context Free Grammars 74
4.2.1 Useless productions 74
4.2.2 DEL: Eliminate ε-rules 75
4.2.3 UNIT: Eliminate unit Productions 76
4.3 Closure Properties of CFL 78
4.4 Converting C F G to C N F 80
4.5 Converting C F G to G N F 87
TURING MACHINE 91
4.6 Formal definition of Turing machine 91
4.7 BASIC MODEL OF TURING MACHINE 92
4.8 LANGUAGE ACCEPTED BY TURING MACHINE 93
4.9 PROGRAMING TECHNIQUES FOR TURING MACHINE 96
4.10 Extensions to Basic Turing Machine 111
4.11 Universal Turing Machine: 114
Unit V: UNDECIDABILITY
5.1 Decidability of problems 115
5.2 Un decidable problem about Turing machine 115
5.2.1 Reduction 115
5.2.2 Theorem 115
5.2.3 Halting problem 116
5.3 Post’s Correspondence Problem 117
5.4 The classes of P and NP problem 118
5.4.1 The classes of language P 118
5.4.2 Kruskal’s Algorithm 119
5.4.3 The classes of language NP 119
5.4.4 Travelling Salesman’s Problem 119
5.5 RICE Theorm 115
Assignment Questions 122
Tutorial Questions 129
Important Questions 136
Objective Questions 142
Internal Question papers 178
External Question papers 180
References 184

lOMoARcPSD|23777972

lOMoARcPSD|23777972
Formal Languages & Automata Theory Department of CSE
UNIT-I
Introduction to Finite Automata
What is Automata?
Automata theory is the study of abstract machine and automata. It is a theory in theoretical
computer science, under discrete mathematics. The word automata (the plural of automaton)
come from the Greek word “avtouata” which means "self-acting".
Automatons are abstract models of machines that perform computations on an input by moving
through a series of states or configurations. At each state of the computation, a transition
function determines the next configuration on the basis of a finite portion of the present
configuration. As a result, once the computation reaches an accepting configuration, it accepts
that input. The most general and powerful automata is the Turing machine.
The major objective of automata theory is to develop methods by which computer scientists can
describe and analyze the dynamic behavior of discrete systems, in which signals are sampled
periodically. The behavior of these discrete systems is determined by the way that the system is
constructed from storage and combinational elements. Characteristics of such machines include:
• Inputs: assumed to be sequences of symbols selected from a finite set I of input signals.
Namely, set I is the set {x1, x,2, x3... xk} where k is the number of inputs.
• Outputs: sequences of symbols selected from a finite set Z. Namely, set Z is the set {y1,
y2, y3 ... ym} where m is the number of outputs.
• States: finite set Q, whose definition depends on the type of automaton.
Finite State Machines
• A finite state machine has a set of states and two functions called the next-state function
and the output function
• The set of states correspond to all the possible combinations of the internal storage
if there are n bits of storage, there are2npossible states
MRECW (Autonomous Institution-UGC, Govt. of India) Page 1

lOMoARcPSD|23777972
• The next state function is a combinational logic function that given the inputs and the
current state, determines the next state of the system
• The output function produces a set of outputs from the current state and the inputs
– There are two types of finite state machines
– In a Moore machine, the output only depends on the current state
– WhileinaMealymachine,theoutputdependsboththecurrentstateandthecurrent input
– We are only going to deal with the Moore machine.
– These two types are equivalent in capabilities
• A Finite State Machine consists of:
K states: S ={s1, s2, … ,sk},s1is initial state N
inputs: I={i1, i2, … ,in}
M outputs: O = {o1, o2, … ,om}
Next-state function T(S, I) mapping each current state and input to next state
Output Function P(S) specifies output
Finite Automata
• Two types– both describe what are called regular languages

– Deterministic(DFA)–There is a fixed number of states and we can only be in
one state at a time
– Nondeterministic(NFA)–There is a fixed number of states but we can be in
multiple states at one time
While NFA’s are more expressive than DFA’s, we will see that adding non-determinism does not
let us define any language that cannot be defined by a DFA.
One way to think of this is we might write a program using a NFA, but then when it is
“Compiled” we turn the NFA into an equivalent DFA.

lOMoARcPSD|23777972
1.1 Structural Representations

Formal Definition of a Finite Automaton
1. Finite set of states, typically Q.

2. Alphabet of input symbols, typically∑
3. One state is the start/initial state, typicallyq0 // q0∈Q
4. Zero or more final/accepting states; the set is typically F. // F ⊆Q
5. A transition function, typically δ.
This function
• Takes a state and input symbol as arguments.
• The most important feature of the automaton is its control unit, which can be in any one of
a finite number of interval states at any point. It can change state in some defined manner
determined by a transition function.
Fig1: The figure above shows a diagrammatic representation of a generic automation.
Let us first give some intuitive idea about a state of a system and state transitions before
describing finite automata.
Informally, a state of a system is an instantaneous description of that system which gives all
relevant information necessary to determine how the system can evolve from that point on.

lOMoARcPSD|23777972
Transitions are changes of states that can occur spontaneously or in response to inputs to the
States. Though transitions usually take time, we assume that state transitions are instantaneous
(which is an abstraction).
Some examples of state transition systems are: digital systems, vending machines, etc. A system
containing only a finite number of states and transitions among them is called a finite-state
transition system. Finite-state transition systems can be modeled abstractly by a mathematical
model called finite automation.
1.2 The Central Concepts of Automata Theory:
1.2.1 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.
1.2.2 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}
Length of a String
• Definition − It is the number of symbols present in a string. (Denoted by |S|).
• Examples −
o If S = ‘cabcad’, |S|= 6
o If |S|= 0, it is called an empty string (Denoted by λ or ε)
Kleene Star
• Definition − The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑,
that gives the infinite set of all possible strings of all possible lengths over ∑including λ.
• Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set of all possible strings of
length p.
• Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..}

lOMoARcPSD|23777972
Kleene Closure / Plus

• Definition − The set ∑+ is the infinite set of all possible strings of all possible lengths
over ∑ excluding λ.
• Representation − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….
∑+ = ∑* − { λ }
• Example − If ∑ = { a, b } , ∑+ = { a, b, aa, ab, ba, bb,………..}
1.2.3 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}
1.3Deterministic Finite (-state) Automata

Informally, a DFA (Deterministic Finite State Automaton) is a simple machine that reads an
input string -- one symbol at a time -- and then, after the input has been completely read, decides
whether to accept or reject the input. As the symbols are read from the tape, the automaton can
change its state, to reflect how it reacts to what it has seen so far. A machine for which a
deterministic code can be formulated, and if there is only one unique way to formulate the code,
then the machine is called deterministic finite automata.
Thus, a DFA conceptually consists of 3 parts:

1. A tape to hold the input string. The tape is divided into a finite number of cells. Each cell
holds a symbol from.
2. A tape head for reading symbols from the tape
3. A control, which itself consists of 3 things:
• finite number of states that the machine is allowed to be in (zero or more states are
designated as accept or final states),
• a current state, initially set to a start state,
• A state transition functions for changing the current state.

lOMoARcPSD|23777972
An automaton processes a string on the tape by repeating the following actions until the tape
head has traversed the entire string:
1. The tape head reads the current tape cell and sends the symbol s found there to the
control. Then the tape head moves to the next cell.
2. He control takes s and the current state and consults the state transition function to get
the next state, which becomes the new current state.
Once the entire string has been processed, the state in which the automation enters is examined.
If it is an accept state, the input string is accepted; otherwise, the string is rejected . Summarizing
Deterministic Finite Automata (DFA):
• A DFA is a five- tuple: M=(Q, Σ, į, q0,F)

Q A finite set of states
Σ A finite input alphabet
q0 The initial/starting state, q0is in Q
F A set of final/accepting states, which is a subset of Q
į A transition function, which is a total function from Q x Σ to Q
į:(Q x Σ)–>Q į is defined for any q in Q and s in Σ, and
į(q,s) =q’ is equal to another state q’ in Q.
Intuitively, į(q,s)is the state entered by M after reading symbols while in state q.
Notes:
• ADFAM= (Q, Σ, į, q0, F) partitions the set Σ* into two sets: L(M) and Σ*-L(M).
• If L=L(M) then L is a subset of L(M) and L(M) is a subset of L.
• Similarly, if L(M1)=L(M2) then L(M1) is as ubset of L(M2) and L(M2)is a subset of
L(M1).
• Some languages are regular, others are not.
For example, if
L1= {x|x is a string of 0's and1's containing an even number of 1's}andL2={x|x=0 n1n for some
n >= 0} Then L1 is regular but L2 is not.

lOMoARcPSD|23777972

lOMoARcPSD|23777972
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 −

lOMoARcPSD|23777972
1.4 Nondeterministic Finite Automata (NFA):
•An NFA is a five-tuple: M = (Q, Σ, δ, q0, F)
Q A finite set of states.

q0 The initial/starting state, q0 is in Q
Δ A transition function, which is a total function from Q x Σ to 2Q
δ: (Q x Σ) -> 2Q -2Q is the power set of Q, the set of all subsets of Q
δ (q,s) -The set of all states p such that there is a transition
Labeled s from q to p
δ (q,s) is a function from Q x S to 2Q (but not to Q)
• Let M = (Q, Σ, δ,q0 ,F) be an NFA and let w be in Σ*. Then w is accepted by M iff δ({q0}, w)
contains at least one state in F.
• Let M = (Q, Σ, δ, q0 ,F) be an NFA. Then the language accepted by M is the set: L(M) = {w |
w is in Σ* and δ({q0},w) contains at least one state in F}
• Another equivalent definition:
L(M) = {w | w is in Σ* and w is accepted by M}

lOMoARcPSD|23777972
TRANSITION DIAGRAMS:

lOMoARcPSD|23777972
1.5 An Application: Text Search Suppose we are given a set of words, called keywords, and we
want to find occurences of any of these words. For such a problem, a useful way to proceed is to
design a NFA which recognizes, by entering in an accepting state, that it has seen one of the
keywords. The NFA is only a nondeterministic program, but we can run it using lists or
transform it to a DFA and get a deterministic (efficient) program Once again, we know that this
DFA will be correct by construction This is a good example of a derivation of a program (DFA)
from a specification (NFA)
The following NFA searches for the keyword web and eBay
w e b
B C
D
A
e
E b a y
F G H
Almost no thinking needed to write this NFA What is a corresponding DFA?? Notice that this
has the same number of states as the NFA
Representation in functional programming
run: String -> Q -> [Q]
run [] q = return q
run (a:x) q = next a q >>= run x
Final:: Q -> Bool
Final D = True
Final H = True
Final _ = False
Accept:: String -> Bool

lOMoARcPSD|23777972
Accept x = or (map final (run x A))
Even for searching an occurence of one keyword this gives an interesting program This is
connected to the Knuth-Morris-Pratt string searching algorithm Better than the naive string
searching algorithm
1.6 Finite Automata with Epsilon-Transitions:
• An NFA-ε is a five-tuple: M = (Q, Σ, δ, q0, F)
Q A finite set of states

q0 The initial/starting state, q0 is in Q
δ A transition function, which is a total function from Q x Σ U {ε} to 2Q
δ: (Q x (Σ U {ε})) –> 2Q
δ(q,s) -The set of all states p such that there is a transition labeled a from q to p, where a
is in Σ U {ε}
• Sometimes referred to as an NFA-ε other times, simply as an NFA.

lOMoARcPSD|23777972
• Let M = (Q, Σ, δ,q0,F) be an NFA-ε and let w be in Σ*. Then w is accepted by M iff δ^({q0},
w) contains at least one state in F.
• Let M = (Q, Σ, δ,q0,F) be an NFA-ε. Then the language accepted by M is the set:
L(M) = {w | w is in Σ* and δ^({q0},w) contains at least one state in F} 40
• Another equivalent definition: L(M) = {w | w is in Σ* and w is accepted by M}

Equivalence of NFA and NFA-ε:
• Do NFAs and NFA-ε machines accept the same class of languages?
– Is there a language L that is accepted by a NFA, but not by any NFA-ε?

– Is there a language L that is accepted by an NFA-ε, but not by any DFA?
• Observation: Every NFA is an NFA-ε.
• Therefore, if L is a regular language then there exists an NFA-ε M such that L = L(M).
• It follows that NFA-ε machines accept all regular languages.
• But do NFA-ε machines accept more?

• Lemma 1: Let M be an NFA. Then there exists a NFA-ε M’ such that L(M) = L(M’).
• Proof: Every NFA is an NFA-ε. Hence, if we let M’ = M, then it follows that L(M’) =
L(M).
• Lemma 2: Let M be an NFA-ε. Then there exists a NFA M’ such that L(M) = L(M’).
• Proof:
Let M = (Q, Σ, δ, q0, F) be an NFA-ε.
Define an NFA M’ = (Q, Σ, δ’, q0, F’) as:
F’ = F U {q0} if ε-closure (q0) contains at least one state from F
F’ = F otherwise
δ’(q, a) = δ^(q, a) - for all q in Q and a in Σ

lOMoARcPSD|23777972
Notes:
δ’: (Q x Σ) –> 2Q is a function
M’ has the same state set, the same alphabet, and the same start state as M
M’ has no ε transitions

lOMoARcPSD|23777972

lOMoARcPSD|23777972
• Theorem: Let L be a language. Then there exists an NFA M such that L= L(M) iff there exists an
NFA-ε M’ such that L = L(M’).
• Proof:
(if) Suppose there exists an NFA-ε M’ such that L = L(M’). Then by Lemma 2 there exists an NFA
M such that L = L(M).
(only if) Suppose there exists an NFA M such that L = L(M). Then by Lemma 1 there exists an NFA-
ε M’ such that L = L(M’).
• Corollary: The NFA-ε machines define the regular languages.
1.7 Equivalence of DFAs and NFAs :

• Do DFAs and NFAs accept the same class of languages?
– Is there a language L that is accepted by a DFA, but not by any NFA?
– Is there a language L that is accepted by an NFA, but not by any DFA?

lOMoARcPSD|23777972
• Observation: Every DFA is an NFA.
• Therefore, if L is a regular language then there exists an NFA M such that L = L(M).
• It follows that NFAs accept all regular languages. But do NFAs accept all?

lOMoARcPSD|23777972
• Lemma 1: Let M be a DFA. Then there exists a NFA M’ such that L(M) = L(M’).
• Proof: Every DFA is an NFA. Hence, if we let M’ = M, then it follows that L(M’) = L(M).
The above is just a formal statement of the observation from the above example.
• Lemma 2: Let M be an NFA. Then there exists a DFA M’ such that L(M) = L(M’).
• Proof: (sketch)
Let M = (Q, Σ, δ, q0, F).
Define a DFA M’ = (Q’, Σ, δ’, q0, F’) as:
Q’ = 2Q each state in M’ corresponds to a
= {Q0, Q1,…,} subset of states from M
Where Qu = [qi0, qi1,…qij]
F’ = {Qu | Qu contains at least one state in F}
q0 = [q0]
δ’(Qu, a) = Qv iff δ(Qu, a) = Qv

lOMoARcPSD|23777972

lOMoARcPSD|23777972
1.8 MOORE and MEALY MACHINE
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 diagram of a Mealy Machine is shown below −

lOMoARcPSD|23777972
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 diagram of a Moore Machine is shown below −
Mealy Machine vs. Moore Machine
The following table highlights the points that differentiate a Mealy Machine from a
Moore Machine.

lOMoARcPSD|23777972
Mealy Machine Moore Machine

1)Output depends both upon present state and Output depends only upon the present state.
present input.Generally, it has fewer states Generally it has more states than Mealy m/c
than Moore Machine
2)Output changes at the clock edges. Input change can cause change in output
change as soon as logic is done.
3)Mealy machines react faster to inputs. In Moore machines, more logic is needed
to decode the outputs since it has more
circuit delays.
1.8.1 Moore Machine to Mealy Machine Algorithm
Input: Moore Machine
Output: Mealy Machine
Step 1 Take a blank Mealy Machine transition table format.

Step 2 Copy all the Moore Machine transition states into this table format..
Step 3 Check the present states and their corresponding outputs in the Moore
Machine state table; if for a state Qi output is m, copy it into the output
columns of the Mealy Machine state table wherever Qi appears in the next
state..
Example
Let us consider the following Moore machine −
Next State
Present a=0 a=1 Output
State
→a d b 1
b a d 0
c c c 0
d b a 1

lOMoARcPSD|23777972

Now we apply Algorithm 4 to convert it to Mealy Machine.
Step 1 & 2
Next State
Present State a=0 a=1
State Output State Output

→a d b
B a d
c c c
d b a
Step 3
Next State
State Output State Output

⇒a d 1 b 0
b a 1 d 1
c c 0 c 0
d b 0 a 1
1.8.2 Mealy Machine to Moore Machine Algorithm
Input: Mealy Machine
Output: Moore Machine
Step 1 Calculate the number of different outputs for each state (Qi) that are
available in the state table of the Mealy machine.
Step 2 If all the outputs of Qi are same, copy state Qi. If it has n distinct
outputs, break Qi into n states as Qin where n = 0, 1, 2....…

lOMoARcPSD|23777972
Step 3 If the output of the initial state is 1, insert a new initial state at the
beginning which gives 0 output.
Example
Let us consider the following Mealy Machine −

Next State
Output Output
Next State Next State
→a d 0 b 1
b a 1 d 0
c c 1 c 0
d b 0 a 1
Here, 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 1and 0. So, we divide b into b0, b1 and c
into c0, c1.
Next State
Present 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

lOMoARcPSD|23777972
Unit II
Regular Expressions
• A regular expression is used to specify a language, and it does so precisely.

• Regular expressions are very intuitive.
• Regular expressions are very useful in a variety of contexts.
• Given a regular expression, an NFA-İ can be constructed from it automatically.
• Thus, so can an NFA, a DFA, and a corresponding program, all automatically!
2.1 Finite Automata and Regular Expressions
Definition:
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))*
• If we apply any of the rules several times from 1 to 5, they are Regular Expressions.

lOMoARcPSD|23777972
• Let Σ be an alphabet. The regular expressions over Σ are:
– Ø Represents the empty set{ }

– İ Represents the set{İ}
– a Represents the set {a},for any symbol a in Σ
Let r and s be regular expressions that represent the sets Rand S, respectively.
– r+s Represents the set R U (precedence 3)

– rs SRepresents the set RS (precedence 2)
– r * Represents the set R* (highest precedence)
– (r) Represents the set R (not an op, provides precedence)
• I fr is a regular expression, then L(r) is used to denote the corresponding language.
• Examples:LetΣ ={0, 1}
(0 +1)* All strings of 0’sand 1’s

0(0 +1)* All strings of 0’sand 1’s, beginning with a 0
(0 +1)*1 All strings of 0’sand 1’s, ending with a 1
(0 +1)*0(0+1)* All strings of 0’sand 1’scontainingatleast one 0(0
+1)*0(0+ 1)*0(0+1)* All strings of 0’sand 1’scontainingatleast two 0’s(0
+1)*01*01* All strings of 0’sand 1’scontainingatleast two 0’s(1
+01*0)* All strings of 0’sand 1’s containing an even number
of0’s1*(01*01*)* All strings of 0’sand 1’s containing an even number
of0’s(1*01*0)*1* All strings of 0’sand 1’s containing an even number of0’s
2.2 Applications of Regular Expressions:
It is defined as representing a regular expression in terms of regular language.

• ϕ is regular expression then regular language is { }.
• ϵϵ is a regular expression then regular language is {ϵ}.

lOMoARcPSD|23777972
• r is regular expression then regular language {r}.

• Let R and S be regular expression then regular language be LRLR and LSLS.
• R + S or R|S be regular expression then regular language is LRLR U LSLS.
• R . S be regular expression then regular language is LR.LSLR.LS.
• R* be regular language then regular expression is LR*.
• R+R+ be regular language then regular expression is L+RLR+.
Applications:
• Regular expressions are useful in a wide variety of text processing tasks, and more
generally string processing, where the data need not be textual. Common applications
include data validation, data scraping (especially web scraping), data wrangling, simple
parsing, the production of syntax highlighting systems, and many other tasks.
• While reg exps would be useful on Internet search engines, processing them across
the entire database could consume excessive computer resources depending on the
complexity and design of the regex.
2.3 Algebraic Laws for Regular Expressions
1. Øu =uØ =Ø Multiplyby0
2. İu=uİ=u Multiplyby1
3. Ø*=İ
4. İ*=İ
5. u+v = v+u
6. u +Ø =u
7. u +u =u
8. u* = (u*)*
9. u(v+w) = uv+uw
10. (u+v)w = uw+vw
11. (uv)*u=u(vu)*12.
(u+v)* = (u*+v)*
= u*(u+v)*
= (u+vu*)

lOMoARcPSD|23777972
= (u*v*)*
= u*(vu*)*
= (u*v)*u
2.4 Properties of Regular Languages
Our main goal is to identify some basic closure properties of regular languages.
• We will be interested in the following types of closure properties.
• Suppose you give me two arbitrary regular languages L and L'.
• Suppose I perform some kind of operation on L and L' such as the set union operation.
• We want to know if the resulting language L union L' is guaranteed to still be regular.
• If it is, we say the class of regular languages has the property of being closed under the set
union operation.
• We will often abbreviate this to say that the class of regular languages is closed under
union.
A second goal is to illustrate the basic methods used to prove such closure properties.
• First, we must define the operation (e.g. set union, set complement) we are interested in.
• We will then create a generic element proof to show that the class of regular languages is
closed under the particular operation.
• Key point:
▪ Note we apply these set operations to individual languages (sets of strings) rather
than to language classes (sets of sets).
▪ However, we are interested in whether or not the resulting language (set of strings)
is still a member of a language class (set of sets).
The Complement Operation:
Definition
The complement Sc of a set S is defined to be the set of all elements of the universe U that are not
elements of S.
Note complement is a unary operator; that is, it is a function on a single input.
In contrast, set union is a binary operator; that is, set union is a function on two inputs.
Examples of languages L (sets of strings) and their complements Lc.

lOMoARcPSD|23777972
*
L=
Lc = {}.
L = {the set of strings of even length}
Lc = {the set of strings not of even length} = {the set of strings of odd length}.
L = {the set of strings beginning with 01}
Lc = {the set of strings not beginning with 01} = {the set of strings beginning with 00, 10, 11}
union {0, 1, }
Generic element proof that the class of regular languages is closed under complement.
Observation:
▪ Looking at the proof, we see that a regular language L and its complement Lc are
arguably identical in complexity since essentially the same FA can recognize either
language.
▪ This is NOT always the case for other classes of languages, a fact we will see in the
next section on context free languages.
Questions
1) What does the statement that the regular languages are closed under complement mean?
2) Suppose L is a non-regular language. Can we conclude that Lc is not regular?
The Union Operation:

Definition
• S union S' of sets S and S' is defined to be the set of all elements of the universe U that
are either elements of S or S'.
▪ Note union is a binary operator; that is, it is a function on two inputs.
▪ In contrast, set complement is a unary operator; that is, set complement is a function
on one input.
• Examples of languages L and L' (sets of strings) and their unions L union L'.
▪ L ={aab,aaba,aabaa}
L' ={b,aaba,bbb}
L union L' = {aab,aaba,aabaa,b,bbb}

lOMoARcPSD|23777972
▪ L is any language
L' = Lc, the complement of L
*
L union L' =
▪ L = {the set of strings beginning with 01}
L' = {the set of strings beginning with 00}
L union L' = {the set of strings beginning with 0 except 0 itself}
Generic element proof that the class of regular languages is closed under union.
Questions
3) What does the statement that the regular languages are closed under set union mean?
4) Suppose L and L' are non-regular languages. Can we conclude that L union L' is not regular?
The Intersection Operation:

Definition
S intersection S' of sets S and S' is defined to be the set of all elements of the universe U that are
elements of both S and S'.
• Note intersection is a binary operator; that is, it is a function on two inputs.
Examples of languages L and L' (sets of strings) and their intersection L intersection L'.
• L ={aab,aaba,aabaa}
L' ={b,aaba,bbb}
L intersection L' = {aaba}
• L is any language L' = Lc, the complement of L L intersection L' = {}
• L ={the set of strings beginning with 0}
L' ={the set of strings ending with 0}
L intersection L' = {the set of strings beginning with 0 and ending with 0}
Generic element proof that the class of regular languages is closed under intersection.
Questions
5) What does the statement that the regular languages are closed under set intersection mean?
6) Suppose L and L' are non-regular languages. Can we conclude that L intersection L' is not
regular?

lOMoARcPSD|23777972
The Set Difference Operator -
Definition:
S - S' is defined to be the set of all elements of the universe U that are elements
of S but not elements of S'.
▪ Note set difference is a binary operator; that is, it is a function on two inputs.
Examples of languages L and L' (sets of strings) and their difference L - L'.
▪ L ={aab,aaba,aabaa}
L' ={b,aaba,bbb}
L - L' = {aab,aabaa}
▪ L is any language
L' = Lc, the complement of L
L - L' = L
▪ L = {the set of strings beginning with 0}
L' = {the set of strings ending with 0}
L - L' = {the set of strings beginning with 0 which do not end with 0}
Examine the generic element proof that the class of regular languages is closed under intersection
and determine how to modify it to show that the class of regular languages is closed under set
difference.
2.5 Pumping Lemma for Regular Languages:
• Pumping Lemma relates the size of string accepted with the number of states in a DFA
• What is the largest string accepted by a DFA with n state?
• Suppose there is no loop?
Now, if there is a loop, what type of strings is accepted via the loop(s)?
• Lemma: (the pumping lemma)
Let M be a DFA with |Q|=n states. If there exists a string x in L(M), such that |x| n, then
there exists a way to write it as x=uvw, where u, v, and w are all in Σ*and:
– 1 |uv| n
– |v| 1
– Such that, the strings uviw are also in L(M), for all i 0

lOMoARcPSD|23777972

lOMoARcPSD|23777972
• Let:
– u = a1…as
– v = as+1…at
• Since 0 s<t n and uv = a1…at it follows that:
–1 |v| and therefore 1 |uv|
– |uv| n and therefore 1 |uv| n
• In addition, let:
– w = at+1…am
• It follows that uviw = a1…as(as+1…at)iat+1…am is in L(M), for all i 0.
In other words, when processing the accepted string x, the loop was traversed once, but could
have been traversed as many times as desired, and the resulting string would still be accepted.
2.6 Closure Properties of Regular Languages
1. Closure under Union
If L and M are regular languages, so is L ⋃ M.

lOMoARcPSD|23777972
Proof: Let L and M be the languages of regular expressions R and S, respectively.
Then R+S is a regular expression whose language is L ⋃ M.
2. Closure under Concatenation and Kleene Closure
RS is a regular expression whose language is LM.
R* is a regular expression whose language is L*.
3. Closure under Intersection
If L and M are regular languages, then so is L ⋂ M.
Proof: Let A and B be DFA’s whose languages are L and M, respectively.
4. Closure under Difference
If L and M are regular languages, then so is L – M = strings in L but not M.
Proof: Let A and B be DFA’s whose languages are L and M, respectively.
5. Closure under Complementation
The complement of language L (w.r.t. an alphabet Σ such that Σ* contains L) is Σ* – L.
Since Σ* is surely regular, the complement of a regular language is always regular.
6. Closure Under Homomorphism
If L is a regular language, and h is a homomorphism on its alphabet, then h(L) = {h(w) | w is in

L} is also a regular language.
2.7 Decision Properties of Regular Languages
A decision property for a class of languages is an algorithm that takes a formal description of a
language (e.g., a DFA) and tells whether or not some property holds.
Example: Is language L empty?
• Representation Matters You might imagine that the language is described informally, so
if my description is “the empty language” then yes, otherwise no. But the representation is a

lOMoARcPSD|23777972
DFA (or a RE that you will convert to a DFA). for DFA A?Can you tell if L(A) =
Why Decision Properties?
• When we talked about protocols represented as DFA’s, we noted that important

properties of a good protocol were related to the language of the DFA.
▪ Example: “Does the protocol terminate?” = “Is the language finite?”
▪ Example: “Can the protocol fail?” = “Is the language nonempty?”
• We might want a “smallest” representation for a language, e.g., a minimum-state DFA

or a shortest RE.
• If you can’t decide “Are these two languages the same?”
• I.e., do two DFA’s define the same language? You can’t find a “smallest.”
2.8 Equivalence and minimization of automata

• Note: Throughout the following, keep in mind that a string is accepted by an NFA-ε if there
exists a path from the start state to a final state.
• Lemma 1: Let r be a regular expression. Then there exists an NFA-ε M such that L(M) = L(r).
Furthermore, M has exactly one final state with no transitions out of it.
• Proof: (by induction on the number of operators, denoted by OP(r), in r).
• Basis: OP(r) = 0
Then r is either Ø, ε, or a, for some symbol a in Σ

lOMoARcPSD|23777972
• Inductive Hypothesis: Suppose there exists a k 0 such that for any regular expression r
where 0 OP(r) k, there exists an NFA-ε such that L(M) = L(r). Furthermore, suppose that M
has exactly one final state.
• Inductive Step: Let r be a regular expression with k + 1 operators (OP(r) = k + 1), where k + 1
>= 1.
Case 1) r = r1 + r2
Since OP(r) = k +1, it follows that 0<= OP(r1), OP(r2) <= k. By the inductive hypothesis there
exist NFA-ε machines M1 and M2 such that L(M1) = L(r1) and L(M2) = L(r2). Furthermore,
both M1 and M2 have exactly one final state.
Case 2) r = r1r2
Since OP(r) = k+1, it follows that 0<= OP(r1), OP(r2) <= k. By the inductive hypothesis there
exist NFA-ε machines M1 and M2 such that L(M1) = L(r1) and L(M2) = L(r2). Furthermore,
both M1 and M2 have exactly one final state.

lOMoARcPSD|23777972
Case 3) r = r1*
Since OP(r) = k+1, it follows that 0<= OP(r1) <= k. By the inductive hypothesis there exists an NFA-
ε machine M1 such that L(M1) = L(r1). Furthermore, M1 has exactly one final state.
Example:
Problem: Construct FA equivalent to RE, r = 0(0+1)*
Solution: r = r1r2
r1 = 0
r2 = (0+1)*
r2 = r3*
r3 = 0+1
r3 = r4 + r5
r4 = 0
r5 = 1
Transition graph:
Definitions Required to Convert a DFA to a Regular Expression

• Let M = (Q, Σ, δ, q1, F) be a DFA with state set Q = {q1, q2, …, qn}, and define:

lOMoARcPSD|23777972
Ri,j = { x | x is in Σ* and δ(qi,x) = qj}

Ri,j is the set of all strings that define a path in M from qi to qj.
• Note that states have been numbered starting at 1!
• Observations:
Arden’s Theorem:
In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along
with the properties of regular expressions.
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*

lOMoARcPSD|23777972
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.
Assumptions for Applying Arden’s Theorem
• The transition diagram must not have NULL transitions
• It must have only one initial state
Method
Step 1 − Create equations as the following form for all the states of the DFA having n states with
initial state q1.
q1 = q1R11 + q2R21 + … + qnRn1 + ε
q2 = q1R12 + q2R22 + … + qnRn2
…………………………
…………………………
…………………………
…………………………
qn = q1R1n + q2R2n + … + qnRnn
Rij represents the set of labels of edges from qi to qj, if no such edge exists, then Rij = ∅
Step 2 − Solve these equations to get the equation for the final state in terms of Rij
We can use Thompson's Construction to find out a Finite Automaton from a Regular Expression.
We will reduce the regular expression into smallest regular expressions and converting these to
NFA and finally to DFA.
Some basic RA expressions are the following –

lOMoARcPSD|23777972
Case 1 − For a regular expression ‘a’, we can construct the following FA –
Case 2 − For a regular expression ‘ab’, we can construct the following FA –
Case 3 − For a regular expression (a+b), we can construct the following FA –

lOMoARcPSD|23777972
Case 4 − For a regular expression (a+b)*, we can construct the following FA –
Method
Step 1 Construct an NFA with Null moves from the given regular expression.
Step 2 Remove Null transition from the NFA and convert it into its equivalent DFA.
Problem
Convert the following RA into its equivalent DFA − 1 (0 + 1)* 0
Solution
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 −
It is an NDFA corresponding to the RE − 1 (0 + 1)* 0. If you want to convert it into a DFA,.

lOMoARcPSD|23777972
Finite Automata with Null Moves (NFA-ε)
A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the
alphabet set but also without any input symbol. This transition without input is called a null
move.
An NFA-ε is represented formally by a 5-tuple (Q, ∑, δ, q0, F), consisting of
• Q − a finite set of states
• ∑ − a finite set of input symbols
• δ − a transition function δ : Q × (∑ ∪ {ε}) → 2Q
• q0 − an initial state q0 ∈ Q
• F − a set of final state/states of Q (F⊆Q).
The above (FA-ε) accepts a string set − {0, 1, 01}
Removal of Null Moves from Finite Automata
If in an NDFA, there is ϵ-move between vertex X to vertex Y, we can remove it using the
following steps −
• Find all the outgoing edges from Y.
• Copy all these edges starting from X without changing the edge labels.
• If X is an initial state, make Y also an initial state.
• If Y is a final state, make X also a final state.
Problem
Convert the following NFA-ε to NFA without Null move.

lOMoARcPSD|23777972
Solution
Step 1 −
Here the ε transition is between q1 and q2, so let q1 is Xand qf is Y.
Here the outgoing edges from qf is to qf for inputs 0 and 1.
Step 2 −
Now we will Copy all these edges from q1 without changing the edges from qf and get the
following FA −

lOMoARcPSD|23777972
Step 3 −
Here q1 is an initial state, so we make qf also an initial state.
So the FA becomes −
Step 4 −
Here qf is a final state, so we make q1 also a final state.
So the FA becomes −

lOMoARcPSD|23777972
Unit III
CONTEXT-FREE GRAMMARS
3.1 REGULAR GRAMMAR
A linear grammar is a grammar in which at most one variable can occur on the right side of any
production without restriction on the position of this variable.
An example of linear grammar is G = ({S, S1, S2}, {a, b}, S, P) with
S ->S1ab,
S1 -> S1ab | S2,
S2 ->a.
A regular grammar is one that is either right-linear or left-liner.
Testing Equivalence of Regular Languages
Let L and M be reg langs (each given in some form).
To test if L = M
1. Convert both L and M to DFA's.
2. Imagine the DFA that is the union of the two DFA's (never mind there are two start states)
3. If TF-algo says that the two start states are distinguishable, then L 6= M, otherwise, L = M.
Example:

lOMoARcPSD|23777972
We can “see" that both DFA accept L(ε+(0+1)*0). The result of the TF-algo is
Therefore the two automata are equivalent.
Regular Grammars and NFA's
• It's not hard to show that regular grammars generate and nfa's accept the same class of
languages: the regular languages!
• It's a long proof, where we must show that
• Any finite automaton has a corresponding left- or right-linear grammar,
• And any regular grammar has a corresponding nfa.
• Example:
We get a feel for this by example.

lOMoARcPSD|23777972
Let S → aA A → abS | b
3.2CONTEXT FREE-GRAMMAR
Definition − A context-free grammar (CFG) consisting of a finite set of grammar rules is a

quadruple (N, T, P, S) where
• N is a set of non-terminal symbols.
• T is a set of terminals where N ∩ T = NULL.
• P is a set of rules, P: N → (N ∪ T)*, i.e., the left-hand side of the production rules P does
have any right context or left context.
• S is the start symbol.
• Example#1 CFG:
G = ({S}, {0, 1}, P, S)

P:
(1) S –> 0S1 or just simply S –> 0S1 | ε
(2) S –> ε
3.3 Derivations Using a Grammar:
You use a grammar by starting with the start non terminal and performing a sequence of rewrites
until all of the non terminals are gone. Each sequence of tokens derivable that way is an allowed
sequence of tokens in the language.
• Example Derivations:
S => 0S1 (1) S => ε (2)
=> 01 (2)
S => 0S1 (1)

lOMoARcPSD|23777972
=> 00S11 (1)

=> 000S111 (1)
=> 000111 (2)
• Note that G “generates” the language {0k1k | k>=0}
3.4 Leftmost and rightmost derivations

When doing rewrites, you are allowed to select any nonterminal in a string to rewrite. But
sometimes it is useful to choose the first nonterminal, other times to choose the last nonterminal,
to rewrite.
A leftmost derivation is a derivation that always selects the leftmost nonterminal to rewrite. For
example,
E ⇒ E+E
⇒ n+E
⇒ n+E*E
⇒ n+(E)*E
⇒ n+(n)*E
⇒ n+(n)*n
is a leftmost derivation of n + ( n ) * n.
A rightmost derivation is a derivation that always selects the rightmost nonterminal to rewrite.
For example,
E ⇒ E+E
⇒ E+E*E
⇒ E+E*n
⇒ E+(E)*n

lOMoARcPSD|23777972
⇒ E+(n)*n
⇒ n+(n)*n
is a rightmost derivation of n + ( n ) * n.
3.5 The language of a grammar
Say that α ⇒*G β if it is possible to rewrite string α into β by doing a sequence of zero or more
rewrite steps using the productions of G. For example, we saw above that, using the expression
grammar G above,
E ⇒*G n + n
A grammar describes a language. If G is a grammar with start nonterminal S, then the language
of G is the set of all sequences of tokens α such that S⇒*G α.
3.6 Derivation (or Parse) Tree
• Definition: Let G = (V, T, P, S) be a CFG. A tree is a derivation (or parse) tree if:
– Every vertex has a label from V U T U {ε}
– The label of the root is S
– If a vertex with label A has children with labels X1, X2,…, Xn, from left to right, then
A –> X1, X2,…, Xn

must be a production in P
– If a vertex has label ε, then that vertex is a leaf and the only child of its’ parent
• More Generally, a derivation tree can be defined with any non-terminal as the root.

lOMoARcPSD|23777972
Representation Technique:
• Root vertex − Must be labeled by the start symbol.
• Vertex − Labeled by a non-terminal symbol.
• Leaves − Labeled by a terminal symbol or ε.
If S → x1x2 …… xn is a production rule in a CFG, then the parse tree / derivation tree will be as
follows −
There are two different approaches to draw a derivation tree −
Top-down Approach −
• Starts with the starting symbol S

lOMoARcPSD|23777972
• Goes down to tree leaves using productions
Bottom-up Approach −
• Starts from tree leaves
• Proceeds upward to the root which is the starting symbol S
Derivation or Yield of a Tree
The derivation or the yield of a parse tree is the final string obtained by concatenating the labels
of the leaves of the tree from left to right, ignoring the Nulls. However, if all the leaves are Null,
derivation is Null.
Example
Let a CFG {N,T,P,S} be
N = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε
One derivation from the above CFG is “abaabb”
S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

lOMoARcPSD|23777972
3.7 Sentential Form
A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all of its
children are in the sub-tree or none of them are in the sub-tree.
If in any CFG the productions are −
S → AB, A → aaA | ε, B → Bb| ε
the partial derivation tree can be the following −
If a partial derivation tree contains the root S, it is called a sentential form. The above sub-tree
is also in sentential form.
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

lOMoARcPSD|23777972
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 −

lOMoARcPSD|23777972
3.8 Ambiguity in Grammars and languages
Left and Right Recursive Grammars
In a context-free grammar G, if there is a production in the form X → Xa where 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.

lOMoARcPSD|23777972
Ambiguity in Context Free Grammar:
Definition: Let G be a CFG. Then G is said to be ambiguous if there exists an x in L(G) with >1
leftmost derivations. Equivalently, G is said to be ambiguous if there exists an x in L(G) with >1
parse trees, or >1 rightmost derivations.
• Note: Given a CFL L, there may be more than one CFG G with L = L(G). Some ambiguous
and some not.
• Definition: Let L be a CFL. If every CFG G with L = L(G) is ambiguous, then L is inherently
ambiguous.
• Example: Consider the string aaab and the preceding grammar
The string has two left-most derivations, and therefore has two distinct parse trees and is ambiguous.
Eliminations of Useless Symbols

• Definition:
Let G = (V, T, S, P) be a context-free grammar. A variable A V is said to be useful if and only
if there is at least one w L(G) such that

lOMoARcPSD|23777972
S→ xAy → w
With x, y (V T) .
In words, a variable is useful if and only if it occurs in at least on derivation. A variable that is
not useful is called useless. A production is useless if it involves any useless variable
• For a grammar with productions

S → aSb | |A
A → aA
A is useless variable and the production S → A plays no role since A cannot be eventually
transformed into a terminal string; while A can appear in a sentential form derived from S, this
sentential form can never lead to sentence!
Hence, removing S → A (and A → aA) does not change the language, but does simplify the
grammar.
• For a grammar with productions
S→A
A → aA |
B → bA
B is useless so is the production B → bA! Observe that, even though a terminal string can be
derived from B, there is no way to get to B from S, i.e. cannot achieve
S → xBy.
• Example:
Eliminate useless symbols and productions from G = (V, T, S, P), where
V = {S, A, B, C}, T = {a, b} and
P consists of
S → aS | A | C
A→ a

lOMoARcPSD|23777972
B → aa
C → aCb
First, note that the variable C cannot lead to any terminal string, we can then remove C and its
associated productions, we get G1 with V1 = {S, A, B}, T1 = {a} and P1 consisting of
S → aS | A
A→a
B → aa
Next, we identify variables that cannot be reached from the start variable. We can create a
dependency graph for V1. For a context-free grammar, a dependency graph has its vertices
labeled with variables with an edge between any two vertices I and J if there is a production of
the form
I → xJy
Consequently, the variable B is shown to be useless and can be removed together with its
associated production.
The resulting grammar G’ = (V’, T’, S, P’) is with V’ = {S, A}, T’ = {a} and P’ consisting of
S -> aS | A
A -> a
Eliminations of null-Production
• Definition :
a) Any production of a context-free grammar of the form
A -> ᵋ
is called a -production.

lOMoARcPSD|23777972
b) Any variable A for which the derivation

A -> ᵋ
is possible is called null able.
• If a grammar contains some null-productions or null able variables but does not generate the
language that contains an empty string, the null-productions can be removed!
• Example:
Consider the grammar, G with productions
S ->aS1b
S1 -> aS1b | ᵋ
L(G) = {anbn | n -> 1} which is a ᵋ -free language. The ᵋ -production can be removed after
adding new productions obtained by substituting ᵋ for S1 on the right hand side.
We get an equivalent G’ with productions
S -> aS1b | ab
S1 -> aS1b | ab
• Theorem:
Let G be any context-free grammar with ᵋ L(G). There exists an equivalent grammar G’ without
null-productions.
Proof :
Find the set VN of all null able variables of G
1. For all productions A -> ᵋ, put A in VN
2. Repeat the following step until no further variables are added to VN:
For all productions
B -> A1A2…An
where A1, A2, …, An are in VN, put B in VN.
With the resulting VN, P’ can be constructed by looking at all productions in P of the form
A -> x1x2…xm, m -> 1
where each xi V T.

lOMoARcPSD|23777972
3.9 Pushdown Automata (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

lOMoARcPSD|23777972
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.
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}

lOMoARcPSD|23777972
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}
3.9.1 Instantaneous Description (ID) of PDA
ID is an informal notation of how a PDA computes an input string and make a decision that
string is accepted or rejected.
An instantaneous description is a triple (q, w, α) where:
q describes the current state.
w describes the remaining input.
α describes the stack contents, top at the left.
3.9.2 Construction of PUSH DOWN AUTOMATA
PROBLEM- 1: Design a PDA for accepting a language {anb2n | n>=1}.
Solution: In this language, n number of a's should be followed by 2n number of b's. Hence, we
will apply a very simple logic, and that is if we read single 'a', we will push two a's onto the
stack. As soon as we read 'b' then for every single 'b' only one 'a' should get popped from the
stack.
The ID can be constructed as follows:
δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)

lOMoARcPSD|23777972
Now when we read b, we will change the state from q0 to q1 and start popping corresponding
'a'. Hence,
δ(q0, b, a) = (q1, ε)
Thus this process of popping 'b' will be repeated unless all the symbols are read. Note that
popping action occurs in state q1 only.
δ(q1, b, a) = (q1, ε)
After reading all b's, all the corresponding a's should get popped. Hence when we read ε as
input symbol then there should be nothing in the stack. Hence the move will be:
δ(q1, ε, Z) = (q2, ε)
Where
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
We can summarize the ID as:
δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)
Now we will simulate this PDA for the input string "aaabbbbbb".
δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)
⊢ δ(q0, abbbbbb, aaaaZ)
⊢ δ(q0, bbbbbb, aaaaaaZ)
⊢ δ(q1, bbbbb, aaaaaZ)
⊢ δ(q1, bbbb, aaaaZ)
⊢ δ(q1, bbb, aaaZ)

lOMoARcPSD|23777972
⊢ δ(q1, bb, aaZ)
⊢ δ(q1, b, aZ)
⊢ δ(q1, ε, Z)
⊢ δ(q2, ε)
ACCEPT
PROBLEM-2: Design a PDA for accepting a language {0n1m0n | m, n>=1}.
Solution: In this PDA, n number of 0's are followed by any number of 1's followed n number of
0's. Hence the logic for design of such PDA will be as follows:
Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then
read 0, and on each read of 0, pop one 0 from the stack.
For instance: Pushdown Automata
This scenario can be written in the ID form as:
δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)
Now we will simulate this PDA for the input string "0011100".
δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)
⊢ δ(q0, 11100, 00Z)
⊢ δ(q0, 1100, 00Z)
⊢ δ(q1, 100, 00Z)

lOMoARcPSD|23777972
⊢ δ(q1, 00, 00Z)
⊢ δ(q1, 0, 0Z)
⊢ δ(q1, ε, Z)
⊢ δ(q2, Z)
ACCEPT
3.9.3 PDA Acceptance
A language can be accepted by Pushdown automata using two approaches:
1. Acceptance by Final State: The PDA is said to accept its input by the final state if it enters
any final state in zero or more moves after reading the entire input.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be
defined as:
L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}
2. Acceptance by Empty Stack: On reading the input string from the initial configuration for
some PDA, the stack of PDA gets empty.
Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined
as:
N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}
Equivalence of Acceptance by Final State and Empty Stack
If L = N(P1) for some PDA P1, then there is a PDA P2 such that L = L(P2). That means the
language accepted by empty stack PDA will also be accepted by final state PDA.
If there is a language L = L (P1) for some PDA P1 then there is a PDA P2 such that L = N(P2).
That means language accepted by final state PDA is also acceptable by empty stack PDA.

lOMoARcPSD|23777972
PROBLEM: Construct a PDA that accepts the language L over {0, 1} by empty stack which
accepts all the string of 0's and 1's in which a number of 0's are twice of number of 1's.
Solution: There are two parts for designing this PDA:
If 1 comes before any 0's
If 0 comes before any 1's.
We are going to design the first part i.e. 1 comes before 0's. The logic is that read single 1 and
push two 1's onto the stack. Thereafter on reading two 0's, POP two 1's from the stack. The δ
can be
δ(q0, 1, Z) = (q0, 11, Z) Here Z represents that stack is empty
δ(q0, 0, 1) = (q0, ε)
Now, consider the second part i.e. if 0 comes before 1's. The logic is that read first 0, push it
onto the stack and change state from q0 to q1. [Note that state q1 indicates that first 0 is read
and still second 0 has yet to read].
Being in q1, if 1 is encountered then POP 0. Being in q1, if 0 is read then simply read that
second 0 and move ahead. The δ will be:
δ(q0, 0, Z) = (q1, 0Z)
δ(q1, 0, 0) = (q1, 0)
δ(q1, 0, Z) = (q0, ε) (indicate that one 0 and one 1 is already read, so simply
read the second 0)
δ(q1, 1, 0) = (q1, ε)
Now, summarize the complete PDA for given L is:
δ(q0, 1, Z) = (q0, 11Z)
δ(q0, 0, 1) = (q1, ε)
δ(q0, 0, Z) = (q1, 0Z)
δ(q1, 0, 0) = (q1, 0)

lOMoARcPSD|23777972
δ(q1, 0, Z) = (q0, ε)
δ(q0, ε, Z) = (q0, ε) ACCEPT state
3.10 The Languages of a PDA
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.
Example
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

lOMoARcPSD|23777972
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.
3.11 Equivalence of PDA's and CFG's
3.11.1 CFG to PDA Conversion
The first symbol on R.H.S. production must be a terminal symbol. The following steps
are used to obtain PDA from CFG is:
Step 1: Convert the given productions of CFG into GNF.
Step 2: The PDA will only have one state {q}.
Step 3: The initial symbol of CFG will be the initial symbol in the PDA.
Step 4: For non-terminal symbol, add the following rule:
δ(q, ε, A) = (q, α)
Where the production rule is A → α
Step 5: For each terminal symbols, add the following rule:

lOMoARcPSD|23777972
δ(q, a, a) = (q, ε) for every terminal symbol
PROBLEM-1: Convert the following grammar to a PDA that accepts the same language.
S → 0S1 | A
A → 1A0 | S | ε
Solution: The CFG can be first simplified by eliminating unit productions:
S → 0S1 | 1S0 | ε
Now we will convert this CFG to GNF:
S → 0SX | 1SY | ε
X→1
Y→0
The PDA can be:
R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}
R2: δ(q, ε, X) = {(q, 1)}
R3: δ(q, ε, Y) = {(q, 0)}
R4: δ(q, 0, 0) = {(q, ε)}
R5: δ(q, 1, 1) = {(q, ε)}
PROBLEM- 2: Construct PDA for the given CFG, and test whether 0104 is acceptable by this
PDA.
S → 0BB
B → 0S | 1S | 0
Solution: The PDA can be given as:
A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}

lOMoARcPSD|23777972
The production rule δ can be:
R1: δ(q, ε, S) = {(q, 0BB)}
R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}
R3: δ(q, 0, 0) = {(q, ε)}
R4: δ(q, 1, 1) = {(q, ε)}
Testing 0104 i.e. 010000 against PDA:
δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)
⊢ δ(q, 10000, BB) R1
⊢ δ(q, 10000,1SB) R3
⊢ δ(q, 0000, SB) R2
⊢ δ(q, 0000, 0BBB) R1
⊢ δ(q, 000, BBB) R3
⊢ δ(q, 000, 0BB) R2
⊢ δ(q, 00, BB) R3
⊢ δ(q, 00, 0B) R2
⊢ δ(q, 0, B) R3
⊢ δ(q, 0, 0) R2
⊢ δ(q, ε) R3
ACCEPT
Thus 0104 is accepted by the PDA.

lOMoARcPSD|23777972
PROBLEM- 3: Draw a PDA for the CFG given below:
S → aSb
S→a|b|ε
Solution: The PDA can be given as:
P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}
The mapping function δ will be:
R1: δ(q, ε, S) = {(q, aSb)}
R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}
R3: δ(q, a, a) = {(q, ε)}
R4: δ(q, b, b) = {(q, ε)}
R5: δ(q, ε, z0) = {(q, ε)}
Simulation: Consider the string aaabb
δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb) R3
⊢ δ(q, εaabb, Sb) R1
⊢ δ(q, aabb, aSbb) R3
⊢ δ(q, εabb, Sbb) R2
⊢ δ(q, abb, abb) R3
⊢ δ(q, bb, bb) R4
⊢ δ(q, b, b) R4
⊢ δ(q, ε, z0) R5
⊢ δ(q, ε)
ACCEPT

lOMoARcPSD|23777972
3.11.2 PDA TO CFG:
Example: Consider the PDA PN = ({q}, {0, 1}, {Z, A, B}, δN, q, Z) in Figure 2. The
corresponding context-free grammar G = (V, {0, 1}, R, S) is given by:
V = {S, [qZq], [qAq], [qBq]}.
1. S ! [qZq]
2. [qZq] ! 0[[qAq][qZq] (since _N(q, 0, Z) contains (q,AZ))
3. [qZq] ! 1[[qBq][qZq] (since _N(q, 1, Z) contains (q,BZ))
4. [qAq] ! 0[[qAq][qAq] (since _N(q, 0,A) contains (q,AA))
5. [qBq] ! 1[[qBq][qBq] (since _N(q, 1,B) contains (q,BB))
6. [qAq] ! 1 (since _N(q, 1,A) contains (q, _))
7. [qBq] ! 0 (since _N(q, 0,B) contains (q, _))
8. [qZq] ! _ (since _N(q, _, Z) contains (q, _))
3.12 Deterministic PDAs and DCFLs

A pushdown automaton (PDA) is a finite state machine which has an additional stack storage.
The transitions a machine makes are based not only on the input and current state, but also on the
stack. The formal definition (in our textbook) is that a PDA is this:
M = (K,Σ,Γ,Δ,s,F)
where
• K = finite state set

lOMoARcPSD|23777972
• Σ = finite input alphabet

• Γ = finite stack alphabet
• s ∈ K: start state
• F ⊆ K: final states
• The transition relation, Δ is a finite subset of (K×(Σ∪{ε})×Γ*) × (K×Γ*)
We have to have the finite qualifier because the full subset is infinite by virtue of
the Γ* component. The meaning of the transition relation is that, for σ ∈ Σ, if ((p,σ,α),(q,β)) ∈ Δ:
• the current state is p
• the current input symbol is σ
• the string at the top of the stack is α
then:
• the new state is q
• replace α on the top of the stack by β (pop the α and push the β)
Otherwise, if ((p,ε,α),(q,β)) ∈ Δ, this means that if
• the current state is p
• the string at the top of the stack is α then (not consulting the input symbol), we can
• change the state is q
• replace α on the top of the stack by β
Machine Configuration, yields, acceptance

A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content)
We define the usual yields relationships:
(p,σw,αγ) ⊢ (q,w,βγ) if ((p,σ,α),(q,β)) ∈ Δ
or
(p,w,αγ) ⊢ (q,w,βγ) if ((p,ε,α),(q,β)) ∈ Δ
As expected, ⊢* is the reflexive, transitive closure of ⊢.
A string w is accepted by the PDA if
(s,w,ε) ⊢* (f,ε,ε)
Namely, from the start state with empty stack, we
• process the entire string,

lOMoARcPSD|23777972
• end in a final state

• end with an empty stack.
The language accepted by a PDA M, L(M), is the set of all accepted strings.
The empty stack is our key new requirement relative to finite state machines. The examples that
we generate have very few states; in general, there is so much more control from using the stack
memory. Acceptance by empty stack only or final state only is addressed in problems 3.3.3 and
3.3.4.
The anbn language

The language is L = { w ∈ {a,b}* : w = anbn, n ≥ 0 }. Here are two PDAs for L:
and

lOMoARcPSD|23777972
Unit IV
NORMAL FORMS
4.1 Normal forms of CFG:
1) CNF (Chomsky Normal Form)
2) GNF (Griebach Normal Form)
4.2 Simplifying Context Free Grammars
The definition of context free grammars (CFGs) allows us to develop a wide variety of
grammars. Most of the time, some of the productions of CFGs are not useful and are redundant.
This happens because the definition of CFGs does not restrict us from making these redundant
productions.
By simplifying CFGs we remove all these redundant productions from a grammar , while
keeping the transformed grammar equivalent to the original grammar. Two grammars are called
equivalent if they produce the same language. Simplifying CFGs is necessary to later convert
them into Normal forms.
Types of redundant productions and the procedure of removing them are mentioned below.
4.2.1 Useless productions – The productions that can never take part in derivation of any string ,
are called useless productions. Similarly , a variable that can never take part in derivation of any
string is called a useless variable. For eg.
S -> abS | abA | abB
A -> cd
B -> aB
C -> dc

lOMoARcPSD|23777972
In the example above , production ‘C -> dc’ is useless because the variable ‘C’ will never occur
in derivation of any string. The other productions are written in such a way that variable ‘C’ can
never reached from the starting variable ‘S’.
Production ‘B ->aB’ is also useless because there is no way it will ever terminate . If it never
terminates , then it can never produce a string. Hence the production can never take part in any
derivation.
To remove useless productions , we first find all the variables which will never lead to a terminal
string such as variable ‘B’. We then remove all the productions in which variable ‘B’ occurs.
So the modified grammar becomes –
S -> abS | abA
A -> cd
C -> dc
We then try to identify all the variables that can never be reached from the starting variable such
as variable ‘C’. We then remove all the productions in which variable ‘C’ occurs.
The grammar below is now free of useless productions –
S -> abS | abA
A -> cd
4.2.2. є or λ productions – The productions of type ‘A -> λ’ are called λ productions ( also
called lambda productions and null productions) . These productions can only be removed from
those grammars that do not generate λ (an empty string). It is possible for a grammar to contain
null productions and yet not produce an empty string.
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 of type ‘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.

lOMoARcPSD|23777972
After finding all the nullable variables, we can now start to construct the null production free
grammar. For all the productions in the original grammar , we add the original production as well
as all the combinations of the production that can be formed by replacing the nullable variables
in the production by λ. If all the variables on the RHS of the production are nullable , then we do
not add ‘A -> λ’ to the new grammar. An example will make the point clear. Consider the
grammar –
S -> ABCd
A -> BC
B -> bB | λ
C -> cC | λ
Lets first find all the nullable variables. Variables ‘B’ and ‘C’ are clearly nullable because they
contain ‘λ’ on the RHS of their production. Variable ‘A’ is also nullable because in (2) , both
variables on the RHS are also nullable. Similarly , variable ‘S’ is also nullable. So variables ‘S’ ,
‘A’ , ‘B’ and ‘C’ are nullable variables.
Lets create the new grammar. We start with the first production. Add the first production as it is.
Then we create all the possible combinations that can can be formed by replacing the nullable
variables with λ. Therefore line (1) now becomes ‘S -> ABCd | ABd | ACd | BCd | Ad | Bd |Cd |
d ’.We apply the same rule to line (2) but we do not add ‘A -> λ’ even though it is a possible
combination. We remove all the productions of type ‘V -> λ’. The new grammar now becomes –
S -> ABCd | ABd | ACd | BCd | Ad | Bd |Cd | d
A -> BC | B | C
B -> bB | b
C -> cC | c
4.2.3 Unit productions – The productions of type ‘A -> B’ are called unit productions.
To create a unit production free grammar ‘Guf’ from the original grammar ‘G’ , we follow the
procedure mentioned below.

lOMoARcPSD|23777972
First add all the non-unit productions of ‘G’ in ‘Guf’. Then for each variable ‘A’ in grammar ‘G’
, find all the variables ‘B’ such that ‘A *=> B’. Now , for all variables like ‘A ’ and ‘B’, add ‘A -
> x1 | x2 | …xn’ to ‘Guf’ where ‘B -> x1 | x2 | …xn ‘ is in ‘Guf’ . None of the x1 , x2 … xn are
single variables because we only added non-unit productions in ‘Guf’. Hence the resultant
grammar is unit production free. For eg.
S -> Aa | B
A -> b | B
B -> A | a
Lets add all the non-unit productions of ‘G’ in ‘Guf’. ‘Guf’ now becomes –
S -> Aa
A -> b
B -> a
Now we find all the variables that satisfy ‘X *=> Z’. These are ‘S *=> A’ , ‘S*=>B’, ‘A *=> B’
and ‘B *=> A’. For ‘A *=> B’ , we add ‘A -> a’ because ‘B ->a’ exists in ‘Guf’. ‘Guf’ now
becomes
S -> Aa
A -> b | a
B -> a
For ‘B *=> A’ , we add ‘B -> b’ because ‘A -> b’ exists in ‘Guf’. The new grammar now
becomes
S -> Aa
A -> b | a
B -> a | b

lOMoARcPSD|23777972
We follow the same step for ‘S *=> A’ and ‘S*=>B’ and finally get the following grammar –
S -> Aa | b | a
A -> b | a
B -> a | b
Note: To remove all kinds of productions mentioned above, first remove the null productions,
then the unit productions and finally , remove the useless productions. Following this order is
very important to get the correct result.
4.3 Closure Properties of Context Free Languages
Context Free languages are accepted by pushdown automata but not by finite automata. Context
free languages can be generated by context free grammar which has the form :
A -> ρ (where A ∈ N and ρ ∈ (T ∪ N)* and N is a non-terminal and T is a terminal)

Properties of Context Free Languages
Union : If L1 and If L2 are two context free languages, their union L1 ∪ L2 will also be context
free. For example,
L1 = { anbncm | m >= 0 and n >= 0 } and L2 = { anbmcm | n >= 0 and m >= 0 }
L3 = L1 ∪ L2 = { anbncm ∪ anbmcm | n >= 0, m >= 0 } is also context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be
equal to number of c’s. Their union says either of two conditions to be true. So it is also context
free language.
Note: So CFL are closed under Union.
Concatenation : If L1 and If L2 are two context free languages, their concatenation L1.L2 will
also be context free. For example,
L1 = {anbn | n >= 0 } and L2 = { cmdm | m >= 0 }
L3 = L1.L2 = {anbncmdm | m >= 0 and n >= 0} is also context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of c’s should be
equal to number of d’s. Their concatenation says first number of a’s should be equal to number

lOMoARcPSD|23777972
of b’s, then number of c’s should be equal to number of d’s. So, we can create a PDA which will
first push for a’s, pop for b’s, push for c’s then pop for d’s. So it can be accepted by pushdown
automata, hence context free.
Note: So CFL are closed under Concatenation.
Kleene Closure : If L1 is context free, its Kleene closure L1* will also be context free. For
example,
L1 = { anbn | n >= 0 }
L1* = {anbn | n >= 0 }* is also context free.
Note :So CFL are closed under Kleen Closure.
Intersection and complementation : If L1 and If L2 are two context free languages, their
intersection L1 ∩ L2 need not be context free. For example,
L1 = { anbncm | n >= 0 and m >= 0 } and L2 = (ambncn | n >= 0 and m >= 0 }
L3 = L1 ∩ L2 = {anbncn | n >= 0 } need not be context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be
equal to number of c’s. Their intersection says both conditions need to be true, but push down
automata can compare only two. So it cannot be accepted by pushdown automata, hence not
context free.
Similarly, complementation of context free language L1 which is ∑* – L1, need not be context
free.
Note : So CFL are not closed under Intersection and Complementation.
4.4 Converting Context Free Grammar to Chomsky Normal Form

lOMoARcPSD|23777972
Prerequisite – Simplifying Context Free Grammars
A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules satisfy
one of the following conditions:
A non-terminal generating a terminal (e.g.; X->x)
A non-terminal generating two non-terminals (e.g.; X->YZ)
Start symbol generating ε. (e.g.; S-> ε)
Consider the following grammars,
G1 = {S->a, S->AZ, A->a, Z->z}
G2 = {S->a, S->aZ, Z->a}
The grammar G1 is in CNF as production rules satisfy the rules specified for CNF. However, the
grammar G2 is not in CNF as the production rule S->aZ contains terminal followed by non-
terminal which does not satisfy the rules specified for CNF.
Note –
For a given grammar, there can be more than one CNF.
CNF produces the same language as generated by CFG.
CNF is used as a preprocessing step for many algorithms for CFG like CYK(membership algo),
bottom-up parsers etc.
For generating string w of length ‘n’ requires ‘2n-1’ production or steps in CNF.
Any Context free Grammar that do not have ε in it’s language has an equivalent CNF.
How to convert CFG to CNF?

lOMoARcPSD|23777972
Step 1. Eliminate start symbol from RHS.

If start symbol S is at the RHS of any production in the grammar, create a new production as:
S0->S
where S0 is the new start symbol.
Step 2. Eliminate null, unit and useless productions.

If CFG contains null, unit or useless production rules, eliminate them.
Step 3. Eliminate terminals from RHS if they exist with other terminals or non-terminals. e.g,;
production rule X->xY can be decomposed as:
X->ZY
Z->x
Step 4. Eliminate RHS with more than two non-terminals.
e.g,; production rule X->XYZ can be decomposed as:
X->PZ
P->XY
Example – Let us take an example to convert CFG to CNF. Consider the given grammar G1:
S → ASB
A → aAS|a|ε
B → SbS|A|bb
Step 1. As start symbol S appears on the RHS, we will create a new production rule S0->S.
Therefore, the grammar will become:

lOMoARcPSD|23777972
S0->S
S → ASB
A → aAS|a|ε
B → SbS|A|bb
Step 2. As grammar contains null production A-> ε, its removal from the grammar yields:
S0->S
S → ASB|SB
A → aAS|aS|a
B → SbS| A|ε|bb
Now, it creates null production B→ ε, its removal from the grammar yields:
S0->S
S → AS|ASB| SB| S
A → aAS|aS|a
B → SbS| A|bb
Now, it creates unit production B->A, its removal from the grammar yields:
S0->S
S → AS|ASB| SB| S
A → aAS|aS|a
B → SbS|bb|aAS|aS|a

lOMoARcPSD|23777972
Also, removal of unit production S0->S from grammar yields:
S0-> AS|ASB| SB| S
S → AS|ASB| SB| S
A → aAS|aS|a
Also, removal of unit production S->S and S0->S from grammar yields:
S0-> AS|ASB| SB
S → AS|ASB| SB
A → aAS|aS|a
Step 3. In production rule A->aAS |aS and B-> SbS|aAS|aS, terminals a and b exist on RHS with
non-terminates. Removing them from RHS:
S0-> AS|ASB| SB
S → AS|ASB| SB
A → XAS|XS|a
B → SYS|bb|XAS|XS|a
X →a
Y→b
Also, B->bb can’t be part of CNF, removing it from grammar yields:
S0-> AS|ASB| SB
S → AS|ASB| SB

lOMoARcPSD|23777972
A → XAS|XS|a
B → SYS|VV|XAS|XS|a
X→a
Y→b
V→b
Step 4: In production rule S0->ASB, RHS has more than two symbols, removing it from
grammar yields:
S0-> AS|PB| SB
S → AS|ASB| SB
A → XAS|XS|a
X→a
Y→b
V→b
P → AS
Similarly, S->ASB has more than two symbols, removing it from grammar yields:
S0-> AS|PB| SB
S → AS|QB| SB
A → XAS|XS|a
X→a

lOMoARcPSD|23777972
Y→b
V→b
P → AS
Q → AS
Similarly, A->XAS has more than two symbols, removing it from grammar yields:
S0-> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
X→a
Y→b
V→b
P → AS
Q → AS
R → XA
Similarly, B->SYS has more than two symbols, removing it from grammar yields:
S0 -> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
B → TS|VV|XAS|XS|a
X→a

lOMoARcPSD|23777972
Y→b
V→b
P → AS
Q → AS
R → XA
T → SY
Similarly, B->XAX has more than two symbols, removing it from grammar yields:
S0-> AS|PB| SB
S → AS|QB| SB
A → RS|XS|a
B → TS|VV|US|XS|a
X→a
Y→b
V→b
P → AS
Q → AS
R → XA
T → SY
U → XA So this is the required CNF for given grammar.
4.5 Converting Context Free Grammar to Greibach Normal Form
Prerequisite – Context Free Grammars, Simplifying Context Free Grammars

lOMoARcPSD|23777972
A context free grammar (CGF) is in Greibach Normal Form (GNF) if all production rules satisfy
one of the following conditions:
A non-terminal generating a terminal (e.g.; X->x)
A non-terminal generating a terminal followed by any number of non-terminals (e.g.; X-

>xX1X2…Xn)
Start symbol generating ε. (e.g.; S-> ε)
Example: Consider the following grammars:
G1 = {S->aA|bB, B->bB|b, A->aA|a}
G2 = {S->aA|bB, B->bB|ε, A->aA|ε}
The grammar G1 is in GNF as production rules satisfy the rules specified for GNF. However, the
grammar G2 is not in GNF as the production rules B-> ε and A-> ε do not satisfy the rules
specified for GNF (only start symbol can generate ε).
Note –
For a given grammar, there can be more than one GNF
GNF produces the same language as generated by CFG
How to convert CFG to GNF –
Step 1. Convert the grammar into CNF.
If the given grammar is not in CNF, convert it to CNF. You can refer following article to convert
CFG to CNF: Converting Context Free Grammar to Chomsky Normal Form
Step 2. Eliminate left recursion from grammar if it exists.
If CFG contains left recursion, eliminate them. You can refer following article to eliminate left
recursion: Parsing | Set 1 (Introduction, Ambiguity and Parsers)
Step 3. Convert the production rules into GNF form.

lOMoARcPSD|23777972
If any production rule is not in the GNF form, convert them. Let us take an example to convert
CFG to GNF. Consider the given grammar G1:
S → XA|BB
B → b|SB
X→b
A→a
As G1 is already in CNF and there is not left recursion, we can skip step 1and 2 and directly
move to step 3.
The production rule B->SB is not in GNF, therefore, we substitute S -> XA|BB in production
rule B->SB as:
S → XA|BB
B → b|XAB|BBB
X→b
A→a
The production rules S->XA and B->XAB is not in GNF, therefore, we substitute X->b in
production rules S->XA and B->XAB as:
S → bA|BB
B → b|bAB|BBB
X→b
A→a
Removing left recursion (B->BBB), we get:
S → bA|BB

lOMoARcPSD|23777972
B → bC|bABC
C → BBC| ε
X→b
A→a
Removing null production (C-> ε), we get:
S → bA|BB
B → bC|bABC|b|bAB
C → BBC|BB
X→b
A→a
The production rules S->BB is not in GNF, therefore, we substitute B → bC|bABC|b|bAB in

production rules S->BB as:
S → bA| bCB|bABCB|bB|bABB
B → bC|bABC|b|bAB
C → BBC|BB
X→b
A→a
The production rules C->BB is not in GNF, therefore, we substitute B → bC|bABC|b|bAB in

production rules C->BB as:
B → bC|bABC|b|bAB
C → BBC

lOMoARcPSD|23777972
C → bCB|bABCB|bB|bABB
X→b
A→a
The production rules C->BBC is not in GNF, therefore, we substitute B → bC|bABC|b|bAB in

production rules C->BBC as:
B → bC|bABC|b|bAB
C → bCBC|bABCBC|bBC|bABBC
C → bCB|bABCB|bB|bABB
X→b
A→a
This is the GNF form for the grammar G1.
TURING MACHINE

lOMoARcPSD|23777972
Turing machine was invented in 1936 by Alan Turing. It is an accepting device which accepts
Recursive Enumerable Language generated by type 0 grammar.
There are various features of the Turing machine:
1. It has an external memory which remembers arbitrary long sequence of input.

2. It has unlimited memory capability.
3. The model has a facility by which the input at left or right on the tape can be read easily.
4. The machine can produce a certain output based on its input. Sometimes it may be
required that the same input has to be used to generate the output. So in this machine, the
distinction between input and output has been removed. Thus a common set of alphabets
can be used for the Turing machine.
4.6 Formal definition of Turing machine
A Turing machine can be defined as a collection of 7 components:
Q: the finite set of states

∑: the finite set of input symbols
T: the tape symbol
q0: the initial state
F: a set of final states
B: a blank symbol used as a end marker for input
δ: a transition or mapping function.
The mapping function shows the mapping from states of finite automata and input symbol on the
tape to the next states, external symbols and the direction for moving the tape head. This is
known as a triple or a program for turing machine.
(q0, a) → (q1, A, R)
That means in q0 state, if we read symbol 'a' then it will go to state q1, replaced a by X and move
ahead right(R stands for right).

lOMoARcPSD|23777972
4.7 BASIC MODEL OF TURING MACHINE
The turning machine can be modelled with the help of the following representation.
1. The input tape is having an infinite number of cells, each cell containing one input symbol and
thus the input string can be placed on tape. The empty tape is filled by blank characters.
2. The finite control and the tape head which is responsible for reading the current input symbol.
The tape head can move to left to right.
3. A finite set of states through which machine has to undergo.
4. Finite set of symbols called external symbols which are used in building the logic of turing
machine.
4.8 LANGUAGE ACCEPTED BY TURING MACHINE
The turing machine accepts all the language even though they are recursively enumerable.
Recursive means repeating the same set of rules for any number of times and enumerable means

lOMoARcPSD|23777972
a list of elements. The TM also accepts the computable functions, such as addition,
multiplication, subtraction, division, power function, and many more.
EXAMPLE:Construct a turing machine which accepts the language of aba over ∑ = {a, b}.
Solution: We will assume that on input tape the string 'aba' is placed like this:
The tape head will read out the sequence up to the Δ characters. If the tape head is readout 'aba'
string then TM will halt after reading Δ.
Now, we will see how this turing machine will work for aba. Initially, state is q0 and head points
to a as:
The move will be δ(q0, a) = δ(q1, A, R) which means it will go to state q1, replaced a by A and
head will move to right as:
The move will be δ(q1, b) = δ(q2, B, R) which means it will go to state q2, replaced b by B and

lOMoARcPSD|23777972
The move will be δ(q2, a) = δ(q3, A, R) which means it will go to state q3, replaced a by A and
The move δ(q3, Δ) = (q4, Δ, S) which means it will go to state q4 which is the HALT state and
HALT state is always an accept state for any TM.
The same TM can be represented by Transition Table:
States a b Δ
q0 (q1, A, R) – –
q1 – (q2, B, R) –
q2 (q3, A, R) – –
q3 – – (q4, Δ, S)
q4 – – –
The same TM can be represented by Transition Diagram:

lOMoARcPSD|23777972
4.9 PROGRAMING TECHNIQUES FOR TURING MACHINE

lOMoARcPSD|23777972
PROBLEM-1: Construct a TM for the language L = {0n1n2n} where n≥1

Solution:
L = {0n1n2n | n≥1} represents language where we use only 3 character, i.e., 0, 1 and 2. In this,
some number of 0's followed by an equal number of 1's and then followed by an equal number of
2's. Any type of string which falls in this category will be accepted by this language.
The simulation for 001122 can be shown as below:
Now, we will see how this Turing machine will work for 001122. Initially, state is q0 and head
points to 0 as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A and
head will move to the right as:
The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any symbol, remain in
the same state and move to the right as:
The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and

lOMoARcPSD|23777972
The move will be δ(q2, 1) = δ(q2, 1, R) which means it will not change any symbol, remain in
the same state and move to right as:
The move will be δ(q2, 2) = δ(q3, C, R) which means it will go to state q3, replaced 2 by C and
Now move δ(q3, 2) = δ(q3, 2, L) and δ(q3, C) = δ(q3, C, L) and δ(q3, 1) = δ(q3, 1, L) and δ(q3,
B) = δ(q3, B, L) and δ(q3, 0) = δ(q3, 0, L), and then move δ(q3, A) = δ(q0, A, R), it means will
go to state q0, replaced A by A and head will move to right as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A, and
The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any symbol, remain in

lOMoARcPSD|23777972
The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and
The move will be δ(q2, C) = δ(q2, C, R) which means it will not change any symbol, remain in
The move will be δ(q2, 2) = δ(q3, C, L) which means it will go to state q3, replaced 2 by C and
head will move to left until we reached A as:
immediately before B is A that means all the 0's are market by A. So we will move right to
ensure that no 1 or 2 is present. The move will be δ(q2, B) = (q4, B, R) which means it will go to
state q4, will not change any symbol, and move to right as:
The move will be (q4, B) = δ(q4, B, R) and (q4, C) = δ(q4, C, R) which means it will not change
any symbol, remain in the same state and move to right as:

lOMoARcPSD|23777972
The move δ(q4, X) = (q5, X, R) which means it will go to state q5 which is the HALT state and
HALT state is always an accept state for any TM.
PROBLEM-2: Construct a TM machine for checking the palindrome of the string of even
length.

lOMoARcPSD|23777972
Solution:
Firstly we read the first symbol from the left and then we compare it with the first symbol from
right to check whether it is the same.
Again we compare the second symbol from left with the second symbol from right. We repeat
this process for all the symbols. If we found any symbol not matching, we cannot lead the
machine to HALT state.
Suppose the string is ababbabaΔ. The simulation for ababbabaΔ can be shown as follows:
Now, we will see how this Turing machine will work for ababbabaΔ. Initially, state is q0 and
head points to a as:
We will mark it by * and move to right end in search of a as:
We will move right up to Δ as:
We will move left and check if it is a:

lOMoARcPSD|23777972
It is 'a' so replace it by Δ and move left as:
Now move to left up to * as:
Move right and read it
Now convert b by * and move right as:
Move right up to Δ in search of b as:
Move left, if the symbol is b then convert it into Δ as:

lOMoARcPSD|23777972
Now move left until * as:
Replace a by * and move right up to Δ as:
We will move left and check if it is a, then replace it by Δ as:
It is 'a' so replace it by Δ as:
Now move left until *
Now move right as:

lOMoARcPSD|23777972
Replace b by * and move right up to Δ as:
Move left, if the left symbol is b, replace it by Δ as:
Move left till *
Move right and check whether it is Δ
Go to HALT state

lOMoARcPSD|23777972
PROBLEM-3: Construct a TM machine for checking the palindrome of the string of odd
length.
Solution:
Firstly we read the first symbol from left and then we compare it with the first symbol from right
to check whether it is the same.
Again we compare the second symbol from left with the second symbol from right. We repeat
this process for all the symbols. If we found any symbol not matching, we lead the machine to
HALT state.
Suppose the string is 00100Δ. The simulation for 00100Δ can be shown as follows:
Now, we will see how this Turing machine will work for 00100Δ. Initially, state is q0 and head
points to 0 as:
Now replace 0 by * and move right as:

lOMoARcPSD|23777972
Move right up to Δ as:
Move left and replace 0 by Δ and move left:
Now move left up to * as:
Move right, convert 0 by * and then move right as:
Moved right up to Δ
Move left and replace 0 by Δ as:
Move left till * as:

lOMoARcPSD|23777972
Move right and convert 1 to * as:
Move left
Since it is *, goto HALT state.
PROBLEM-4: Construct TM for the addition function for the unary number system.

lOMoARcPSD|23777972
Solution:
The unary number is made up of only one character, i.e. The number 5 can be written in unary
number system as 11111. In this TM, we are going to perform the addition of two unary
numbers.
For example
2+3
i.e. 11 + 111 = 11111
If you observe this process of addition, you will find the resemblance with string concatenation
function.
In this case, we simply replace + by 1 and move ahead right for searching end of the string we
will convert last 1 to Δ.
Input: 3+2
The simulation for 111+11Δ can be shown as below:
Move right up to + sign as:
Convert + to 1 and move right as:
Now, move right
Again move right

lOMoARcPSD|23777972
Now Δ has encountered, so just move left as:
Convert 1 to Δ
Thus the tape now consists of the addition of two unary numbers.
The TM will look like as follows:
Here, we are implementing the function of f(a + b) = c. We assume a and b both are non zero
elements.

lOMoARcPSD|23777972
PROBLEM-5: Construct a TM for subtraction of two unary numbers f(a-b) = c where a is

always greater than b.
Solution: Here we have certain assumptions as the first number is greater than the second one.
Let us assume that a = 3, b = 2, so the input tape will be:
We will move right to - symbol as perform reduction of a number of 1's from the first number.
Let us look at the simulation for understanding the logic:
Move right up to - as:
Move right and convert 1 to * as:
Now move left
Again move left

lOMoARcPSD|23777972
Convert 1 to * and move right-hand
Now move right till 1
Convert 1 to * and move left
Convert 1 to * and move
Move right till Δ as:
Now we are in the HALT state.

Thus we get 1 on the input tape as the answer for f(3-2).
The Turing machine will look like this:

lOMoARcPSD|23777972
4.10 Extensions to Basic Turing Machine

1. Multiple Tape Turing Machine:
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.

lOMoARcPSD|23777972
2. Two-way infinite Tape Turing Machine:

• Infinite tape of two-way infinite tape Turing machine is unbounded in both directions left
and right.
• Two-way infinite tape Turing machine can be simulated by one-way infinite Turing
machine(standard Turing machine).
3. Multi-tape Multi-head Turing Machine:

• The multi-tape Turing machine has multiple tapes and multiple heads
• Each tape controlled by separate head
• Multi-Tape Multi-head Turing machine can be simulated by standard Turing machine.

lOMoARcPSD|23777972
4. Multi-dimensional Tape Turing Machine:

• It has multi-dimensional tape where head can move any direction that is left, right, up or
down.
• Multi dimensional tape Turing machine can be simulated by one-dimensional Turing
machine
5. Multi-head Turing Machine:

• A multi-head Turing machine contain two or more heads to read the symbols on the same
tape.
• In one step all the heads sense the scanned symbols and move or write independently.
• Multi-head Turing machine can be simulated by single head Turing machine.

lOMoARcPSD|23777972
6. Non-deterministic Turing Machine:

• A non-deterministic Turing machine has a single, one way infinite tape.
• For a given state and input symbol has atleast one choice to move (finite number of
choices for the next move), each choice several choices of path that it might follow for a
given input string.
• A non-deterministic Turing machine is equivalent to deterministic Turing machine.
4.11 Universal Turing Machine:
The universal Turing machine is a multi tape TM, the universal language Lu with a set of binary
integers which can be modeled by Turing machine. The universal language can be represented
by a pair(M, w) where M is a TM that accepts this languages and w is a binary string in (0+1)*
such that w belongs to L(M).
FINITE
CONTROL
INPUT M w
TAPE 0000010001001
STATE
A universal Turing machine is a multi tape TM, which contains a finite control with 3
tapes.First tape represents the transitions of Turing machine.Second tape represents the input
string which is encoded in binary form,Third tape represents states of a TM.

lOMoARcPSD|23777972
UNIT-V
UNDECIDABILITY
5.1 Decidability of problems:
A problem is said to be decidable if there exists some algorithm which solves the
problem. If no such algorithm exists then the problem is said to be undecidable. Generally if the
problem is recognized by a Turing machine then it is decidable problem otherwise they are
called undecidable problems.
Note: if a language is recursive then it is called decidable language otherwise it is called

undecidable.
5.2 Undecidable problem about Turing machine:
In this section we will discuss all the undecidable problems regarding Turing machine.
The reduction is used to prove whether given language is decidable or not. Let us understand the
concept of reduction first.
5.2.1 Reduction:
Reduction is a technique in which if a problem p1 is reduced to a problem p2 then any

solution of p2 solves p1. In general, if we have an algorithm to convert an instance of a problem
p1 to instance of a problem p2 that have the same answer then it is called as p1 reduces p2.
Hence if p1 is not recursive then p2 is also not recursive. Similarly if p1 is not recursively
enumerable then p2 also is not recursively enumerable
5.2.2 Theorem: if p1 is reduced to p2 then,
i)if p1 is undecidable then p2 is also undecidable.
ii)if p1 is non-RE then p2 is also non-RE.

lOMoARcPSD|23777972
Proof:
i) Consider an instance w of p1. Then construct an algorithm such that the algorithm w as
input and converts it into another instance x of p1. Then apply that algorithm to check whether x
is in p2, if algorithm answers “yes” then that means x is in p2, similarly we can also say that w is
in p1. Since we have obtained p2 after reduction of p1. Similarly if algorithm answers “no” then
x is not in p2 that also means w is not in p1. This proves that if p1 is undecidable then p1 is also
undecidable.
ii) we assume that p1 is non-RE but p2 is RE. now construct an algorithm to reduce p1 to
p2, but by this algorithm p2 will be recognized that means there will be a turing machine that
says “yes” if the input is p2 but may or may not halt for the input which is not in p2. As we know
that one can convert instance of w in p1 to an instance x in p2. Then apply a TM to check
whether x is in p2. If x is accepted that also means w is accepted. This procedure describes a TM
whose language is p1 if w is in p1 then x is also in p2 and if w is not in p1then x is also not in p2.
This proves that if p1 is non-RE then p2 is also non-RE.
5.2.3 Halting problem:
This is a famous undecidable problem of Turing machine. to state halting problem we

will consider the given configuration of a Turing machine. The output of TM can be
i)Halt: The machine starting at this configuration will halt after a finite number of states.
ii) No Halt: The machine starting at this configuration never reaches a halt state, no
matter how long it runs.
Now the question arises based on these two observations: Given any functional matrix, input
data tape and initial configuration, then it is possible to determine whether the process will ever
halt? This is called halting problem. That means we are asking for a procedure which enable us
to solve the halting problem for every pair (machine, tape).

lOMoARcPSD|23777972
The answer is “no” that is the halting problem is unsolvable. Now we will prove why it is
unsolvable. Let, there exists a TM, M1 which decides whether or not any computation by a TM
Twill ever halt when a description dT of T and tape t of T is given[that means the input to
machine M1will be (machine, tape) pair]. Then for every input (t, dT) to M1 if T halt for input
t,M1 also halts which is called accept halt. Similarly if T does not halt for input t then the M1 will
halt for input t then the M1 will halt which is called reject halt, as shown in fig.
When T halts for t
M1
Accept halt
(t, dT)
Input
Reject halt
When T does not halt for t
5.3 Post’s Correspondence Problem:
In this concept we will discuss about the undecidability of strings and not of Turing
machines. The undecidability of strings is determined with the help of post’s correspondence
problem (PCP).
“Posts correspondence problem consists of two lists of strings that are of equal length
over the input ∑. The two lists are A= w1,w2,w3, - - - - -,wn and B= x1,x2,x3,- - - - -,xn then there
exists a non empty set of integers i1,i2,i3,- - - ,in such that w1,w2,w3, - - - - -,wn = x1,x2,x3,- - - - -,xn”.
Example 5.3.1: Consider the correspondence system as given below-
A= (1, 0, 010, 11) and B = (10, 10, 01, 1). The input set is ∑ = {0, 1}. Find the solution.
Solution: A solution is 1, 2, 1, 3, 3, 4. that means w1w2w1w3w3w4 = x1x2x1 x3x3x4

lOMoARcPSD|23777972
W1 W2 W1 W3 W3 W4
Left to Right
1 0 1 010 010 11
X1 X2 X1 X3 X3 X4
10 10 10 01 01 1
Left to Right
Example 5.3.2: obtain the solution for the following correspondence system.
A={ba, ab, a, baa,b),B={bab, baa, ba, a, aba}. The input set is{a,b}
Solution: To obtain the corresponding sytem the one sequence can be chosen. Hence we get
w1w5w2w3w4w4 w3w4 = x1x5x2x3x4x4x3x4.
This solution gives a unique string babababaabaaabaa= babababaabaaabaa.
Hence solution is 15234434.
5.4 The classes of P and NP problem:
5.4.1 The classes of language P:
If the Turing machine M has some polynomial p(n) and the machine M never makes more
than p(n) moves when an input of length n is given to M then such Turing machine is said to be
polynomial time TM.
The class P is set of languages is accepted by polynomial time and Turing machine.
However, the class P is also a set of problems that can be solved by real computer in polynomial
time there are many such problems.

lOMoARcPSD|23777972
for eg: Transitive closure, Matrix Multiplication, Kruskals Algorithm for minimum spanning
tree.
5.4.2 Kruskal’s Algorithm
In this algorithm the minimum weight is obtained. In this algorithm also the circuit should
not be formed. Each time the edge of minimum weight has to be selected, from the graph. It is
not necessary in this algorithm to have edges of minimum weights to be adjacent.
5.4.3 The classes of language NP
If the non deterministic Turing machine M has some polynomial P(n) and the machine M never
makes more than P(n) moves when and input of length n is given to M then such a Turing
machine is said to be polynomial time NTM. The class NP is set of languages accepted by
polynomial-time non deterministic Turing machine. There are many problems in NP which are
not in P if we can’t resolve the P=NP question, we can at least demonstrate that certain problems
in NP are hardest”, in the sense that if any one of them were in P, then P=NP. Such problems are
also called as NP complete problems.
5.4.4 Travelling Salesman’s Problem:
Given a set of cities and a cost to travel between each pair of cities, determine whether
there is a path that visits every city once and returns to the first city, such that the cost travelled is
less.
This problem is a NP problem as there may exist some path with shortest distance
between the cities. If you get the solution by applying certain algorithm then travelling salesman
problem is NP complete problem. If we get no solution at all by applying an algorithm then that
travelling salesman problem belongs to NP hard class. b
a c

lOMoARcPSD|23777972
d e f
The P is a class of problems which can be solved in polymorphism time whereas NP is a

class of problems for which is it is not possible to determine whether they are solved in
polynomial time or not. Determine Turing machines. The NP class problems are of two kinds NP
complete and NP hard problems. If for solving some problems there may be some algorithm
existing then such set of problems belong to NP complete problem. On the other hand a problem
is assigned to the NP class if it is solvable in polynomial time by a non deterministic Turing
machine. One can also say p subset of NP. A problem is NP- hard if solving it in polynomial
time would make it possible to solve all problems in class NP in polynomial-time. The problem
is called NP complete if it may or may not be solved in polynomial time. Therefore NP problems
are undecidable problems. In this chapter we have seen various proofs regarding undecidability.
We have also seen the concept of posts correspondence problem and obtained solution to some
of these problems. Finally we have got introduced with the class of languages called P and NP.
Undecidability is mainly associated is mainly associated with the NP class problems.
5.5 RICE THEORM
Rice theorem states that any non-trivial semantic property of a language which is
recognized by a Turing machine is undecidable. A property, P, is the language of all Turing
machines that satisfy that property.
Formal Definition
If P is a non-trivial property, and the language holding the property, Lp , is recognized by

Turing machine M, then Lp = {<M> | L(M) ∈ P} is undecidable.
Description and Properties
Property of languages, P, is simply a set of languages. If any language belongs to P (L ∈ P), it is

said that L satisfies the property P.
A property is called to be trivial if either it is not satisfied by any recursively enumerable

languages, or if it is satisfied by all recursively enumerable languages.

lOMoARcPSD|23777972
A non-trivial property is satisfied by some recursively enumerable languages and are not
satisfied by others. Formally speaking, in a non-trivial property, where L ∈ P, both the following
properties hold:
Property 1 − There exists Turing Machines, M1 and M2 that recognize the same language, i.e.
either ( <M1>, <M2> ∈ L ) or ( <M1>,<M2> ∉ L )
Property 2 − There exists Turing Machines M1 and M2, where M1 recognizes the language
while M2 does not, i.e. <M1> ∈ L and <M2> ∉ L
Proof
Suppose, a property P is non-trivial and φ ∈ P.
Since, P is non-trivial, at least one language satisfies P, i.e., L(M0) ∈ P , ∋ Turing Machine M0.
Let, w be an input in a particular instant and N is a Turing Machine which follows −
On input x
• Run M on w
• If M does not accept (or doesn't halt), then do not accept x (or do not halt)
• If M accepts w then run M0 on x. If M0 accepts x, then accept x.
A function that maps an instance ATM = {<M,w>| M accepts input w} to a N such that
• If M accepts w and N accepts the same language as M0, Then L(M) = L(M0) ∈ p
• If M does not accept w and N accepts φ, Then L(N) = φ ∉ p
Since ATM is undecidable and it can be reduced to Lp, Lp is also undecidable.
ASSIGNMENT QUESTIONS

lOMoARcPSD|23777972
UNIT-1
1. Conclude what type of strings will be accepted by the below Finite automata as shown
in figure
2. (a) Design a DFA, M that accepts the language. L(M) = {w/w ε{a,b} * } and w does not
contain 3 consecutive b’s
(b) Design DFA to accept strings with c and d such that number d’s are divisible by 4
(c) Design DFA which accepts language L ={ 0,000,00000,........} over {0}.
3. Out of the following languages, which are/is accepted by given FA and explain as shown
in figure 1.
(a) (a+b)* (c+d)* (ef)* (b) (ab)* (cd)* (ef)*

(c) (a+b)*+(c+d)*+(ef)* (d) ( (ab)*+ (cd)*+ (ef)* ) *.
4. Construct NFAs for the following languages

(a) The set of strings over alphabet {0,1,.........,9} such that the final digit has
appeared before.
(b) The set of strings over alphabet {0,1,.......,9} such that the final digit has not
appeared before.
(c) The set of strings of 0’s and 1’s such that there are two 0’s separated by a number
of
positions that is a multiple of 4. Note that 0 is an allowable multiple of 4.
5. Construct DFA for the following:

(a) L={w/w has both an even number of 0’s and even number of 1’s }
(b) L= { w/w is in the form of ‘x01y’ for some strings x and y consisting of 0’s And
1’s}.
6. Design a Mealy machine that uses its state to remember the last symbol read and emits
output ‘y’ whenever current input matches to previous one, and emits n otherwise.
7. a)Construct DFA for given (figure 2) NFA with ε-moves.

lOMoARcPSD|23777972
b)For the following NFA with ε -moves convert it in to an NFA with out ε -moves and
show that
NFA with ε -moves accepts the same language as shown in figure
8. (a) Design a Moore machine to determine the residue mod 5 for each ternary string (base
3)
treated as ternary integer.
(b) Convert the following Mealy machine into equivalent Moore machine as shown in
figure
9. (a) Show that the FA are equivalent as shown in figure
(b) Construct DFA for given FA as shown in figure 2b. [8+8]

lOMoARcPSD|23777972
10. (a) Construct a minimal state finite automaton to the following state diagram:
(b) Design a Moore machine and Mealy machine that accepts strings over $ = {0, 1}
where, if the input ends in 001, output a A; if the input ends in 100 , output a B;
else output a C.
11. Conversion of Moore to Mealy Machine
12. Conversion of Mealy to Moore Machine
UNIT-II
1. Find a Regular expression corresponding to each of the following subsets over {0,1}*.
(a) The set of all strings containing no three consecutive 0’s.
(b) The set of all strings where the 10th symbol from right end is a 1.
(c) The set of all strings over {0,1} having even number of 0’s & odd no. of 1’s.
(d) The set of all strings over {0,1} in which the number of occurrences of is
divisible by 3.
2. Construct an NFA for the following:
(a) R=01[((10)*+111)*+0]*1
(b) ((01+10)*00)*
3. Construct a DFA accepting language represented by 0*1*2*.
4. Is FA is possible for the following language L = {anbn |n >= 1 } if not why? Explain?
5. (a) When are two regular expressions said to be equivalent? Explain.
(b) Find the regular expression for the following finite automaton:
.
6. Construct finite automation to accept the regular expression (0+1*) (00+11) (0+1)*.
7. Construct the NFA for the regular expression,
r = 0*1( (0+1) 0*1)* (Ε+(0+1)(00)*)+0(00)*.
8. Give a DFA for accepting = {anbn / abs(n -m) mod 3 <=1} show that L is non-regular.
9. Construct an NFA and DFA for the regular expression: (0 + 1)*(00 + 11) 110.

lOMoARcPSD|23777972
10. Find the regular expression for the following finite automaton:
UNIT- III
1. (a) Write a CFG for EVEN and ODD palindromes?

(b) Obtain a right linear grammar for the following FA as shown in figure
2. Find CFG generating the following Languages

(a) L1= {aibjck |i = j }
(b) L2= {anbm |n ≠ m }
(c) L3= {0i1j0k |j > i + k }.
3. Consider the following context free grammar:
Find the leftmost derivation, rightmost derivation, and parse tree for the string:
a*(a+b00).
4. (a) Construct a context free grammar for generating the balanced parentheses, like ( ),[
], [( ) ( ) ], ( [ ] ), etc. and find the moves of the grammar to derive the string: ( [ ( ) ] ( )
)
(b) Draw the parse tree for the production grammar: S (S) |S‫כ‬S |~S |i |j, Generating
the symbolic formula: (~ ~ i ‫ ( כ‬i ‫ ~ ~ כ‬j ) ).
5. Explain Chomsky hierarchy.
6. Prove that the following language is not context-free language
L = {www |wε{a, b}*} is not context free.

lOMoARcPSD|23777972
7. Simplify the following grammar:

S -> AB
A ->a
B ->C
B -> b
C -> D
D ->E.
8. (a) What do you mean by ambiguity? Show that the grammar S -> S/S, S -> a is
ambiguous.
(b) Show that the grammar G with production
S -> a/aAb/abSb A->aAAb/bS is ambiguous.
9. Convert the following grammar into CNF.
S->aAD A->aB/bAB B->b D->d.
10. Convert the following grammar to GNF:
G = ({A1,A2,A3}, {a, b}, P1, A1) Where P consists of the following:
A1 ->A2A3 A2 -> A3A1/b A3 -> A1A2/a.
11. Construct a PDA that accepts the language

L = {wcwR/w є {a, b}*}.
12. Let G be the grammar given by
S -> aABB/aAA A -> aBB/a B -> bBB/A
Construct the PDA that accepts the language generated by this grammar G.
13. Prove that acceptance by empty stack and by final state is equivalent.
14. (a) Construct the context free grammar G which accepts the PDA A by empty stack,
where A=({q0, q1}, {a, b}, {Z0,Z}, δ, q0,Z0, φ)
δ is given by
δ(q0, b,Z0) = {(q0,ZZ0)}, δ(q0,^,Z0) = {(q0, L)}
δ(q0, b,Z) = {(q0,ZZ)}, δ(q0, a,Z) = {(q1,Z)}
δ(q1, b,Z) = {(q1,^)}, δ(q1, a,Z0) = {(q0,Z0)}
(b) What is the ID of the PDA on the string ‘bbaa’.
15. Define Deterministic pushdown automata. Explain with an example.

lOMoARcPSD|23777972
16. Find the PDA with only one state that accepts the language {ambn : n > m }.
17. Construct the PDA that recognizes the languages L={x=×R: x є {a,b}+}.
18. Define a PDA. Design a PDA for L {xcxr / x є {a,b}*}process the string “abbacabba”.
Note: xr stands for reverse of the string x.
19. What do you mean by an instantaneous description of a PDA. Explain with example.
20. (a) when do we say that PDA is nondeterministic? Design a PDA for recognizing the
language of palindromes over the input alphabet {a,b}.
(b) Distinguish between a DPDA and NPDA
UNIT-IV
1. Define a Turing machine mathematically. Define the term ‘move’ in a TM.
2. Design a TM that recognizes the set {0n1n >=|n = 1 }
3. Design a Turing Machine that accepts the set of all even palindromes over{0,1}.
4. Give a Turing machine for the following:
(a) That computes ones complement of a binary number
(b) That shifts the input string, over the alphabet (0,1) by one position right by
inserting ‘#′as the first character.
5. Explain briefly about the different types of Turing Machines.
6. Design a Turing Machine (TM) that accepts the language, L = { 0n1n0n| n >=1 }
7. Consider the following transition table (States versus Tape symbols) of a Turing
Machine, M:
Find the computation sequence of the input string: 00B

8. What is instantaneous description of a TM? Briefly explain.
9. Given ∑= {0,1}, design a Turing machine that accepts the language denoted
by the regular expressions 00*.
10. Briefly explain the properties of recursive enumerable languages.

lOMoARcPSD|23777972
UNIT-V
1. Write a short notes on Decidability.

2. What is Halting Problem of Turing Machine? Is it decidable or not? Explain?
3. Explain about Universal Turing Machine?
4. What is PCP? Find the solution to the following instance of PCP:
W = (1, 10111, 10) and x = (111, 10, 0)?
5. Explain the Turing reducibility in detail.
6. Discuss about Rice Theorem.
7. What are P and NP class of Languages? What is NP Complete and give examples?
8. Giving relevant examples explain NP Hard and NP complete problems.
9. Explain in detail about Modified Post’s Correspondence Problem with an example?
10. Find whether the lists
M = (abb, aa, aaa) and N = (bba, aaa, aa) have a Post Correspondence Solution?

lOMoARcPSD|23777972
TUTORIAL QUESTIONS
UNIT-I
1. Define NFA and explain with an example.

2. (a) Design a DFA that accepts the set{an}U{b/n >=1}
(b) Draw the transition diagram for below FA.
M= { {A,B,C,D}, {0,1}, δ,C, {A,C} }
δ (A,0) = δ (A,1) = {A,B,C}
δ(B,0) = B, δ(B,1) = { A, C }
δ (C,0) = {B,C}, δ(C,1) ={ B, D }
δ (D,0) = { A, B, C, D }
δ(D,1) = {A}.
3. (a) Design a DFA for the following language. L = {0m1n/m >=0 and n >=1} .
(b) Represent all five tuples for below transition diagram and decide whether
it is DFA or NFA.
4. (a) Compare NFA and DFA with the help of suitable examples.
(b) Construct a DFA that accepts an identifier of a ‘C’ programming language.
(c) Consider the following finite automaton that recognizes a set of strings of length 6.
What is the total number of strings in the set? Explain.
5. (a) Explain NFA mathematically with an example.

lOMoARcPSD|23777972
(b) Construct a DFA that accepts an identifier of a ‘C’ programming language.
(c) Obtain the number of states in the minimized machine of the following state table of
FSM: PS NS, OUTPUT
I/P=0 I/P=1
A D, 0 A, 0
B A, 0 A, 1
C B, 1 C, 1
D B, 1 C, 1
6. Construct DFA for given FA as shown in figure
7. Define NFA mathematically. Explain its significance and the functioning. Convert the
given finite automation into deterministic equivalent. Explain method Taking suitable
exa
mp
le
pro
ve
both accept the sane string:

lOMoARcPSD|23777972
8. (a) Design a DFA that accepts the language over the alphabet, å = {0, 1, 2} where the
decimal equivalent of
the language is divisible not by 3.
(b) Design a Moore machine and Mealy machine that accepts strings over $ = {0, 1}
where, if the input ends
in 001, output a A; if the input ends in 100 , output a B; else output a C.
9. Design a Moore Machine to determine the residue mod 4 for each binary string
treated as integer.
10. Construct Minimum state Automata for the following DFA? (* denotes final state)
UNIT- II
1. Give a regular expression for the following language

L = {x ε {0, 1}* |x ends with 1 and does not contain the sub string 00}.
2. Consider the two regular expressions : r=0*+1*, s=01*10*+1*0+(0*1)*
(a) Find a string corresponding to r but not to s.
(b) Find a string corresponding to s but not to r.
3. (a) Write a procedure that combines two NFAs into a single NFA. The operations
to be performed are
those of Concatenation, Union and Closure.
(b) Show that the Language L = {an-> : n >= 0} is not regular?
4. Give a regular expression for the set of all strings over {a, b} accepting all strings
which have number of a’s divisible by 6 and number of b’s divisible by 8.
5. Find a Regular expression corresponding to each of the following subsets over
{0,1}*.

lOMoARcPSD|23777972
(a) The set of all strings containing no three consecutive 0’s.

(b) The set of all strings where the 10th symbol from right end is a 1.
(c) The set of all strings over {0,1} having even number of 0’s & odd number of
1’s.
6. Construct NFA for the following regular expressions
(a) 0+10* +01*0
(b) (0+1)*(01+110).
7. Give the English description and NFA for the following regular expressions.
(a) r=(1+01+001)*(+0+00)
(b) r=[00+11+(01+10)(00+11)*(01+10)]*
8. When are two regular expressions said to be equivalent? Obtain the regular
expression represented by
the regular set: {0, 1, 00, 01, 000, 001, 0000, 0001, …}
9. Prove the following regular expression identities:
(i) 1 + (Ε + 0)( Ε + 0)* 1 = 0* 1
(ii) Ε + 1* (011)* (1* (011)* )* = (1 + 011)*
10. Show that the simplified regular expression recognized by the following DFA is the
set of all strings of a’s and b’s that end with letter a.
UNIT- III
1. Find the left most and right most derivations for the word abba in the gram mar
S ->AA
A->aB
B->bB/a/b
2. Obtain a CFG to obtain balanced set of parentheses.(i.e every left parentheses
should match with the corresponding right parentheses).
3. Obtain a Left Linear Grammar for the DFA as shown in figure

lOMoARcPSD|23777972
4. Construct CFG without production form

S ->a /Ab / a B a A ->b/ B ->b/A
5. What is i) Derivation ii) Derivation / parse tree give example for each.
6. Define regular grammar? Construct a DFA to accept the language generated by the
following grammar.
S ->01A, A -> 10B, B->0A/11
7. Consider the following context free grammar: E +EE|*EE |−EE |x |y
Find the leftmost derivation, rightmost derivation, and parse tree for the string: +
*−xyxy
8. (a) What is meant by ambiguous grammar? Show that the grammar
S -> a |a b S b| aAb
A ->bS |aAAb is ambiguous.
(b) Find a CFG with no useless symbols equivalent to
S -> AB|CA
A -> a
B->BC|AB
C ->aB|b.
9. Reduce the Grammar G given by S->aAa
A->Sb/bcc/DaA
C->abb/DD
E->ac
D->aDA
10. Prove that the following language is not context-free language
L1= {anbncj/n<= j<= 2n}

lOMoARcPSD|23777972
11. Define PDA. In what ways a PDA can show the acceptance of a string. Explain
with examples
12. Define Deterministic pushdown automata. Explain with an example
13. Construct the PDA M for the language L={wwR/wє{a, b}_} such that L=L(M).
14. Construct a PDA for the following language. {ambmcn/m, n> =1}.
15. Construct a PDA to accept strings with 0’s and 1’s such that number of 0’s are
greater than number 1’s.
16. Show that the languages
(a) L1={0n1m/n = m and n>= 1} (b) L2={0n1m / n=2m
and n>= 1}
are deterministic context free languages?
17. Given L={ambn/n < m}. Derive (a) a CFG that accepts L.
(b) a PDA accepting L by empty stack. (c) a PDA accepting L by
final state.
18. What do you mean by an instantaneous description of a PDA. Explain with
example.
19. Define a PDA. Design a PDA for L {xcxr / x є {a,b}*}process the string
“abbacabba”.
20. Construct the PDA corresponding to the grammar:
S->aABB/aAA A->aBB/a B->bBB/A
UNIT- IV
1. Let T be the Turing machine defined by the five tuples:
(q0, 0, q1, 1,R), (q0, 1, q1, 0, r), (q0,B, q1, 0,R),
(q1, 0, q21, L), (q1, 1, q1, 0, r)(q1,B, q2, 0, L).
for each of the following initial tapes, determine the final tape when T halts,
assuming that T begins in initial position.
2. Design a Turing machine to add two given integers.
3. Design a TM that can compute proper subtraction i.e, m-n if m>n and 0 if m<n.
4. Define Turing machine formally. Explain how Turing machine can be used to
compute integer functions?

lOMoARcPSD|23777972
5. Design the Turing machine to compute following function, Show its transition
diagram also f(x)=x2 where x is integer represented in unary.
6. Define a Turing machine (TM) and the language accepted by a TM. Design a TM
for recognizing the language (a+b)* aba (a+b)*. Draw it’s transition diagram and
table using the instantaneous description notation. Process the string “aabaabaaab”.
7. Design a TM for recognizing the language of palindromes over the input alphabet
{a,b}show the moves of TM for the string “abbbba”.
8. Design a Turing Machine, M that accepts the set of strings with an equal number
of 0’s and 1’s.
9. Design a Turing Machine (TM) that accepts the language, L = { 0n1n0n| n >=1 }
10. Design a T.M for copying of information from one place to the other place.
Assume all the necessary. assumptions. Give Example of the working of your T.M.
UNIT- V
11. Write a short notes on LR(0) grammar.

12. Write a short notes onUndecidable Problems.
13. What is Halting Problem of Turing Machine? Is it decidable or not? Explain?
14. Explain about Universal Turing Machine?
15. What is post correspondence problem? Explain with an example ?
16. Distinguish between Recursive and Recursively Enumerable Languages?
17. What are P and NP class of Languages? What is NP Complete and give examples?
18. Giving relevant examples explain NP Hard and NP complete problems.
19. Explain in detail about Modified Post’s Correspondence Problem with an example?
20. Explain in detail about LBA?

lOMoARcPSD|23777972
Important Question papers
Short answer questions:
Unit I
1. Explain transition diagram, transition table with example.

2. Define transition function of DFA.
3. Define İ–transitions.
4. ConstructaDFAtoacceptevennumberof0’s.
5. Define Klean closure.
6. Construct a DFA to accept empty language.
7. Explain power of an alphabet?
8. Write transition diagram for DFA accepting string ending with 00.
9. Write transition diagram for DFA to accept exactly one a.
10. Define the language of NFA.
Unit-II
1. Define Regular Languages.

2. Define Pumping Lemma.
3. Write the applications of pumping lemma for regular languages.
4. List any two applications of regular expression.
5. Define Context Free Grammars.
6. Write through an intermediate state whose number is not greater than K-1.
7. Write regular expression for denoting language containing empty string.
8. Differentiate LMD and RMD.
9. Define ambiguous grammar.
Unit III
1. Define Greibach normal form.

2. Define null able Variable.
3. State the null able variables from the following CFG.
S->ABCa|bD

lOMoARcPSD|23777972
A->BC|b
B->b|İC
C->Đ|İD
D->d
4. State the symbol is used to label the in teriornode of the parse tree.
5. Define the language of PDA accepted by final state.
6. List the steps to convert CFG to PDA.
7. Define CNF.
8. Define PDA.
9. Define NPDA.
10. Differentiate between deterministic and non deterministic PDA.
Unit IV
1. Write the Turing Machine model.

2. Explain the moves in Turing Machine
3. Define an ID of a Turing Machine?
4. Define the Language of Turing Machine.
5. List types of TM
6. Define Turing Machine.
7. Write the difference between Push down Automata and Turing Machine.
8. Explain Church’s Hypothesis.
9. Define Context sensitive language.
10. Define multi head Turing Machine, multi dimensional Turing Machine.
UNIT-V
1. Define Chomsky hierarchy of languages.

2. Define Universal Turing Machine
3. Define LR(0)grammars.
4. Define decidability & undecidability
5. Define P, NP problems.
6. Define Rice‘s theorem

lOMoARcPSD|23777972
7. Give examples for Undecidable Problems

8. Define Turing Machine halting problem.
9. Define Turing Reducibility
10. Define PCP.

lOMoARcPSD|23777972
Long Answer Questions
Unit I
1. Define language over an alphabet with examples. Write a DFA to accept set of all string
sending with010.
2. Give example for Minimize the DFA.
3. ConstructaMooremachinetoacceptthefollowinglanguage.L={w|wmod3=0}on∑={ 0,1,2}
4. Write any four differences between DFA and NFA
5. Convert NFA with Ɛ to NFA with an example.
6. Construct NFA for (0 +1)*(00+11)(0+1)*and Convert to DFA.
7. Construct NFA for (0+1)*(00+11)(0+1)*and Draw the transition table and transition
diagram and example strings.
UNIT-II
1. ConvertRegularExpression01*+1toFiniteAutomata.
2. Convert given Finite Automat to Regular Expression using Arden’s theorem.
3. ConvertgivenFiniteAutomattoRegularExpressionusingstandardmethod(RKmethod)ij
4. Explain Identity rules. Give an example using the identity rules for the simplification.
5. Construct Regular grammar for the given Finite Automata.
6. Construct a Transition System M accepting L (G) for a given Regular Grammar G.
7. Discuss the properties of Context free Language. Explain the pumping lemma with an
example.
Unit III
1. Write a short notes on Chomsky Normal Form and Greibach Normal Form
2. Showthatthefollowinggrammarisambiguouswithrespecttothestringaaabbabbba.
S aB|bAA aS|bAA|aB bS|aBB|b
3. Illustrate the construction of Greibach normal form with an example.
4. Show that the following CFG ambiguous.
S iCtS|iCtSeS|a
C b
5. WritetheproceduretoconvertCFGtoPDAandalsoconvertthefollowingCFGtoPDA

lOMoARcPSD|23777972
S B|aAA
A aBB|a
B bBB|A
C a
6. Illustrate the construction of Greibach normal form with an example.
7. Discuss the Pumping lemma for Context Free Languages concept with example
{anbncnwhere n>0}
8. Write the procedure to convert CFG to PDA and also convert the following CFG to PDA.
S B|aAA
A aBB|a
B bBB|A
C a
Unit IV
1. Define a Turing Machine. With a neat diagram explain the working of a Turing Machine.
2. Construct a Turing Machine which shifts non block symbols 3 cells to the right.
3. Construct a Turing Machine to accept the following language. L={0n1n0n|n≥1}

4. Construct a Turing Machine that accepts the language L={0n1n|n≥1}. Give the transition
diagram for the Turing Machine obtained and also show the moves made by the Turing
machine
5. L={w#wR| wϵ(a+b)*}
6. Write short notes on Recursive and Recursively Enumerable languages?
7. Write the properties of recursive and recursively enumerable languages
Unit V
1. Explain the concept of undecidability problems about Turing Machine

2. Write a note on Modified PCP and Multi tape Turing machine.
3. Explain individually classes P and NP
4. Write short notes on post's correspondence problem and check the following is PCP or
not.
I A B
1 11 111

lOMoARcPSD|23777972
2 100 001
3 111 11
5. Explain the Halting problem and Turing Reducibility.

6. Write a short notes on universal Turing machine
7. Write a short note on Chomsky hierarchy.
8. Write a short note on Context sensitive language and linear bounded automata.

lOMoARcPSD|23777972
Objective Questions
1 Which of the following statements is (are) correct ? D
Recursive languages are closed under complementation.
If a language and its complement are both regular, the language is recursive
Set of recursively enumerable language is closed under union
All of these
2 Context free grammar is not closed under C
product
union
complementation
kleen star
3 Correct hierarchical relationship among context- free, right-linear, and context- D

sensitive language is
context-free ⊂ right-linear ⊂ context-sensitive
context-free ⊂ context-sensitive ⊂ right-linear
context-sensitive ⊂ right-inear ⊂context-free
right-linear ⊂context-free ⊂context-sensitive
5 Which of the following CFG's can't be simulated by an FSM ? B
S --> Sa | b
S --> aSb | ab

lOMoARcPSD|23777972
S --> abX, X --> cY, Y --> d | aX
None of these
6 Following context free grammar A

S —> aB | bA
A —>b | aS | bAA
B —> b | bS | aBB
generates strings of terminals that have
equal number of a's and b's
odd number of a's and odd number b's
even number of a's and even number of b's
odd number of a's and even number of a's
7 Basic limitation of FSM is that it A
cannot remember arbitrary large amount of information
sometimes fails to recognize grammars that are regular
Sometimes recognizes grammars are not regular
None of these
8 Which of the following is not possible algorithmically ? C
Regular grammar to context free grammar
Non-deterministic FSA to deterministic FSA
Non-deterministic PDA to deterministic PDA
None of these
9 The CFG B

lOMoARcPSD|23777972
s---> as | bs | a | b
(a + b)
(a + b) (a + b)*
(a + b) (a + b)
None of these
10 Consider the grammar : A
S —> ABCc | Abc

BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa
Which of the following sentences can be derived by this grammar
Abc
Aab
abcc
abbb
11 B
Pumping lemma is generally used for proving tha
given grammar is regular
given grammar is not regular
whether two given regular expressions are equivalent or not

lOMoARcPSD|23777972
None of these
12 The language of all words with at least 2 a's can be described by the regular D
expression
(ab)*a and a (ba)*
(a + b)* ab* a (a + b)*
b* ab* a (a + b)*
all of these
13 Any string of terminals that can be generated by the following CFG is D

S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a
has atleast one 'b'
should end in a 'a'
has no consecutive a's or b's
has atleast two a's
14 Which of the following statement is correct? D
All languages can not be generated by CFG
Any regular language has an equivalent CFG
Some non regular languages can't be generated by CFG
both (b) and (c)
15 Set of regular languages over a given alphabet set is not closed under D
Union

lOMoARcPSD|23777972
Complementation
Intersection
All of the above
16 FSM can recognize D
Any grammar
Only CG
Both (a) and ( b )
only regular grammar
15 B
If Σ = (0, 1), L = Σ* and R = (0n 1nsuch that n > 0 )
then languages L ∪ R and R respectively are
Regular, Regular
Regular, Not regular
Not regular, Not regular
None of these
16 L = (an bn an | n = 1,2,3) is an example of a language that is D
context free
not context free
not context free but whose complement is CF
both (b) and (c)

lOMoARcPSD|23777972
17 Given A = (0,1) and L = A*. If R = (0n 1n, n > 0) , then language L ∪ R and R are D
respectively
Regular,regular
not regular, regular
regular, not regular
context free, not regular
18 B
Define for a context free language
L ≤ {0 ; 1} init (L) = {u/uv ε L for some v in {0,1}}
(in other words, init (L) is the set of prefixes of L)
Let L {w/w is noempty and has an equal number of 0’s and 1’s)
Then init (L) is
set of all binary strings with unequal number of 0’s and 1’s
set of all binary strings including the null string
set of all binary strings with exactly one more 0’s than the number of 1’s or 1
more than the number of 0’s
none of these
19 If L1 and L2 are context free language and R a regular set, then which one of the B
languages below is not necessarily a context free language?
L1 L2

lOMoARcPSD|23777972
L1 ∩ L2
L1 ∩ R
L1 ∪ L2
20 Consider a grammar with the following productions C
S--> aab | bac | aB

S --> α S | b
S --> α b b | ab
Sα --> bdb | b
The above grammar is
Context free
Regular
Context sensitive
LR(k)
21 What can be said about a regular language L over {a} whose minimal finite state A
automation has two states?
L must be { an | n is even}
L must be {an | > 0}
Either L must be {an | n is odd}, or L must be {an | n is even}
L must be { an | n is odd}
22 Given the language L = {ab, aa, baa}, which of the following strings are in L*? C
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab

lOMoARcPSD|23777972
4) baaaaabaa
1,2 and 3
2,3 and 4
1,2 and 4
1,3 and 4
23 A PDM behaves like a TM when the number of auxiliary memory it has is C
zero
One or more
Two or more
None of these
24 All strings having equal number of a and b can be recognized by C
DFA
NDFA
PDA
All of these
25 Which of the following problems are decidable? D
1) Does a given program ever produce an output?
2) If L is context-free language, then, is ~L also context-free?
3) If L is regular language, then, is ~L also regular?
4) If L is recursive language, then, is ~L also recursive?

lOMoARcPSD|23777972
1,2,3,4
1,2
2,3,4
3,4
26 Which of the following is complement of a? C
Recursive language is recursive
Recursively enumerable language is recursively enumerable
Recursive language is either recursive or recursively enumerable
None of these
27 If nL can be recognized by a multitape TM with time complexity f, then L can be A

recognized by a one-tape machine with time complexity DSD
O( f 2)
o( f 2)
o( f 2)
O(h2)
28 If T is a TM recognizing L, and T reads every symbol in the input string, τT(n) ≥ 2n C

+ 2, then any language that can be accepted by a TM T with τT(n) = 2n + 2 is
Regular
Not regular
Uncertain
None of these

lOMoARcPSD|23777972
29 Consider an alternate Turing machine model, in which there is an input tape on which A
the tape head can move in both directions but cannot write, and one or more work
tapes, one of which serves as an output tape. For a function f, denoted by DSpace ( f )
, the set of languages that can be recognized by a Turning machine of this type which
uses no more than f(n) squares on any work tape for any input string of length n. The
only restriction we need to make on f is that f(n) > 0 for every n. The language of
balanced strings of parentheses are in
DSpace (1+ ⌈log2 (n + 1 ⌉). (⌈ x ⌉) means the smallest integer greater than or equal to
x.
DSpace (1+ ⌈log2 n⌉)
DSpace ( 1+ ⌈ log2 n2⌉)
none of these
30 Which of the following problems is solvable ? A
Writing a universal Turing machine
Determining of an arbitrary turing machine is an universal turing machine
Determining of a universal turing machine can be written for fewer than k instructions
for some k
Determining of a universal turing machine and some input will halt
31 Which of the following is not primitive recursive but partially recursive ? D
Carnot's function
Ricmann function
Bounded function
Ackermann's function

lOMoARcPSD|23777972
32 Turing machine (TM) is more powerful than FMS (Finite State Machine) because C
tape movement is confined to one direction
it has no finite state
it has the capability to remember arbitrarily long sequences of input symbols
none of these
33 If f : N--> N. If L can be recoognized by a TM T, so that τT(n) ≤ f (n) for all but A

finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).
L ∈Time (f)
L ∈ Time(cf)
L ∈ Time (h)
none of these
34 Let s is a step-counting function satisfying s(n) ≥ n, and L be a language accepted by a A

(multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes
for an input string of length n, then T ∈
Space(s)
F(n)
Time(f)
Time(h)
35 Which of the following statements is false ? D
Halting problem of Turing machines is undecidable
Determining whether a context-free grammar is ambiguous is undecidable

lOMoARcPSD|23777972
Given two arbitrary context-free grammars G1 G2 and it is undecidable whether L (G1)

= L (G2).
Given two regular grammars G1 G2 and it is undecidable whether L (G1) = L (G2)
36 A problem is decidable if there is D
An algorithm that answers either 'Yes' or 'No'
An algorithm that answer both 'Yes' and 'No'
A Turing machine that decides the problem
Both an algorithm that answers either 'Yes' or 'No' and a Turing machine that decides
the problem are correct.
37 Post correspondence problem is first suggested by B
Allan Turing
Emil Post
Kurt Godel
None of them
38 Post correspondence is to determine a B
sting
Match between two sets of strings
Match between two strings
None of them
39 If L1 and L2 are two regular languages then the problem “Is L1 ⨁ L2 (L1 Ex-OR L2) A
regular” is

lOMoARcPSD|23777972
decidable
undecidable
regular
Both decidable and regular are correct
40 Post correspondence problem over {a} is A
Decidable always
Undecidable always
Some time decidable
Undecidable some time
41 Let G1 and G2 are two grammars and G1 is regular grammar. The problem L(G1) = C
L(G2) or not is decidable when
G2 is type of 0 grammar
G2 is Context free grammar
G2 is regualr grammar
G2 is Context Sensitive grammar
42 If L1, L2, .. .. .., Ln are regular languages, then L = L1 ∪ L2 ∪ .. .. .. ∪ Ln is regular. B

This is
Undecidable
Decidable
Dependent or nature of L1
Partially decidable

lOMoARcPSD|23777972
43 If L1, L2, .. .. .. Ln are regular languages, then L = L1 ⨁ L1 ⨁ .. .. .. ⨁ Ln is regular. B

This is
Undecidable
Decidable
Dependent on nature of L1, L2, .. .. .. Ln
Partially decidable
44 If L1 is a recursively enumerable language, then whether L1c is recursively enumerable A

or not is
Undecidable
Decidable
Dependent or nature of L1
Partially decidable
45 Deciding ambiguity of a language generated by a CFG is C
Decidable
Depend on nature of the grammar
Undecidable
None of the above
46 Select the correct statements D
Recursive languages are closed under union and intersection
L = {anbncn: n ≥ 1} is recursive language
Every recursive language is recursive enumerable

lOMoARcPSD|23777972
All are correct
47 If a language L and its complement (∼L) are recursively enumerable then select B
statement
L is recursive but not ∼L
Both L and ∼L are recursive
∼L is recursive but not L
None of them
48 Select the correct statement D
Recursive languages are closed under complement
Recursive enumerable language are closed under union
If language L and its complement (∼L) are recursively enumerable then L and ∼L are
recursive
All the statements are correct
49 If there is a Turing machine M for a problem set P. M is applied to any problem in the C
set P and terminates when answer is “Yes” and may or may not terminate otherwise
then P is
Solvable
Unsolvable
Partially Solvable
None of these
50 The statement “A Turing machine con’t solve Halting problem” is B
False

lOMoARcPSD|23777972
True
Still an open question
None of these
51 Consider the following problem X D

Given a Turing machine M over the input alphabet ∑ any state of M and a word w∈∑,
does the computation of M on w visit the state q?
Which of the following statements about X is correct?
X is decidable
X is undecidable but partially decidable
X is undecidable and not even partially decidable
X is not a decision problem
52 Given Turing machine M, produce a Turing machine M' such that M' halts and C
accepts x if M loops on x and M' loops otherwise.
Since we can't know if M will halt, we can't know if M' will halt.
Since we can't know if M' will halt, we can't know if M will halt.
No computer can produce M' from M.
None of the above
53 Given M that takes no input and either accepts or loops, produce M' that enumerates A
primes if M accepts and enumerates ∅∅ if M loops.
We can't decide if the machine will enumerate 5.
We can't decide if the machine will enumerate 6.
No computer can produce M' from M.

lOMoARcPSD|23777972
None of the above
54 Turing machine is more powerful than C
Finite automata
PDA
Both (a) and (b)
None of these
55 In one move the turing machine: D
May change its state
Write a symbol on the cell being scanned
Write a symbol on the cell being scanned
All of the above
56 Turing machine can be represented using: D
Transition table
Transition diagram
Instantaneous description
All of these
57 Which of the following is an extension to the basic model of turing machine: D
Multitude turing machine
Multi head turing machine
Offline turing machine

lOMoARcPSD|23777972
All of the above
58 Which of the following is the restricted model of turing machines D
Turing machine with semi-infinite tape
Multi stack machine
Offline turing machine
Both (a) and (b)
59 Which of the following statement is worng? D
Turing machine is a simple mathematical model of general purpose computer.
Turing machine is more powerful than finite automata.
Turing machine can be simulated by a general purpose computer.
All of these
60 An instantaneous description of turing machine consists of B
Present state and input to be processed
Present state and entire input to be processed
Present input only
None of these
61 Which of the following statement is false? C
turing machine was developed by Alan turing
PDA is less powerful than turing machine
Both (a) and (b)

lOMoARcPSD|23777972
None of these
62 In multi head turing machine there are A
More than one heads of the turing machine
More than one input tapes of turing machine
Similar to the basic model of turing machine
All of these
63 Assume statements S1 and S2 defined as : C
S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive

enumerable respectively.
S2 : The set of all Turing machines is countable.
Which of the following is true ?
S1 is correct and S2 is not correct.
Both S1 and S2 are correct.
Both S1 and S2 are not correct.
S1 is not correct and S2 is correct
64 Which of the following is the most general phase structured grammar ? B
Regular
Context-sensitive
Context-sensitive
None of the above

lOMoARcPSD|23777972
65 Following grammar A
S-> bS
S -> b
S -> aA
A -> bA
Type -3 grammar
Type -2 grammar
Type -1 grammar
Type -0 grammar
66 Finite state machine___________recognize palindromes. B
Can
Can not
May
May not
67 What is the reason behind a Turing machine is more powerful than finite state C
machine FSM?
Turing machine head movement is continued to one direction
Turing machine head moment is in both directions i.e. left moment and right moment
as well.
Turing machine has capability remember arbitrary long sequence of input string

lOMoARcPSD|23777972
All are correct
68 The language L = {anbnan| n≥ 1} is recognized by D
Turing Machine
PDA
Post machine
All are correct
69 If a Turing machine halts for each and every world of a language L and rejects other, C
then L is said to be
Recursive enumerable
Recursive
Context Free Language
None of these
70 A universal Turing machine is a A
Reprogrammable turing machine
Two-tape Turing machine
Single tape Turing machine
None of them
71 The difference between a read-only Turing machine and a two-way finite state C
machine is
Head movement
Finite control

lOMoARcPSD|23777972
Storage capacity
power
72 Which is correct regard an off-line Truing machine? A
An offline Turing machine is a special type of multi-tape turing machine
An offline Turing machine is a kind of multi-tracks Truing machine
An offline Turing machine is a kind of single-track Turing machine
None of them
73 Which of the following statement is wrong? D
Power of NTM and TM is same
For n ≥ 2, NPDA has some power as a TM
For n ≥ 2, NPDA has some power as a TM
Power of NTM and TM is not same
74 Four pairs are following; in each pair both objects have some common thing. Choose D
the odd pair;
TM,2PDA
(Computer, UTM)
(2PDA, nPDA)
(FA,PDA)
75 We think of a Turing machine’s transition function as a B
Computer system
Software

lOMoARcPSD|23777972
Hardware
All of them
76 Which of the following is the most general phase-structure grammar?
Regular Grammar
Context-sensitive Grammar
Context free Grammar
None of these
77 A context free grammar is : C
type 0
type 1
type 2
type 3
78 Context free grammar(CFG) can be recognized by C
Finite state automaton
2-way linear bounded automata
Push down automata
Both B & C
79 Which one is false C
L is recursive then TM halts for every x belongs to L
If L & complement L both are recursive Enumerable then L is recursive

lOMoARcPSD|23777972
Complement of recursive language is again recursive
Every recursive enumerable language is recursive
80 The family of recursive languages is not closed under which of the following D
operations
Complementation
Union
Intersection
None of these
81 Choose which of the following is not correct B
Recursive languages closed under complementation
Set of recursively enumerable languages closed under union
If a language and its complement are regular, then the language must be recursive
None of these
82 Any language generated by unrestricted grammar is B
Not recursively enumerable
Recursive
Recursively enumerable
None of these
83 Let A is set of recursive languages and B is set of enumerable languages then A
A and B are disjoint sets
A and B are same sets

lOMoARcPSD|23777972
B is subset of A
A is subset of B
84 Which of the following statement is true C
A context sensitive language is recursive
A set X is recursive if we have a algorithm to decide whether a given element belongs

to X or not
A recursive set is recursively enumerable
All of the above
85 The union of two recursively enumerable languages is C
Recursive enumerable
Recursive
Not recursive
None
86 Which one of the following properties of recursively enumerable set is not recursively B
enumerable
L contains at least 10 numbers
L-Lu≠ᶲ
L≠ᶲ
None
87 Which one of the following properties of recursively enumerable set is recursively C

enumerable

lOMoARcPSD|23777972
L contains at least 10 numbers
L≠ᶲ
L-Lu≠ᶲ
None
88 Universal language is A
Recursive
Decidable
Non-recursively enumerable
recursively enumerable
89 Let L and complement of L be a pair of complementary languages then C
Both L and L’ are recursive
neither L and L’ is recursively enumerable
Any of the above
None of the above
90 The complement of recursive is D
Can’t say
Recursive
Non recursive
none
91 A problem whose language is recursive is said to be C

lOMoARcPSD|23777972
Can’t say
Decidable
Undecidable
None
92 Select the false statement C
The blank tape halting problem is undecidable
The Turing machine halting problem is undecidable
The Turing machine halting problem is decidable
None of the above
93 Which of the statement is correct C
If the emptiness problem is undecidable Type 0 grammars, then it is also undecidable

for type3 grammars
If the emptiness problem is decidable Type 3 grammars, then it is also decidable for
type 0 grammars
If the emptiness problem is decidable Type 0 grammars, then it is also decidable for
type3 grammars
None of the above
94 The problem of determining that a Turing machine would halt after giving a Yes/No B
output is
Decidable
Unsolvable
Solvable

lOMoARcPSD|23777972
None of the above
95 Let G is unrestricted grammar. Then the problem of determining whether or not C

L(G)=ᶲ
Can’t say
Decidable
Undecidable
None
96 What can you say about the membership problem For type 0 grammars D
Partially decidable
Decidable
UnDecidable
None
97 Correct hierarchical relationship among context- free, right-linear, and context- D

sensitive language is
context-free ⊂ right-linear ⊂ context-sensitive
context-free ⊂ context-sensitive ⊂ right-linear
context-sensitive ⊂ right-inear ⊂context-free
right-linear ⊂context-free ⊂context-sensitive

lOMoARcPSD|23777972
98 L and ~L are recursive enumerable then L is D
Regular
Context free
Context sensitive
Recursive
99 Which of the following is the most general phase structured grammar ? C
Regular
Context free
Context sensitive
None
100 Which of the following problems are decidable? D
1) Does a given program ever produce an output?
2) If L is context-free language, then, is ~L also context-free?
3) If L is regular language, then, is ~L also regular?
4) If L is recursive language, then, is ~L also recursive?
1,2,3,4,
1,2
2,3,4
3,4
101 The language L={0ᵐ1ᵐ0ᵐ| m ≥ 1} is a D

lOMoARcPSD|23777972
Regular language
Context free language
Both
None of these
102 The finite automata accept the following language: B
context free language
Regular language
Context sensitive language
All the above
103 Which of the following is complement of a? C
Recursive language is recursive
Recursively enumerable language is recursively enumerable
Recursive language is either recursive or recursively enumerable
None of these
104 If nL can be recognized by a multitape TM with time complexity f, then L can be A

recognized by a one-tape machine with time complexity DSD
O( f 2)
o( f 2)
O( h 2)
O( h)
105 If T is a TM recognizing L, and T reads every symbol in the input string, τT(n) ≥ 2n + C

lOMoARcPSD|23777972
2, then any language that can be accepted by a TM T with τT(n) = 2n + 2 is
Regular
Not regular
Uncertain
None
106 Which of the following problems is solvable ? A
Writing a universal Turing machine
Determining of an arbitrary turing machine is an universal turing machine
Determining of a universal turing machine can be written for fewer than k instructions
for some k
Determining of a universal turing machine and some input will halt
107 Which of the following statements is false ? D
Halting problem of Turing machines is undecidable
Determining whether a context-free grammar is ambiguous is undecidable
Given two arbitrary context-free grammars G1 G2 and it is undecidable whether L (G1)

= L (G2).
Given two regular grammars G1 G2 and it is undecidable whether L (G1) = L (G2) D
108 Universal TM influenced the concept of
stored program computers
interpretative implementation of programming language
computability

lOMoARcPSD|23777972
all of these
109 Number of external states of a UTM should be atleast B
110 The statement, “A TM can’t solve halting problem” is A
true
false
still an open question
All the above
111 A total recursive function is a D
partial recursive function
premitive recursive function
both
None
112 If L can be recognized by a TM T with a doubly infinite tape, and τt = f, then L can be A
recognized by an ordinary TM with time complexity
O(f)
o(f)
O(h)

lOMoARcPSD|23777972
o(f)
113 Consider an undirected graph G with 100 nodes. The maximum number of edges to be C
included in G so that the graph is not connected is
5689
4931
4851
4321
114 Consider three decision problems P1, P2 and P3. It is known that P1 is decidable C
and P2 is undecidable. Which one of the following is TRUE?
P3 is decidable if P1 is reducible to P3
P3 is undecidable if P3 is reducible to P2
P3 is undecidable if P2 is reducible to P3
P3 is decidable if P3 is reducible to P2’s complement
115 Consider the languages A
L1 = {anbncm|n, m > 0} and L2 = {anbmcm|n, m > 0}
Which one of the following statements is false?
L1 ∩ L2 is a CFL
L1 ∪ L2 is a CFL
L1 ∪ L2 is inherently ambiguous
L1 ∩ L2 is a CSL
116 L1 = {an + m bn cm|n, m ≥ 0} D

lOMoARcPSD|23777972
L2 = {an + m bn + m cm|n, m ≥ 0}
L3 = {an + m bn + m cm + n|n, m ≥ 0}
Which of these languages are not CF.
L1 only
L3 only
L1 and L2
L3 and L2
117 Which one of the following is the strongest correct statement about a finite D
language L over a finite alphabet Σ?
L is undecidable
L is recursive
L is CSL
L is regular set
118 Which of the following statements is TRUE? C
infinite union of regular sets is regular
infinite union of finite sets is regular
finite union of finite sets is regular
complement of a finite set need not be regular
119 It is undecidable, whether C
an arbitrary TM has 15 states
an arbitrary TM halts after 10 steps

lOMoARcPSD|23777972
an arbitrary TM ever prints a specific letter
an arbitrary TM accepts a string w in 5 steps
120 Assuming P != NP, which of the following is true ? B
NP-complete = NP
NP-complete ᴖP = ᶲ
NP-hard = NP
P = NP-complete
121 Let S be an NP-complete problem and Q and R be two other problems not known to B
be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to
R. Which one of the following statements is true? (GATE CS 2006)
R is NP-complete
R is NP-hard
Q is NP-complete
Q is NP- hard
122 Let X be a problem that belongs to the class NP. Then which one of the following is C
TRUE?
There is no polynomial time algorithm for X.
If X can be solved deterministically in polynomial time, then P = NP.
If X is NP-hard, then it is NP-complete
X may be undecidable
123 Which of the following statements are TRUE? B
(1) The problem of determining whether there exists a cycle in an undirected graph is

lOMoARcPSD|23777972
in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is
in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time

algorithm to solve A.
1,3
1,2,3
1,2
2,3
124 Which of the following is true about NP-Complete and NP-Hard problems.
The first problem that was proved as NP-complete was the circuit satisfiability
problem.
NP-complete is a subset of NP Hard
All the above
None of these
125 A problem in NP is NP-complete if B
It can be reduced to the 3-SAT problem in polynomial time
The 3-SAT problem can be reduced to it in polynomial time
It can be reduced to any other problem in NP in polynomial time
some problem in NP can be reduced to it in polynomial time

lOMoARcPSD|23777972
INTERNAL QUESTION PAPERS

MALLA REDDY ENGINEERING COLLEGE FOR WOMEN
MID-I
II-CSE-A,B,C,D Formal Languages and Automata Theory Marks :40
PART-A
a) Define Finite Automata and its block diagram? 2M

b) Differentiate NFA and DFA? 2M
c) Construct the regular expression for the language containing all strings having any
number of a’s and b’s except null string? 2M
d) Prove (a+b)*= a*(ba*)* 2M
e) Define left linear and right linear grammars? 2M
PART-B
1.Explain in detail the conversion of NFA to DFAwith an example?

or
2. The moore machine to determine residue mod3 for binary number is given below. Convert it
to mealy equivalent machine?
Q 0 1 λ
q0 q0 q1 0
q1 q2 q0 1
q2 q1 q2 2
3. Construct finite automata to accept the regular expression? (0+1)*(00+11)*(0+1)*

or
4. Define the following and give examples?
i)CFG ii)derivation tree iii)Sentential form iv)Right most and left most derivation of strings
5.(a) Design the PDA for the language that accepts strings with na (w) < nb (w) where w∊(a+b)*
(b) Let G be CFG that generates the set of palindromes given by S→ aSa / bSb / a / b.
Find the PDA that accepts L(G)
or
6. Define and give example for CNF, GNF, and Pumping Lemma for CFL

lOMoARcPSD|23777972
MALLA REDDY ENGINEERING COLLEGE FOR WOMEN
MID-II
II-CSE-A,B,C,D Formal Languages and Automata Theory Marks :40
PART-A
a) Explain about counter machine with neat diagram? 2M

b) Explain basic model of Turing Machine? 2M
c) What is decidability of Problems? 2M
d) Explain about Turing Reducibility? 2M
e) what is universal Turing machine 2M
PART-B
1(a) Design the PDA for the language that accepts strings with na (w) < nb (w) where w∊(a+b)*
(b) Let G be CFG that generates the set of palindromes given by S→ aSa / bSb / a / b.
Find the PDA that accepts L(G)
or
2. Define and give example for CNF, GNF, and Pumping Lemma for CFL
3. Construct a Turing Machine for checking the palindrome of string of even length.
or
4. Explain about the Context Sensitive Language and Design a LBA for the language
L={an bn cn / n≥1}
5(a) Explain Chomsky Hierarchy of Languages?
(b) Obtain the solution for the following system of post correspondence problem
A={100,0,1} B={1,100,00}
or
6.(a). Explain about Universal Turing Machine?
(b). Explain the classes of P and NP problems?

lOMoARcPSD|23777972
External Question papers

lOMoARcPSD|23777972

lOMoARcPSD|23777972

lOMoARcPSD|23777972

lOMoARcPSD|23777972
REFERENCES
1. Yan, Song Y. (1998). An Introduction to Formal Languages and Machine Computation.
Singapore: World Scientific Publishing Co. Pte. Ltd. pp. 155–156.
2. Jump up^ Chakraborty, P., Saxena, P. C., Katti, C. P. 2011. Fifty Years of Automata
Simulation: A Review. ACM Inroads, 2(4):59–
70. http://dl.acm.org/citation.cfm?id=2038893&dl=ACM&coll=DL&CFID=65021406&CFTOK
EN=86634854
3. Jump up^ Jirí Adámek and Vera Trnková. 1990. Automata and Algebras in Categories.
Kluwer Academic Publishers:Dordrecht and Prague
4. Jump up^ S. Mac Lane, Categories for the Working Mathematician, Springer, New
York (1971)
5. Jump up^ Cartesian closed category Archived November 16, 2011, at the Wayback
Machine.
6. Jump up^ The Category of Automata Archived September 15, 2011, at the Wayback
Machine.
7. Jump up^ http://www.math.cornell.edu/~worthing/asl2010.pdf James

Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North
American Annual Meeting, March 17, 2010
8. Jump up^ Aguiar, M. and Mahajan, S.2010. "Monoidal Functors, Species, and Hopf
Algebras".
9. Jump up^ Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Information and
Computation 88:105–155

lOMoARcPSD|23777972
10. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata
Theory, Languages, and Computation (2nd Edition). Pearson Education. ISBN 0-201-44124-1.
11. Michael Sipser (1997). Introduction to the Theory of Computation. PWS

Publishing. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp. 29–122.
Section 4.1: Decidable Languages, pp. 152–159. Section 5.1: Undecidable Problems from
Language Theory, pp. 172–183.
12. Elaine Rich (2008). Automata, Computability and Complexity: Theory and Applications.
Pearson. ISBN 0-13-228806-0.
13. Salomaa, Arto (1985). Computation and automata. Encyclopedia of Mathematics and Its
Applications. 25. Cambridge University Press. ISBN 0-521-30245-5. Zbl 0565.68046.
14. Anderson, James A. (2006). Automata theory with modern applications. With
contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-
8. Zbl 1127.68049.
15. Conway, J.H. (1971). Regular algebra and finite machines. Chapman and Hall
Mathematics Series. London: Chapman & Hall. Zbl 0231.94041.
16. Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French
by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.

Cse Flat Digital Notes Full 2020 21

Uploaded by

Copyright:

Available Formats

Cse Flat Digital Notes Full 2020 21

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

Cse Flat Digital Notes Full 2020 21

Uploaded by

Copyright:

Available Formats

lOMoARcPSD|23777972

CSE-FLAT Digital Notes-FULL (2020-21)

Computer Science (Jawaharlal Nehru Technological University, Hyderabad)

Studocu is not sponsored or endorsed by any college or university

Dr. SUBBA REDDY Mr. K.V. RAJESH

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

foundations of computer science from the perspective of formal languages.

• Classify machines by their power to recognize languages.

• Employ finite state machines to solve problems in computing.

• Explain deterministic and non-deterministic machines.

• Comprehend the hierarchy of problems arising in the computer sciences.

to recognize the languages.

help of Chomsky hierarchy.

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

FORMAL LANGUAGES & AUTOMATA THEORY

Introduction to Finite Automata: Structural Representations, Central Concepts of Automata

Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular

Context-Free Grammars: Definition , Derivations Using a Grammar, Leftmost and Rightmost

Push Down Automata: Construction of Pushdown Automaton, the Languages of a PDA,

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Undecidability: A Language that is Not Recursively Enumerable, An Undecidable Problem

1. Introduction to Automata Theory, Languages, and Computation, 3nd Edition, John E.

1. Introduction to Languages and the Theory of Computation, John C Martin, TMH.

3. A Text book on Automata Theory, P. K. Srimani, Nasir S. F. B, Cambridge Universit

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

3.12 Deterministic PDAs and DCFLs 71

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

Introduction to Finite Automata

• States: finite set Q, whose definition depends on the type of automaton.

Finite State Machines

if there are n bits of storage, there are2npossible states

MRECW (Autonomous Institution-UGC, Govt. of India) Page 1

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

• Two types– both describe what are called regular languages

MRECW (Autonomous Institution-UGC, Govt. of India) Page 2

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

1.1 Structural Representations

1. Finite set of states, typically Q.

Fig1: The figure above shows a diagrammatic representation of a generic automation.

MRECW (Autonomous Institution-UGC, Govt. of India) Page 3

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

MRECW (Autonomous Institution-UGC, Govt. of India) Page 4

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

Kleene Closure / Plus

1.3Deterministic Finite (-state) Automata

Thus, a DFA conceptually consists of 3 parts:

MRECW (Autonomous Institution-UGC, Govt. of India) Page 5

Downloaded by 21WH1A1218 P. LAKSHMI VARSHITHA (21wh1a1218@bvrithyderabad.edu.in)

Formal Languages & Automata Theory Department of CSE

Deterministic Finite Automata (DFA):