DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS3452-THEORY OF COMPUTATION

Question Bank

II YEAR A&B|| BATCH : 2022-2026

Vision of Institution
To build Jeppiaar Engineering College as an Institution of Academic Excellence in Technical
education and Management education and to become a World Class University.
Mission of Institution

M1 To excel in teaching and learning, research and innovation by promoting the

principles of scientific analysis and creative thinking

To participate in the production, development and dissemination of knowledge and

M2
interact with national and international communities

To equip students with values, ethics and life skills needed to enrich their lives and
M3
enable them to meaningfully contribute to the progress of society

M4 To prepare students for higher studies and lifelong learning, enrich them with the
practical and entrepreneurial skills necessary to excel as future professionals and
contribute to Nation’s economy

Program Outcomes (POs)

Engineering knowledge: Apply the knowledge of mathematics, science, engineering
PO1 fundamentals, and an engineering specialization to the solution of complex engineering
problems.
Problem analysis: Identify, formulate, review research literature, and analyze complex
PO2 engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.
Design/development of solutions: Design solutions for complex engineering problems
and design system components or processes that meet the specified needs with
PO3 appropriate consideration for the public health and safety, and the cultural, societal, and
environmental considerations
Conduct investigations of complex problems: Use research-based knowledge and
PO4 research methods including design of experiments, analysis and interpretation of data,
and synthesis of the information to provide valid conclusions.
Modern tool usage: Create, select, and apply appropriate techniques, resources, and
PO5 modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.
The engineer and society: Apply reasoning informed by the contextual knowledge to
PO6 assess societal, health, safety, legal and cultural issues and the consequent responsibilities
relevant to the professional engineering practice.
Environment and sustainability: Understand the impact of the professional engineering
PO7 solutions in societal and environmental contexts, and demonstrate the knowledge of, and
need for sustainable development.
 Ethics: Apply ethical principles and commit to professional ethics and responsibilities
PO8 and norms of the engineering practice.
Individual and team work: Function effectively as an individual, and as a member or
PO9 leader in diverse teams, and in multidisciplinary settings.
Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and
PO10 write effective reports and design documentation, make effective presentations, and give
and receive clear instructions.
Project management and finance: Demonstrate knowledge and understanding of the
PO11 engineering and management principles and apply these to one’s own work, as a member
and leader in a team, to manage projects and in multidisciplinary environments.
Life-long learning: Recognize the need for, and have the preparation and ability to
PO12 engage in independent and life-long learning in the broadest context of technological
change.

Vision of Department
To emerge as a globally prominent department, developing ethical computer professionals,
innovators and entrepreneurs with academic excellence through quality education and research .
Mission of Department

To create computer professionals with an ability to identify and formulate the

M1
engineering problems and also to provide innovative solutions through effective
teaching learning process.

M2 To strengthen the core-competence in computer science and engineering and to create

an ability to interact effectively with industries.

M3 To produce engineers with good professional skills, ethical values and life skills for the
betterment of the society.

M4 To encourage students towards continuous and higher level learning on technological

advancements and provide a platform for employment and self-employment.

Program Educational Objectives (PEOs)

PEO1 To address the real time complex engineering problems using innovative approach
with strong core computing skills.

PEO2 To apply core-analytical knowledge and appropriate techniques and provide

solutions to real time challenges of national and global society

PEO3 Apply ethical knowledge for professional excellence and leadership for the
betterment of the society.

PEO4 Develop life-long learning skills needed for better employment and
entrepreneurship
Program Specific Outcomes (PSOs)

Students will be able to

An ability to understand the core concepts of computer science and engineering and to
PSO1 enrich problem solving skills to analyze, design and implement software and hardware
based systems of varying complexity.

To interpret real-time problems with analytical skills and to arrive at cost effective and
PSO2 optimal solution using advanced tools and techniques.

An understanding of social awareness and professional ethics with practical proficiency in

the broad area of programming concepts by lifelong learning to inculcate employment and
PSO3
entrepreneurship skills.

BLOOM TAXANOMY LEVELS(BTL)

BTL6: Creating.,
BTL 5: Evaluating.,
BTL 4: Analyzing.,
BTL 3: Applying.,
BTL 2: Understanding.,
BTL 1: Remembering
 SYLLABUS

CS3452 THEORY OF COMPUTATION LTPC

300 3
COURSE OBJECTIVES:
 To understand foundations of computation including automata theory
 To construct models of regular expressions and languages.
 To design context free grammar and push down automata
 To understand Turing machines and their capability
 To understand Undecidability and NP class problems

UNIT I AUTOMATA AND REGULAR EXPRESSIONS 9

Need for automata theory - Introduction to formal proof – Finite Automata (FA) – Deterministic Finite
Automata (DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA –
Finite Automata with Epsilon transitions – Equivalence of NFA and DFA- Equivalence of NFAs with and
without ε-moves- Conversion of NFA into DFA – Minimization of DFAs.

UNIT II REGULAR EXPRESSIONS AND LANGUAGES 9

Regular expression – Regular Languages- Equivalence of Finite Automata and regular expressions –
Proving languages to be not regular (Pumping Lemma) – Closure properties of regular languages.

UNIT III CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA 9

Types of Grammar - Chomsky‘s hierarchy of languages -Context-Free Grammar (CFG) and Languages –
Derivations and Parse trees – Ambiguity in grammars and languages – Push Down Automata (PDA):
Definition – Moves - Instantaneous descriptions -Languages of pushdown automata – Equivalence of
pushdown automata and CFG-CFG to PDA-PDA to CFG – Deterministic Pushdown Automata.

UNIT IV NORMAL FORMS AND TURING MACHINES 9

Normal forms for CFG – Simplification of CFG- Chomsky Normal Form (CNF) and Greibach Normal
Form (GNF) – Pumping lemma for CFL – Closure properties of Context Free Languages –Turing
Machine : Basic model – definition and representation – Instantaneous Description – Language
acceptance by TM – TM as Computer of Integer functions – Programming techniques for Turing
machines (subroutines).

UNIT V UNDECIDABILITY 9
Unsolvable Problems and Computable Functions –PCP-MPCP- Recursive and recursively enumerable
languages – Properties - Universal Turing machine -Tractable and Intractable problems - P and NP
completeness – Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF SAT problems.

OUTCOMES:
At the end of this course, the students will be able to:
C211.1: Construct automata theory using Finite Automata
C211.2: Write regular expressions for any pattern
C211.3: Design context free grammar and Pushdown Automata
C211.4: Design Turing machine for computational functions
C211.5: Differentiate between decidable and undecidable problems

TOTAL:45 PERIODS

INDEX
Unit # Ref. Book
J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata

Unit 1 Theory, Languages and Computations”, Second Edition, Pearson

Education, 2003.
J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata

Unit 2 Theory, Languages and Computations”, Second Edition, Pearson

Education, 2003.
J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata

Unit 3 Theory, Languages and Computations”, Second Edition, Pearson

Education, 2003.
J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata

Unit 4 Theory, Languages and Computations”, Second Edition, Pearson

Education, 2003.
J.E.Hopcroft, R.Motwani and J.D Ullman, “Introduction to Automata

Unit 5 Theory, Languages and Computations”, Second Edition, Pearson

Education, 2003.
 UNIT I AUTOMATA AND REGULAR EXPRESSIONS

Need for automata theory - Introduction to formal proof – Finite Automata (FA) – Deterministic Finite
Automata (DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA –
Finite Automata with Epsilon transitions – Equivalence of NFA and DFA- Equivalence of NFAs with and
without ε-moves- Conversion of NFA into DFA – Minimization of DFAs.

S. Question Course Blooms

No. Outcome Taxanomy
Level
Define
(a) Finite Automata (FA)
C211.1 BTL 1
(b) Transition Diagram NOV/DEC 2012
a) Finite Automata is a 5 tuples denoted by

A = (Q, ∑, δ, q0, F) where

 Q is a finite set of states

1  ∑ is the finite set of input symbols
 δ is a transition function (Q X ∑  Q )
 q0 is the start state or initial state
 F is a set of final or accepting states
b) A diagram consisting of circles to represent states and directed
line segments to represent transitions between the states. One or
more actions (outputs) may be associated with each transition.
The diagram represents a finite state machine

2 State the Principle of induction. NOV/DEC 2012

If S(i) is true for n = i ,then it is to be proved that for all n > i , S(n) implies C211.1 BTL 1
S(n+1) then S(n) is true for all n ≥ i..

What is proof by contradiction? MAY/JUNE 2012

To prove P→Q
3 C211.1 BTL 1
Prove by contradiction, that is assume P and ¬Q are True then derive a
Known fact will become false that is contradiction to our assumption so
that the given one is true
Define ε-closure(q) with an example. MAY/JUNE 2012
4 The set of all states reachable from a given state q using ε transitions only. We
use ε -closure to denote the set of all vertices p such that there is a path from q C211.1 BTL 1
to p labeled ε.
5 Differentiate between proof by contradiction and proof by
contrapositive. APR/MAY 2011
C211.1 BTL 1
To prove P→Q Prove by contradiction, that is assume P and ¬Q and
derive a contradiction and Prove the contra positive, that is
 assume ¬Q and show ¬P.

Construct a DFA for the language over {0, 1}* such that it contains
“000” as a substring. APR/MAY 2011
C211.1 BTL 3
1 0,1
6
Q 0 Q 0 0Q 0 Q0
0 1 2 3
1 1

What is structural induction? NOV/DEC 2011

Let S(X) be a statement about the structures X that are defined by some
C211.1 BTL 1
particular recursive definition.
7 1. As a basis, Prove S(X) for the basis structure(s) X.
2. For inductive step, take a structure X that the recursive definition
says is formed from Y1, Y2,....Yk. Assume the statements
S(Y1),...,S(Yk) and use these to prove S(X).

State the difference between NFA and DFA. NOV/DEC 2011,

NOV/DEC 2018
C211.1 BTL 1

Construct deterministic finite automata to recognize odd number of

1’s and even number of 0’s? 1 APR/MAY 2010
B C211.1 BTL 3
0 A0 1 0 0
9
1
C D
1

10 Find the set of strings accepted by the finite automata. NOV/DEC

2010
C211.1 BTL3
0, 1
 (0+1)* or L={ε, 0, 1, 00, 01, 10, 11,............}

What is meant by DFA MAY/JUNE

2013,NOV/DEC 2016
11 C211.1 BTL 1
DFA—also known as deterministic finite state machine—is a finite state
machine that accepts/rejects finite strings of symbols and only produces a
unique computation (or run) of the automaton for each input string.

Define the term Epsilon transition MAY/JUNE 2013

In the automata theory, a nondeterministic finite automaton with ε-moves
12 (NFA-ε)(also known as NFA-λ) is an extension of nondeterministic finite C211.1 BTL 1
automaton(NFA), which allows a transformation to a new state without
consuming any input symbols

Draw the transition diagram for an identifier NOV/DEC

2013
13 C211.1 BTL 3
letter letter,digit

What is non deterministic finite automata? NOV/DEC

2013
C211.1 BTL 1
In automata theory, a nondeterministic finite automaton (NFA), or
14
nondeterministic finite state machine, is a finite state machine that (1) does not
require input symbols for state transitions and (2) is capable of transitioning to
zero or two or more states for a given start state and input symbol

Define Deductive Proof. NOV/DEC 2014

A Deductive proof consists of a sequence of statements whose truth
C211.1 BTL 1
leads us from some initial statement, called the ‘hypothesis’ to a
15 ‘conclusion’ statement.
“if H then C”

Ex: if x >= 4 then 2x >= x2

Design DFA to accept strings over ∑ = (0,1) with two consecutive 0’s.
NOV/DEC 2014 C211.1 BTL 3
1 0,1
16
q0 q1 q3
0 0

17 What is a finite automaton? NOV/DEC 2015

A finite automaton (FA) is a simple idealized machine used to recognize
C211.1 BTL 1
patterns within input taken from some character set (or alphabet) C. The
job of an FA is to accept or reject an input depending on whether the
 pattern defined by the FA occurs in the input.

Finite Automata is a 5 tuples denoted by

A = (Q, ∑, δ, q0, F) where

 Q is a finite set of states

 ∑ is the finite set of input symbols
 δ is a transition function (Q X ∑  Q )
 q0 is the start state or initial state
 F is a set of final or accepting states

Draw a Non-deterministic finite automata to accept strings

containing the substring 0101. MAY/JUNE 2016
C211.1 BTL3
18
0,1 0,1
0 1 0 1

Define the languages described by DFA and NFA.

L(DFA) = { w / δ‟(q0,w) is in F}.It is the set of strings w that take the
C211.1 BTL 1
19 start state q0 to one of the accepting states.

L(NFA)= { w / δ‟(q0,w)∩F≠ɸ}.It is the set of strings w such that

δ‟(q0,w)contains at least one accepting state.

Define extended transition function for a DFA.

The extended transition function δ‟: QX∑* €Q is defined as
C211.1 BTL 1
follows.
20
(i) δ’(q, ε ) = q (ε - Empty)

(ii)Suppose w is a string of form xa(w= xa), w€∑*and q€Q , then

δ’(q, w)= δ( δ’(q, x),a)

Construct a DFA that accepts input string of 0,s and 1’s that end
with 11. 0
C211.1 BTL3
1 1
21
q0 q1 q2
0 1
0

22 Define extended transition function for a NFA.

The extended transition function δ‟: QX∑*2 Q is defined as follows.
(i) δ’(q, ε ) = {q} C211.1 BTL3
(ii) (ii) Suppose w is of the form xa where a is the final symbol of w and x
 is the rest of w. δ’(q,x)= {p1, p2, p3...pk}
k
U δ(pi ,a) = {r1, r2, r3,.....rm}
i=1
Therefore δ‟(q,w) ={r1, r2, r3,.....rm}

Construct a DFA for the language L = { an b , n ≥ 0}.

a
23 C211.1 BTL3
b
q0 q1

What is deductive proof?

A deductive proof consists of a sequence of statements, which starts
24 C211.1 BTL3
from a hypothesis, or a given statement to a conclusion. Each step is
satisfying some logical principle.

Define − Transition Diagram.

Transition diagram is a directed graph in which the vertices of the graph
C211.1 BTL3
25 correspond to the states of FA. If there is a transition from state q to
state p on input a, then there is an arc labelled ‘a’ from q to p in the
Transition Diagram.

List out the operations on strings.

The various operations performed on strings are:
C211.1 BTL3
1. Length of a string
2. Empty string
3. Concatenation of string
26
4. Reverse of a string
5. Power of an alphabet
6. Kleene closure
7. Substring
. 8. Palindrome

List out the applications for finite automaton.

Text editors and lexical analyzers are designed as finite state systems. A
C211.1 BTL3
27 lexical analyzer scans the symbols of a program to locate strings
corresponding to identifiers, constants etc, and has to remember limited
amount of information.

Define TOC
Theory of Computation is the branch that deals with how efficiently
C211.1 BTL3
28 problems can be solved on a model of computation, using an algorithm.
The field is divided into three major branches: automata theory,
computability theory, and computational complexity theory.
 Give some examples for additional forms of proof.
29 1. Proofs about sets 2. Proofs by contradiction 3. Proofs by counter
C211.1 BTL3
examples.

Design FA to check whether given unary number is divisible by

three.
C211.1 BTL3

30 1 1 1 1
1 q0 q1 q1 q3

Write short notes on Minimization of DFA?

Reducing the number of states from given FA C211.1 BTL1

- First find out which two states are equivalent we than replace those
31 two states by one representative state.
- For findingthe equivalent states we will apply the followingrule - The
two states S1 & S2 are equivalent if and only if both the states arefinal
or non-final

When two states are equivalent and distinguishable?

We say that two states p and q are equivalent iff for each input string x ,
32 δ(p,x) is an accepting state iff δ(q,x) is an accepting state. p is C211.1 BTL1
distinguishable from q if there exists an x such that δ(p,x) is in F and
δ(p,x) is not in F or vice versa.

PART B
1 Explain the different forms of proof with examples. (8)
NOV/DEC 2012
C211.1 BTL 1
2 Prove that, if L is accepted by an NFA with ε-transitions, then L is
accepted by an NFA without ε-transitions.(8) NOV/DEC 2012,
C211.1 BTL 1
NOV/DEC 2013

3
Convert an NFA to a DFA given NFA M = (Σ,Q,δ,q0, F) Σ={0,1},
Q = { q0, q1, q2 ,q3},F= { q0}, C211.1 BTL 3

4 Construct a DFA that accepts the following

(i) L={ x € {a,b}:|x|a = odd and |x|b = even}. (10) NOV/DEC
C211.1 BTL 3
2012
 (ii) Binary strings such that the third symbol from the right end
is 1. (10) MAY/JUNE 2012
(iii) All strings w over {0,1} such that the number of 1’s in w is 3
mod 4. (8) NOV/DEC 2011
(iv) Set of all strings with three consecutive 0’s.(10) NOV/DEC
2010

5
Prove by induction on n that (6)
C211.1 BTL 3
MAY/JUNE 2012

6 Construct an NFA without ε-transitions for the NFA give below. (8)
MAY/JUNE 2012
C211.1 BTL 3
0 1

Q ε Q
1
0

Construct an NFA accepting binary strings with two consecutive

7 0’s. (8) MAY/JUNE 2012
C211.1 BTL 3
8 Prove that there exists a DFA for every ε-NFA. (8)
APR/MAY 2011 Refer Notes
C211.1 BTL 1
9
Compute ε closure (ii) Convert the automaton to a DFA
C211.1 BTL 3
ε a b c
P { ф} {p} {q} {r}
q {p} {q} {r} { ф}
r {q} {r} { ф} {p}

10 Prove that there exists a DFA for every NFA.(8) MAY/JUNE 2013,
NOV/DEC 2018
C211.1 BTL 4
11 (i) Prove that every tree has ‘e’ edges and ‘e+1’ nodes.
NOV/DEC 2014
C211.1 BTL 4
2n+1 n+2
(ii) Prove that for every integer n>=0 the number 4 +3
is a multiple of 1 NOV/DEC 2014

12 (i) Show that the maximum edges in a graph (with no self-loops

or parallel edges) is given by (n(n-1))/2 where ‘n’ is the
C211.1 BTL 4
number of nodes.(8) APR/MAY 2011
(ii) Prove that is not rational. (8)
 NOV/DEC 2011

13 Conversion of ɛ-NFA to NFA then to DFA NOV/DEC 2018

C211.1 BTL 3
1
1D 0 1
ɛ ɛ
A B C

14 Explain the DFA minimization algorithm with an example. (10)

NOV/DEC 2014
C211.1 BTL 1
15 Minimization of Automaton NOV/DEC 2018

State a b
C211.1 BTL 3
*1 2 3

2 4 5

3 6 7

4 5 4

5 7 5

6 2 7

*7 7 4

16 Construct minimized automata for the following automata to define

the same language. (10) APR/MAY 2011

a b C211.1 BTL 3

q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
 q7 q6 q3

UNIT II REGULAR EXPRESSIONS AND LANGUAGES

Regular expression – Regular Languages- Equivalence of Finite Automata and regular expressions –
Proving languages to be not regular (Pumping Lemma) – Closure properties of regular languages.

S. Question Course Blooms

No. Outcome Taxanomy
Level
Define regular expression and give an example C211.2 BTL 1
1
The language accepted by finite automata are easily described by
simple expression called regular expression. Example : a*b
State the relations among regular expression, deterministic C211.2 BTL4
finite automata, non deterministic finite automaton and finite
automaton with epsilon transition. APR/MAY 2010
Every Regular language defined by a regular expression ia also
2
defined by the finite automata with epsilon transition . Finite
automata with epsilon transition can be converted into Non
deterministic finite automata and then converted into Deterministic
finite automata.

Write Regular Expression for the set of strings over {0.1} that BTL 3
have atleast one. NOV/DEC 2015
3
Regualr Expression = (0+1)*1

State the pumping lemma for regular languages. MAY/JUNE

2016, NOV/DEC 2018
C211.2 BTL 1
4 Let L be a regular language. Then there exists a constant n such
that for every string w in L ,|w|>n, z = uvw such that
(i)|uv|<n,
(ii) |v|>0 then uviw € L for all i.

Give a regular expression for the set of all strings having odd C211.2
5 number of 1’s
BTL 3
RE= 1(0+11)*

Give the regular expression for the set of all strings ending in C211.2
6 00.
BTL 3
Regular expression = (0+1)*00
 What are the applications of regular expression? C211.2
7 Regular expression in UNIX, Lexical analysis, Pattern searching
BTL 4

Write regular expressions for the following. C211.2

(i)Binary numbers that are multiple of 2. (0/1)*.
BTL3
(ii)Strings of a‟s and b‟s with no consecutive a‟s .
8 b* (abb*)(a / ε)
(iii) Strings of a‟s and b‟s containing consecutive a‟s.
(a/b)*aa(a/b)*

State Arden’s theorem.

Let P and Q be two regular expressions over ∑. If P does not
9 C211.2 BTL 1
contain null string ε over ∑ then R=Q+RP, it has the solution
R=QP*

Differentiate L* and L+ C211.2 BTL 1

L* denotes Kleene closure and is given by L* =

example : 0* ={ ε,0,00,000,…………………………………}
10 Language includes empty words also.

L+ denotes Positive closure and is given by L+=

example : 0+ ={ 0,00,000,…………………………………}
Language includes empty words also.

Construct a r.e for the language over the set ={a,b} in which C211.2 BTL 3
11 total number of a’s are divisible by 3
( b* a b* a b* a b*)*

Regular expression denoting a language over ∑ ={1} having (i) C211.2 BTL 3
even length of string (ii) odd length of a string.
12 (i) Even length of string R=(11)*

(ii) Odd length of the string R=1(11)*

What are the applications of pumping lemma? C211.2 BTL 1

Pumping lemma is used to check if a language is regular or not.
1. Assume that the language(L) is regular.
2. Select a constant ‘n’.
13 3. Select a string(z) in L, such that |z|>n.
4. Split the word z into u,v and w such that |uv|<=n and |v|>=1.
5. You achieve a contradiction to pumping lemma that there
exists an ‘i’ Such that uvi w is not in L.
Then L is not a regular language.
 What is the closure property of regular sets? C211.2 BTL 3
The regular sets are closed under union, concatenation and Kleene
closure.
r1Ur2= r1 +r2
14
r1.r2= r1r2
( r )*=r*
The class of regular sets are closed under complementation,
substitution, homomorphism and inverse homomorphism.

Lists on the closure properties of Regular sets. C211.2 BTL 1

15 Union, Concatenation, Complementation, Intersection, Transpose,
Substitutions, Homomorphism

What are the three methods of conversion of DFA to RE? C211.2 BTL 1

Regular Expression equation method

16
Arden’s Theorem.

State elimination technique,

Prove that (r*)*= r* for a regular expression r. C211.2 BTL 3

17
(r*)*== {ε, r, rr,……}=r*
Construct NFA for the regular expression a*b*. C211.2 BTL 3
MAY/JUNE 2012
18 a,b

q
1

Is regular set is closed under complementation?Justify. C211.2

MAY/JUNE 2012
Closure under complement

 If L is a regular language, over alphabet ∑

Complement of L=∑* - L

19  Let L = L(A) for DFA A = (Q, ∑, δ, q0, F)

BTL 4
 Complement of L = L(B) where DFA B = (Q, ∑, δ, q0, Q-
F)

 B is similar to A except accepting states of A have become

non-accepting states of B and vice-versa.
A string w is in L(B) iff δ’ (q0,w) is in Q-F which occurs iff w is
not in L(A).
20 Prove that the complement of a regular language is also C211.2 BTL 4
 regular. APR/MAY 2011
Complement of L1 is constructed from L1 by reversing the states
and the arrows in automata

Let L = {w:w ε {0,1}* w does not contain 00 and is not empty}. C211.2 BTL 3
Construct a regular expression that generates L. APR/MAY
21 2010

Regular Expression = (0+1)(1+10)*(101+1)*

Prove or disprove that the regular languages are closed under C211.2 BTL 4
concatenation. APR/MAY 2010.

Closure under concatenation

22  Since L and M are regular languages,they have regular

expressions

L=L(R) and M=L(S)

 Then L.M = L(R.S), by definition of regular expression

Construct NFA equivalent to the regular expression (0+1)01 C211.2 BTL 3

NOV/DEC 2013

23
Q 0,1 Q 0 Q 1 Q
0 1 2
3

Is the set of strings over the alphabet {0} of the form 0n where n C211.2 BTL 4
is not a prime is regular? Prove or disprove. NOV/DEC 2011

To prove this language is not regular, examine the complement

because the set of regular languages is closed under complement.

Assume that the set is regular. Let p be the pumping length of the
24 language. Then, according to the pumping lemma, break the string
s=0p into s=xyz where y has positive length.

Then, s=xyi z=0p+(i-1)|y| must also be in the set for any i. In particular
let i=p+1.Then xyp+1z=0p+p|y| must be in the set so p+p|y| = p(1+|y|)
must be prime. Thus we have a contradiction and the set cannot be
regular.

25 State pumping lemma for regular set. NOV/DEC 2010, C211.2 BTL 1
NOV/DEC 2013,NOV/DEC 2014

Let L be a regular set. Then there is a constant n such that if Z is a

string in L and |Z| >=n, Z can be written as Z=UVW such that |V|
 >=1 and |UV|<=n and for all i>=0 UViW is in L.

Prove that (0 * 1*) * = (0 + 1)*. C211.2 BTL 4

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

26
RHS: (0+1)* = { ε, 0,1,00,11,0011,011,0011110…}

Hence LHS = RHS is proved

Let R be any set of regular languages. Is U(R) regular? Prove C211.2 BTL 4
it.

27 Yes, UR is regular. Let P, Q be any two regular languages. As per

theorem L(R) = L (P UQ) = L (P+Q)

Since ‘+’ is a operator for regular expressions L(R) is also regular.

Write the regular expression for the language in which every C211.2 BTL 3
string will have at least one ‘a’ followed by at least one ‘b’.

The regular expression for the language in which every string will
28 have at least one ‘a’ followed by atleast one ‘b’ is given as: R=a+ b+
.

PART B
1 C211.2
Obtain the regular expression that denotes the language accepted
by BTL 3

2 C211.2
Using pumping lemma for regular sets. Prove that the language
L = {anbn /n>=1} is not regular BTL 3

3 Convert the given Regular Expression in to DFA and Minimize C211.2

it. (a/b)*abb
BTL 3
4 Construct an NFA for the following regular expression: (8) C211.2 BTL 3
APR/MAY 2010 (a+b)*a+b

5 Construct Finite Automata equivalent to the regular expression C211.2 BTL 3

NOV/DEC 2015
(ab+a)*
6 State the pumping lemma for Regular languages. Show that the C211.2 BTL 4
set L={0i2|i>=1} not regular. NOV/DEC 2015

7 What is Regular Expression? Write a regular expression for set C211.2 BTL 3
of strings that consists of alternating 0’s and 1’s. (8)
MAY/JUNE 2016

8 C211.2 BTL 1

9 Discuss the basic approach to convert from NFA to regular C211.2 BTL 1
expression. Illustrate with an example. (16)
NOV/DEC 2016

10 Show that the given two regular Languages are equivalent C211.2 BTL 4

(a+b)*

(a*+b*)*

11 (i) Discuss on regular expressions C211.2 BTL 1

(ii) Discuss in detail about the closure properties of regular
languages. MAY/JUNE 2013, NOV/DEC 2013

12 Prove that there exists an NFA with ε-transitions that accepts C211.2 BTL 1
the regular expression γ. (10)
MAY/JUNE 2012, NOV/DEC 2010

13 Which of the following languages is regular? Justify.(Using C211.2 BTL 3

Pumping Lemma)

(i) L={anbm | n,m>=1}

(ii) L={anbn | n>=1}

(8) MAY/JUNE 2012

(iii) L={ambn | m>n}

(10) NOV/DEC 2012
 (iv) L={anbn | n>=1}
(6) NOV/DEC 2010

(v) L={0n2| n is an integer, n>=1}

(6) NOV/DEC 2014

C211.2 BTL 3
14
Obtain the regular expression for the finite automata.
(8) MAY/JUNE 2012

a a

q0 b q1 b q2
15 Construct a minimized DFA from the regular expression C211.2 BTL 3
(i) (b/a)*baa
(10) MAY/JUNE 2012
(ii) 0*(01)(0/111)*
(16) NOV/DEC 2012
(iii) (x+y)x(x+y)*. Trace for a string w=xxyx.
(16) NOV/DEC 2011
(iv) (a+b)(a+b)* and trace for a string baaaab.
(16) APR/MAY 2010
(v) (b/a)*baa
(16) NOV/DEC 2010
(vi) 10+(0+11)0*1
(16) NOV/DEC 2014

16 Construct a regular expression for the following DFA using C211.2 BTL 3
kleene’s theorem. (10) APR/MAY 2011

0 1
*A A B
B C B
C A B

17 Construct a ε-NFA for the following regular expression. (6) C211.2 BTL 3
APR/MAY 2011

(0+1)*(00+11)(0+1)*
18 C211.2 BTL 3

19 State and explain the conversion of DFA into regular C211.2 BTL 1
expression using Arden’s theorem. Illustrate with an example.
(16) NOV/DEC 2011

20 Convert the following NFA into a regular expression C211.2 BTL 3

NOV/DEC 2013
0,1
1 0,1 0,1
C D
A B

21

22

UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES

CFG – Parse Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown Automata –
Languages of a Pushdown Automata – Equivalence of Pushdown Automata and CFG, Deterministic
Pushdown Automata.

S. Question Course Blooms

No. Outcome Taxanomy
Level
1 Define CFG. NOV/DEC 2013

A context-free grammar (CFG) is a formal grammar in which C211.3 BTL 1

every production rule is of the form V → w where V is a single
nonterminal symbol, and w is a string of terminals and/or
nonterminals (w can be empty). A formal grammar is
considered "context free" when its production rules can be
applied regardless of the context of a nonterminal. No matter
which symbols surround it, the single nonterminal on the left
 hand side can always be replaced by the right hand side

Construct context free grammar {0 m 1 n |1<=m<=n}

S->0AS1B|ε C211.3 BTL 3

2
A->ε

B->1B|ε

Define Ambiguous Grammar? Give an Example. C211.3

NOV/DEC 2012, MAY/JUNE 2013
BTL 1
3 A Grammar Generates more than one parse tree for one of its
string then the Grammar is said to be ambiguous grammar.
Example: E->E+E|E*E|id

Let G be the grammar with C211.3

SaB|bA
Aa|aS|bAA BTL 3
Bb|bS|aBB For the string aaabbabbba find the left
most derivation.

S=> aB
4 aaBB
aaaBBB
aaabBB
aaabbSB
aaabbaBB
aaabbabB
aaabbabbS
aaabbabbbA
aaabbabbba
Let G = {{s,c},{a,b},P,S} where P consists of S->aCa, C211.3
C->aCa|b Find L(G).
5 BTL 3
S->aCa->aaCaa->aaaCaaa->…..->aicai->anban(C->b)
L(G) = {anban |n>=1}

Define a derivation tree for a CFG. C211.3

A derivation tree for a CFG G = (V,T,P,S)is a tree satisfying the
following: a)Every vertex has a label which is a symbol of BTL 1
6 VUTUε .b)The label of the root is S. c)the internal vertices must be
in V. (d) If n has a label ‟ a‟ and vertices n 1,n2,n3,n4,…..nk are sons of
the vertex n ,in order from the left with label X 1,X2,X3,X4,…..Xk
respectively. Then A-> X1,X2,X3,X4,…..Xk must be a production in P.
(e) If vertex n has label ε then n is a leaf and is only son of its father.
7 Let G = (N,T,P,S), P ={S->A1B|a, A->0A| ε , B->0B|1B| ε } C211.3
give a leftmost and rightmost derivation for the string
BTL 3
00101

LMD:
S=>A1B=>0A1B=>00A1B=>001B=>0010B=>00101B=>0010
 1

RMD:
S=>A1B=>A10B=>A101B=>A101=>0A101=>00A101=>001
01

Show that id+id*id can be a ambiguous one for the grammar C211.3
E->E+E/ E*E/ (E)/id
BTL 3
LMD 1
8 EE+E id+Eid +E*E id +id*Eid +id*id
LMD 2
EE*EE+E*Eid+E*Eid+id*Eid+id*id. Therefore id+id*id
can be generated by two distinct LMD .Thus it is ambiguous.

Is the grammar below ambiguous S SS | (S) | S(S)S | E? C211.3

NOV/DEC 2011
BTL 3
9 It is ambiguous
The sentence such as E(E)E can have more than one LMD (or)
RMD (or) Parse tree.

Construct a CFG for set of strings that contain equal C211.3

number of a’s and b’s over ∑ = {a,b}. MAY / JUNE
10 BTL 3
2016
S->aSb | bSa | ε

What is unambiguity? C211.3

11
A Grammar Could not be able to generate more than one parse tree for
any of its string then the grammar is said to be unambiguous one. BTL 1
Mention the application of CFG. MAY/JUNE 2012 C211.3
12
Writing Syntax rule to the programming Language. BTL 4
Generating Recursive Structure can be easy.
Define the instantaneous descriptions(ID) of pushdown C211.3
Automaton NOV/DEC 2018
Let P= (Q,∑, Г, δ,q0, Z0 , F) be a PDA then the instantaneous BTL 1
description is given by
13
δ (q0, x, Z0)= δ (q1, xβ)
where q0 is current state, x is current input symbol, Z0 is
the current stack symbol, q1 indicates next state and xβ
represents top of the stack

14 What are the diiferent types of language accepted by a PDA C211.3

and define them? NOV/DEC 2012
BTL 1
There are two ways of language acceptances,
1) Acceptance by final state .L(M)= {w | (q0,w,Z0) Г (q,*

ε ,γ) for some q in F and γ in Г*}

2) Acceptance by empty stack. N(M)= {w | (q0,w,Z0)
 Г (q, ε, ε) for some q in Q}
*

What is DPDA? Give Example NOV/DEC 2018

A PDA P= ( Q,∑, Г, δ,q0, Z0 , F) is a deterministic if
C211.3 BTL 1
and only if the following two conditions are met:

1. δ (q, a, X) has at most one member for any q in Q, a

15 in ∑ or a = ε, and X in Г.

2. δ (q, a, X) is non empty, for some a in ∑, then δ (q, ε , X)

must be empty.

Define rules for the conversion of Grammars to PDA

Let G= (V, T, Q, S) be a CFG. Then PDA P that accepts L(G) by
empty statck as follows C211.3 BTL 1
P=({q}, T, VUT, δ, q, S) where the transition function δ is defined
16
by
1. For each variable A, δ(q, ε , A)= {(q, β) | A --> β is a production
of P}.
2. For each terminal a, δ(q, a, a)= {(q, ε)}.

Is it true that Non deterministic PDA is more powerful than

that of Deterministic PDA. Justify.
Yes. It is true that non deterministic PDA is more powerful C211.3 BTL 1
17
than that of deterministic PDA. This is because the class of
languages accepted by NPDA is larger than that of class of
languages accepted by DPDA.

Is the language of Deterministic PDA and Non –

deterministic PDA same? APR/MAY 2011
18 C211.3 BTL 1
The language is not same. This language of NPDA is a superset
of the language of DPDA.

Compare NFA and PDA NOV/DEC 2013

1. Stack which is used to store the necessary tape symbols and C211.3 BTL 1
19 use the state to remember the conditions.
2. Two ways of language acceptances, one reaching its final
state and another by emptying its stack.

20 What are the main applications of pumping lemma in CFL’s?

MAY/JUNE 2012, NOV/DEC 2012
The main applications of pumping lemma in CFL is to prove a C211.3 BTL 1
particular language is not a CFL .
Let L be any CFL. Then there exist a constant n ,depending on L,
Such that if z is in L and │z│≥ n, then z = uvwxy such that
i) │vx│≥1,
ii) │vwx│≤ n
 iii) For all I ≥ 0 u v w x y is in L.
i i

Define the rule for construction of CFG from given PDA

If q0 is the start state and qn is the final state of PDA then [q0Zqn]
becomes the start state of CFG. Z represents stack symbol. C211.3 BTL 1
21 For δ(qi, a, Z0) = (qi+1, Z1Z2)
δ(qi, Z0 qi+k) ---> a (qi+1 Z1 qm) (qm Z2 qi+k)
For δ(qi, a, Z0) = (qi+1, ε) can be converted as (qi Z0 qi+1) --> a

State the definition of Pushdown automata.

APR/MAY 2010, MAY/JUNE 2016
C211.3 BTL 1
A pushdown automaton consists of 7 tuples

P = (Q, ∑, Г, δ, q0, Z0, F)

Where Q – A finite non empty set of states

∑ - A finite set of input symbols

Г – A finite non empty set of stack symbols

δ - The transition function is given by

22 δ:Q X (∑ U {ε}) X Г  Q X Г*

q0 – q0 in Q is the start state

Z0 - Initial start symbol of the stack

F - F in Q, set of accepting states or final states.

Convert the following CFG to a PDA. NOV/DEC 2015

SaAA, AaS|bS|a
23 C211.3 BTL3
δ(q,ε,S)={(q,aAA)}
δ(q,ε,A)={(q,aS),(q,bS),(q,a)}

Does a Push down Automata have memory? Justify.

24 MAY/JUNE 2016
C211.3 BTL 1
Yes. It has the memory in the form of stack model.

Is the grammar EE+E|id is ambigupus ? Justify.

NOV/DEC 2010
C211.3 BTL 3
 It is ambiguous
25
 The sentence such as id+id+id can have more than one
LMD (or) RMD (or) Parse tree.

26 If S->aSb | aAb, A->bAa, A->ba then determine CFL.

S->aAb=>abab S->aSb=>a aAb b =>a a ba b b(sub S->aAb) S->aSb C211.3 BTL 3

=>a aSb b =>a a aAb b b=>a a a ba b bb Thus L={an b m a m b n ,
 where n,m>=1}

What is the language generated by the grammar G = (V, T, P, S)

where P={S->aSb, S->ab}?
27 C211.3 BTL 3
S=> aSb => aaSbb =>… =>an b n Thus the language L(G)={ an b n |
n>=1}.The language has strings with equal number of a’s and b’s.

Differentiate sentences from sentential forms.

28 A sentence is a string of terminal symbols. A sentential form is a C211.3 BTL 4

string containing a mix of variables and terminal symbols or all
variables. This is an intermediate form in doing a derivation.

What are the properties of the CFL generated by CFG?

29 The properties are: 1. Each variable and each terminal of G appears C211.3 BTL 1
in the derivation of some word in L 2. Here are no productions of the
form A->B where A and B are variables

What are the components of PDA ?

The PDA usually consists of four components: A control unit. C211.3 BTL 1
30
A Read Unit. An input tape.
A Memory unit.

Consider the context free Grammar given below give the

LMD for the string bbaa NOV/DEC 2018
31
S->bSa|aT|£, T->aT|bU|£, U->aT|£

S=>bSa=>bbSa=>bbaTa=>bbaa

Show that the following grammar is ambiguous S->SbS|a

NOV/DEC 2018

The grammar generates two parese tree for the string ababa

S S
32
S b S S b S

a S b S S b S

a a a a

33 Convert the given CFG to PDA NOV/DEC 2018

SaS|bS|a|b
 δ (q,ɛ,S)={(q,aS),(q,bS),(q,a),(q,b)}

δ (q,a,a)=(q, ɛ)

δ (q,b,b)=(q, ɛ)

PART – B
1 Consider the following grammar for list structures:

Sa|^|(T) TT,S|S C211.3 BTL 3

Find left most derivation, rightmost derivation and parse

tree for (((a,a),^(a)),a)(10) NOV/DEC 2012

2 Is the following grammar is ambiguous? Justify your

answer.
C211.3 BTL 3
1. E E+E |E*E | id (6) MAY/JUNE 2012

2. E E+E|E*E|(E)|a (4) APRIL/MAY 2011

3 Find the context free languages for the following

grammars.
C211.3 BTL 3
1. SaSbS|bSaS| ε (10)
MAY/JUNE 2012

2. SaSb|ab

3. SaSb|aAb, AbAa, Aba (6) NOV/DEC

2011

4 Show that the following Grammars are Ambiguous.

NOV/DEC 2013
C211.3 BTL 3
SaSbS|bSaS| ε

SaSb|ab

5 Given the grammar G=(V,∑,R,E) where

V={E,D,1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)} C211.3 BTL 3

∑ ={1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)} and R contains the

following rules

ED|(E)|E+E|E-E|E*E|E/E

D0|1|2|….9
 Find a parse tree for the string 1+2*3 NOV/DEC 2015
6 Let G=(V,T,P,S) be a Context free grammar then prove
that if the recursive inference procedure tells us that
C211.3 BTL 4
terminal string W is in the language of variable A, then
there is a parse tree with root A and yield w.
NOV/DEC 2015

7 What is an ambiguous grammar? Explain with an

example. NOV/DEC 2015
C211.3 BTL 1
8 Let G be the grammar

SaB|bA C211.3 BTL 3

Aa|aS|bAA

Bb|bS|aBB

for the string baaabbabba. Find leftmost derivation,

rightmost derivation and parse tree.
(9)

NOV/DEC 2010,MAY/JUNE 2013

9 Consider the grammar

(i) SiCtS C211.3 BTL 3

(ii) SiCtSeS
(iii) Sa
(iv) Cb
where i, t, and e stand for if, then, and else, and C
and S for “conditional” and “statement”
respectively.

(i) Construct a leftmost derivation for the

sentence w=ibtibtaea.
(ii) Show the corresponding parse tree for the
above sentence.
(iii) Is the above grammar ambiguous?
If so, prove it.
Remove ambiguity if any and prove that both the
grammar produces the same language.

Construct the PDA accepting the language

1. L={(ab)n|n>=1} by empty stack.(6) NOV/DEC C211.3 BTL 3

2012

2. L={a2nbn|n>=1} Trace your PDA for the input with

10
 n=3. (10) NOV/DEC 2012

3. L={wwR|w is in (a+b)*} (10)MAY/JUNE 2012

4. L={0n12n} by empty stack(8)APR/MAY 2011

5. L={wwRw|w is in {0+1}*}(10)NOV/DEC 2010

11 Find the PDA equivalent to the given CFG with the

following productions
C211.3 BTL 3
1. SA, ABC, Bba, Cac (6) NOV/DEC 2012

2. SaSb|A, AbSa|S| ε (10) NOV/DEC 2011

Give the CFG generating the language accepted by the

following PDA M==({q0,q1,},{0,1},{z0,x},δ,q0, z0, ε),with
C211.3 BTL 3
12 transactions δ( q0, 1,z0 ) = {( q0, xz0 )} , δ( q0, 1,x ) =
{( q0, xx )}, δ( q0, 0, x ) = {( q1, x)}, δ( q0, ε, z0 ) = {( q0,
ε)},δ( q1, 1, x ) = {( q1, ε)},δ( q1, 0 ,z0 ) = {( q0, z0)}
NOV/DEC 2018
13 Prove that if there exists a PDA that accepts by final
state then there exists an equivalent PDA that accepts by
C211.3 BTL 4
Null state. (8) APRIL/MAY 2011

14 Is NPDA (Nondeterministic PDA) and DPDA

(Deterministic PDA) equivalent? Illustrate with an
C211.3 BTL 4
example. (8) NOV/DEC 2011

15 What are the different types of language acceptances by

a PDA and define them. Is it true that the language
C211.3 BTL 1
accepted by a PDA by these different types provides
different languages? (8) NOV/DEC
2011

UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES

Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines –
Programming Techniques for TM.
S. Question Course Blooms
No. Outcome Taxanomy
Level
Define CNF form. NOV/DEC 2014
1
Every Production is in the form N.T->N.T N.T or N.T->T C211.4 BTL 1
where N.T stands for Non Terminal and T stands for Terminal
 Eliminate the ε production from the CFG given below
A-> 0 B 1 | 1 B 1
B-> 0 B | 1 B | ε C211.4 BTL 3
2
A->0B1|1B1|01|11

B->0B|1B|0|1

Define GNF Form. MAY/JUNE 2013

Every Production is in the form of N.T->N.T α or N.T->T
3 C211.4 BTL 1
where
α stands for any number of Terminal Symbols

Consider the following grammar G with productions

S ABC | BaB
C211.4 BTL 3
AaA|BaC|aaa

BbBb|a

CCA|AC

Give a CFG with no useless variables that generates the

4
same language. APR/MAY 2010

Symbol C is non-generative, after removing productions with C

we have the below grammar,

S BaB

A aA|aaa

BbBb|a

Convert the following grammar into an equivalent one with

no unit productions and no useless symbols SABA
C211.4 BTL 3
AaAA|aBC|bB B A|bB|Cb CCC|Cc NOV/DEC
5
2011
The given grammar does not generate any symbol so all the
symbols are useless symbol.

What are the three ways to simplify a context free

grammar?
C211.4 BTL 1
By removing the useless symbols from the set of productions.
6
By eliminating the empty productions.
By eliminating the unit productions.

7 Construct CFG without ε production from : S →a | Ab |

aBa , A →b | ε , B→b | A.
C211.4 BTL 3
 S->a|Ab|b|aBa|aa
A->b
B->b

What do you mean by null production and unit production?

Give an example. MAY / JUNE 2016
C211.4 BTL 1
8 In a grammar any of the Production body has ε then that
particular production is called Null Production. In a grammar
any of the production body has Single Non Terminal then that
particular production is called Unit Production

Convert the following grammar G in greibach normal

form. SABb|a AaaA|B BbAb APR/MAY 2010

 No ε production in the given grammar

9 Eliminating unit production AB we have

SABb|a AaaA|bAb BbAb C211.4 BTL 3

 Eliminating useless variables A & B (non generating)

Sa

State the two normal forms and give an example.

NOV/DEC 2011
10 1. Chomsky normal form ABC |a C211.4 BTL 1
2. Greibach normal form XbYXZ|a

Define Instantaneous description of turing machine

ID of turing machine is represented as
X1 X2......Xi-1 q Xi Xi+1.....Xn
11 i) where q is the state of turing machine.
ii) The tape head is scanning the ith symbol from left C211.4 BTL 1
iii) X1 X2....Xn is the portion of the tape between the leftmost
and the rightmost non blank

What are the applications of Turing Machine?

NOV/DEC 2012
12 It is a theoretical model for real world computer.
C211.4 BTL 4
It is used to recognize regular Language

13 State Chomsky hierarchy of the language. NOV/DEC 2016,

NOV/DEC 2018
C211.4 BTL 1
Language Class Grammar Model

TYPE 3 Regular NFA/DFA

TYPE 2 Context Free PDA

 TYPE 1 Context Sensitive Linear Bounded
Automaton

TYPE 0 Unrestricted Turing Machine

Define the language of Turing machine

Let M= (Q,∑, Г ,δ,q0, B , F) be a turing machine. Then L(M) is the
14
set of strings w in ∑* such that q0 w ├ * α p β for some state p in F
and any tape strings α and β. C211.4 BTL 1

What is a multitape turing machine?NOV/DEC 2015

A Multitape Turing machine has a finite control with some

15 finite number of tapes. Each tape is divided into cells and each
cell can hold any symbol of the finite tape alphabet. The set of C211.4 BTL 1
tape symbol includes a blank, and has a subset called the input
symbols, of which the blank is not a member.

Construct a Turing machine to compute ‘n mod 2’ where n

is represented in the tape in unary form consisting of only
0’s. APR/MAY 2011
0 B
q0 (q1,B,R) (q2,B,R)
16
q1 (q0,B,R) (q3,B,R)
q2 - - representing even C211.4 BTL 3
no
q3 - - representing odd
no

Design a TM that accepts the language of odd integers

written in binary. NOV/DEC 2011
17 To accept odd valued binary strings, we only have to look at
the last bit. The TM moves right until it reads a blank, moves C211.4 BTL 3
left one space and acepts if and only if there is a 1 on the tape.

What is a multiple track Turing machine?

18 A TM in which the input tape is divided into multiple tracks
where each track is having different inputs is called multiple C211.4 BTL 1
track TM.
Define Halting Problem
The halting problem is the problem of determining, from a
19
description of an arbitrary computer program and an input,
whether the program will finish running or continue to run C211.4 BTL 1
forever
20 Design a Turing machine with no more than three states
that accepts the language a(a+b)*. Assume ∑ = {a,b}
C211.4 BTL 3
APR/MAY 2010
TM M=(Q, ∑, Г, δ, q0, B,{q2})

Q – {q0,q1,q2}
 ∑ - {a,b}

Г – (a,b,B}

q0 – Initial state

q2 - Final state

δ - Transition function given as follows

δ(q0,a) = (q1,a,R)

δ(q1,a) = (q1,a,R)

δ(q1,b) = (q1,b,R)

δ(q1,B) = (q2,B,R)

What is Turing machine? NOV/DEC 2010

TM is denoted by

M=(Q, ∑, Г, δ, q0, B,F) where

Q – A finite non empty set of states

∑ - A finite set of input symbols

21 Г – A finite non empty set of tape symbols

δ - The transition function is given by C211.4 BTL 1

δ:Q X Г  Q X Г X {L,R,S}

q0 – Initial state

B ε Г – Blank Symbols

F - Final state

What are the required fields of an instantaneous

description of a Turing machine? NOV/DEC 2016
22
It requires i)the state of the TM. ii)the contents of the tape. iii)the
position of the tape head on the tape. C211.4 BTL 1

List the primary objectives of Turing Machine.

NOV/DEC 2016
23 It acts as a Computing Function.
It will accept Recursive Language C211.4 BTL 1
It has infinite amount of memory to store the input

24 List out different types of TMs.

 Multi tape Turing machine, off-line Turing Machine , Multi track
BTL 1
Turing machine & Universal TM . C211.4
Is Halting problem decidable or undecidable problem
The machine starting at given configuration will halt after
finite number of steps or will never reach to a halt state. For a
25
given configuration and input tape we can't determine whether the
machine will ever halt. This problem is called halting problem. C211.4 BTL 1
The halting problem is unsolvable. Hence it is undecidable
problem.
List out the different techniques for turing machine
construction.NOV/DEC 2013
26
(i)Storage in the Finite Control
(ii)Multiple tracks C211.4 BTL 1
(iii)Checking off symbols
(iv)Subroutines
Compare FM, PDA and TM MAY/JUNE 2016
Finite Machine is of two types - DFA and NFA. Both DFA and
NFA accept regular language only
27
PDA has a memory and hence it accepts large class of language.
TM can be programmed. Hence TM accepts very large class of C211.4 BTL 1
language. TM is therfore most powerful computational mode

Is it possible that a turing machine could be considered as a

computer of functions from integers to integers? If yes justify
Yes, TMs simulate computer of functions from integers to
28 integers. That means it is a device for computing integer valued
functions. In this scheme integers were presented in unary as
C211.4 BTL 1
blocks of a single character and machine computed by changing
the lengths of blocks or by constructing new blocks on the input
tape
What does Multitape turing machine contain?
1. The input, a finite sequence of input symbols, is placed on
the first tape.
29
2. All other cells of all the tapes hold the blank.
3. The final control is in initial state. C211.4 BTL 1
4. The head of the first tape is at the left end of input.
5. All other tape heads are at some arbitrary cell.
Define Subroutines in Turing machine
A Turing machine subroutine is a set of states that performs
some useful process. This set of states includes a start state and
30
another state that temporarily has no moves, and that serves at
the return state to pass control to whatever other set of states C211.4 BTL 1
called the subroutine

31 Differenciate Multihead and Multitape Turing Machine.

Muti Head TM Multi Tape TM
Single Tape with multi heads Mutiples tuples with each C211.4 BTL4
tape having its own
independent head
Input strings stored in a Input strings stored in a
single tape with multiple Multiple tapes with multiple
 read/write controlls read/write controlls
A multihead TM can be A multitape TM can be
simulated into a single head simulated into a single Tape
TM TM
PART – B
1 Define Pumping Lemma for Context Free Languages.
Show that L={ai bj ck : i<j<k}is not context free grammar
C211.4 BTL 1,BTL
(6) APR/MAY 2010 3

2 Show that langyage {0n1n2n | n>=1} is not context free

language.(4) NOV/DEC 2014, NOV/DEC 2018
C211.4 BTL 3
3 Convert the following grammar into GNF

S -> XY1/0 C211.4 BTL 3

X -> 00X/Y

Y -> 1X1 NOV/DEC 2013

4 What is the purpose of normalization? Construct the

CNF and GNF for the following grammar and explain
C211.4 BTL 3
the steps. (10) MAY/JUNE 2016

SaAa | bBb |€

AC|a

BC|b

CCDE | €

DA|B|ab

ii) Constuct a CFG for the regular expression

(011+1)(01). (6) MAY/JUNE 2016

5 Construct a equivalent grammar G in CNF for the

grammar G1 where
C211.4 BTL 3
G1=({S,A,B},{a,b},{SASB|ε,AaAS|a, BSbS|A|
bb},S) NOV/DEC 2015

6 Convert the following grammar into CNF

(i) ScBA, SA, AcB, AAbbS, C211.4 BTL 3

Baaa (6) NOV/DEC 2012

(ii) Sa|AAB, Aab|aB| ε, Baba| ε

(8) APR/MAY 2011
 (iii) SA|CB, AC|D, B1B|1,
C0C|0, D2D|2 (16)
APR/MAY 2010

(iv) SaAD AaB|bAB B b D

d (6) NOV/DEC 2014

(v) SABC|BaB NOV/DEC 2018

AaA|Bac|aaa

BbBb|a|D

C->CA|AC

Dɛ

7 State and prove the pumping lemma for CFL. What is

its main application? Give two examples. NOV/DEC
C211.3 BTL 1
2012, NOV/DEC 2011, MAY/JUNE 2013

8 Explain the different models of Turing machines.

(10) NOV/DEC 2011
C211.4 BTL 1
(i) Write about Multi tape Turing Machines. (10)
9 NOV/DEC 2016
(ii) Explain and highlight the implications of halting
C211.4 BTL 1
problems (6) NOV/DEC 2016

10 Design a Turing machine for the following

Reverses the given string {abb}. (8) NOV/DEC 2012 C211.4 BTL 3

L={1n0n1n|n>=1} (10) MAY/JUNE 2012

L={anbncn} (8) APR/MAY 2011,NOV/DEC

2018

To perform proper subtraction (8) APR/MAY 2011

To move an input string over the alphabet A ={a} to the

right one cell. Assume that the tape head starts
somewhere on a blank cell to the left of the input string.
All other cells are blank, labeled by ^. The machine must
move the entire string to the right one cell, leaving all
remaining cells blank. (10) APR/MAY 2010
n n
L={1 0 |n>=1} (8) NOV/DEC 2010
 L={wwR| w is in (0+1)*} (8) NOV/DEC 2010

mplement the function “MULTIPLICATION” using the

subroutine “COPY”. (12)
NOV/DEC 2014

L={0n1n|n>=1} (10) NOV/DEC 2015

Write briefly about the programming techniques for

TM. (8) NOV/DEC 2012,MAY/JUNE 2013, NOV/DEC
11
2015 C211.4 BTL 1

12 Convert the Grammar into GNF NOV/DEC 2018

SAB ABS|b BSA|a

UNIT V UNDECIDABILITY
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems
about TM – Post‘s Correspondence Problem, The Class P and NP.

PART - A

S. Question Course Blooms

No Outcom Taxanom
. e y Level
When we say a problem is decidable? Give an example of
undecidable problem. NOV/DEC 2012,NOV/DEC 2015
C211.5 BTL 1
problem whose language is recursive is said to be decidable.
1 Otherwise the problem is undecidable . i.e there is no algorithm that
takes as input an instance of the problem and determines whether the
answer to that instance is yes or no.
Eg. Halting problem

2 What is recursively enumerable language? NOV/DEC 2012,

MAY/JUNE 2012, NOV/DEC 2010, MAY/JUNE 2013,
C211.5 BTL 1
NOV/DEC 2013

A language is recursively enumerable if there exists a Turing machine

that accepts every string belonging to that language. And if the string
does not belong to that language then it can cause the turing machine to
enter ia an infinite loop
 Mention the difference between P and NP problems.
MAY/JUNE 2012
C211.5 BTL 1
P consists of all those languages or problems accepted by some TM
3 that runs in some polynomial amount of time, as a function of its
input length.
NP is the class of languages or problems that are accepted by some
nondeterministic TM‟s with a polynomial bound on time taken
along any sequence of nondeterministic choices.

How to prove that the Post Correspondence problem is

Undecidable. NOV/DEC 2011
4 Introduce a modified PCP and reduce the same to the original PCP. C211.5 BTL 1
Again reduce Lu to the modified PCP.
The chain of reduction infers if original L u is known to be
undecidable then conclude that PCP is undecidable.
Show that any PSPACE-hard language is also NP-hard.
NOV/DEC 2011
First we must show that the language is not in NP. This is trivial C211.5 BTL 1
5 since NP is a subset of PSPACE and therefore, anything outside of
PSPACE is also outside of NP.
Then we must show that any problem in NP can be reduced to any
PSPACE-hard language. Thus, any PSPACE-hard problem is also
NP-hard.
State Rice’s theorem. APR/MAY 2010
6 Every non-trivial property of the RE language is undecidable.
A property is trivial if it is either empty such that it is satisfied by no C211.5 BTL 1
language or is all RE languages, or else it is non-trivial.
Show that the collection of all Turing machines is
countable.APR/MAY 2010
 If for a set there is an enumerator, then the set is countable. C211.5 BTL 1
 Any Turing Machine can be encoded with a binary string of 0’s
and 1’s.
7  An enumeration procedure for the set of Turing Machine strings:
Repeat
 Generate the next binary string of 0’s and 1’s in proper
order
 Check if the string describes a Turing Machine
If Yes: Print string on output tape
If No: Ignore string
Mention the difference between decidable and undecidable
8 problems. NOV/DEC 2010
C211.5 BTL 1
 Decidable Problem – Existence of an algorithm
 Undecidable Problem – No algorithm for solving it.
9 What is universal turing machineNOV/DEC 2013, NOV/DEC
 2013
Universal Turing machine (UTM) is a Turing machine that can C211.5 BTL 1
simulate an arbitrary Turing machine on arbitrary input. The
universal machine essentially achieves this by reading both the
description of the machine to be simulated as well as the input
thereof from its own tape
Features of Universal TM
Universal TM can simulate any other turing machine. Universal TM
10 C211.5 BTL 1
is a single machine used to compute any computable sequence.
Universal TM has an ability to manipulate an unbounded amount of
data in finite amount of time
Give example for NP-complete problems. NOV/DEC
11 2014
Traveling Salesman Problem C211.5 BTL 1
Graph Coloring Problem
When a language is said to be recursive?
A language is said to be recursive if there exists a turing
machine that accepts every string of the language and every string is
rejected if it is not belonging to that language.
12

Define modified posts correspondence problem.

Given lists A and B of k strings each from ∑* , say A = w1 ,w2, w3,
13 …wk, B = x1 ,x2, x3,…xk does there exist a sequence of integers C211.5 BTL 1
i1,i2,…ir such that w1, wi1,wi2,wi3,….wir=xi1,xi2,xi3,…xir .The
sequence i1,i2,…ir is a solution to this instance of MPCP.
State two languages, which are not recursively enumerable
14  Diagonalization language is not recursively enumerable.
 The partially decidable languages or undecidable languages C211.5 BTL 1
are not recursively enumerable.
Define posts correspondence problem.
An instance of posts correspondence problem consists of two lists A
= w1 ,w2, w3,…wk , B = x1 ,x2, x3,…xk of strings over some C211.5 BTL 1
15 alphabet ∑.This instance of PCP has a solution if there is any
sequence of integers i1,i2,…im with m ≥1 such that wi1,wi2,wi3,
….wim=xi1,xi2,xi3,…xim.The sequence i1,i2,…im is a solution to
this instance of PCP.
Prove that the complement of recursive languages is recursive. C211.5
APR/MAY 2011

16 Y N
w M

Y
N
17 Write the properties of Recursive Languages. C211.5
a formal language is recursive if there exists a total Turing
 machine (a Turing machine that halts for every given input) that,
when given a finite sequence of symbols as input, accepts it if it
belongs to the language and rejects it otherwise. Recursive
languages are also called decidable.
When do you say a problem is NP - hard? C211.5
18 A problem is said to be NP - hard if an algorithm for solving it can
be translated into a problem which is NP problem. Thus NP - hard is
a algorithm for a problem which is atle
When a problem is said to be undecidable? C211.5
19
If a problem is not a recursive language, then it is said to be
undecidable problem
What is diagonalization language? C211.5
20 The language Ld Which consists of all those strings w such that the
Turing machine represented by w does not accept the input w.
Ld = { wi | wi L(Mi)}
Define Problem Solvable in Polynomial Time C211.5
21 A Turing Machine M is said to be of time complexity T(n) if
whenever m given an input w of length n, m halts after making at
most T(n) moves, regardless of whether or not m accepts.
Show that union of recursive language is recursive C211.5
L1 and L2 are recusive language. Then there exists a machine M1
that accepts L1 as well as machine M2 that accepts L2. We can
22 simulate a machine M that accepts the language L such that L = L1
U L2. Then construct M which accepts if M1 accepts. If M1 does
not accept then M2 simulates M. That means if M2 accepts then M
accepts, if M2 rejects M also rejects. Thus M accepts the language L
= L1 U L2 which is recursive.
Define NP-Completeness. C211.5
23 A language is NP-complete if the following statements are true.(i)L
is in NP (ii)For every language L‟ in NP there is a polynomial time
reduction of L‟ to L.
What is the difference between PCP and MPCP? C211.5
24
The difference between MPCP and PCP is that in the MPCP ,a
solution is required to start with the first string on each list.
What are the concepts used in UTMs? C211.5
25
Stored program computers. Interpretive Implementation of
Programming languages. Computability
Define L .When is a trivial property? C211.5
26
L is defined as the set { | L(M) is in . } is a trivial property if is
empty or it consists of all r.e languages
When we say a problem is decidable? Give an example of C211.5
undecidable problem?
A problem whose language is recursive is said to be decidable.
27 Otherwise the problem is said to be undecidable. Decidable
problems have an algorithm that takes as input an instance of the
problem and determines whether the answer to that instance is “yes”
or “no”. (eg) of undecidable problems are (1)Halting problem of the
TM.
28 Define the class NP Problem. C211.5
A problem is said to be NP if 1. its solution comes from a finite set
of possibilities, and 2. it takes polynomial time to verify the
 correctness of a candidate solution. Example - Scheduling problems.
What are tractable problems and intractable problems? C211.5
Tractable Problem: a problem that is solvable by a polynomial-time
29
algorithm. The upper bound is polynomial. Intractable Problem: a
problem that cannot be solved by a polynomial-time algorithm. The
lower bound is exponential.
What are the properties of recursive and recursively enumerable
languages?.
(i)The complement of a recursive language is recursive,(ii)The union C211.5 BTL 1
30
of two recursive languages are recursive. (iii)The union of two
recursively enumerable languages are recursively enumerable.(iv)If
a language L and are both recursively enumerable then L is
recursive.

PART – B
Explain any four NP-Complete Problems.
1 (8)NOV/DEC 2010,NOV/DEC 2013
C211.5 BTL 3
Prove that “MPCP reduces to PCP”. NOV/DEC 2015
2
C211.5 BTL 1
State and prove the Post’s correspondence problem.
3 (10)NOV/DEC 2012, NOV/DEC 2014
C211.5 BTL 3
Write a note on NP problems.
4 (6) NOV/DEC 2012
C211.5 BTL 1
Explain undecidability with respect to post correspondence
5 problem. (8) MAY/JUNE2012
C211.5 BTL 1
6 Show that the union of two recursive language is recursive &
union of two recursively enumerable languages is recursive.
C211.5 BTL 1
(12) NOV/DEC 2014

7 (i) Explain about “A language that is not recursively

enumerable”
C211.5 BTL 1
(ii)Prove Lne is recursively enumerable. MAY/JUNE 2013

9 Prove that for two recursive languages L 1 and L2 their union and
intersection is recursive. NOV/DEC 2013,NOV/DEC
C211.5 BTL 1
2014,NOV/DEC 2018

10 State and explain RICE theorem. NOV/DEC 2015

C211.5 BTL 1
11 Prove that if a language is recursive if and only if it and its
complement are both recursively enumerable. NOV/DEC 2013 C211.5 BTL 1
12 Let ∑={a,b}*. Let A and B the lists of three strings as given
below: A={b,bab3,ba} B={b3,ba,a} C211.5
BTL 3
Does this instance of PCP have a solution? Justify your
answer. (8) NOV/DEC 2011

13 Write short notes on recursive and recursively enumerable

languages. (8) NOV/DEC 2011, NOV/DEC 2015 C211.5
BTL 4

14 What is Universal Turing Machine? Explain the procedure to

construct Universal Turing Machine. NOV/DEC 2018