JEPPIAAR ENGINEERING COLLEGE
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
CS6503
THEORY OF COMPUTATION
Question Bank
III YEAR A & B / BATCH : 2016 -20
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
M2
To participate in the production, development and dissemination of knowledge and
interact with national and international communities
M3
To equip students with values, ethics and life skills needed to enrich their lives and
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)
PO1
Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.
PO2
Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.
PO3
Design/development of solutions: Design solutions for complex engineering problems
and design system components or processes that meet the specified needs with
appropriate consideration for the public health and safety, and the cultural, societal, and
environmental considerations
PO4
Conduct investigations of complex problems: Use research-based knowledge and
research methods including design of experiments, analysis and interpretation of data,
and synthesis of the information to provide valid conclusions.
PO5
Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.
PO6
The engineer and society: Apply reasoning informed by the contextual knowledge to
assess societal, health, safety, legal and cultural issues and the consequent responsibilities
relevant to the professional engineering practice.
PO7
Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and
need for sustainable development.
PO8
Ethics: Apply ethical principles and commit to professional ethics and responsibilities
and norms of the engineering practice.
PO9
Individual and team work: Function effectively as an individual, and as a member or
leader in diverse teams, and in multidisciplinary settings.
PO10
Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and
write effective reports and design documentation, make effective presentations, and give
and receive clear instructions.
PO11
Project management and finance: Demonstrate knowledge and understanding of the
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.
PO12
Life-long learning: Recognize the need for, and have the preparation and ability to
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
M1
To create computer professionals with an ability to identify and formulate the
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
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
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
entrepreneurship skills.
BLOOM TAXANOMY LEVELS(BTL)
BTL6: Creating.,
BTL 5: Evaluating.,
BTL 4: Analyzing.,
BTL 3: Applying.,
BTL 2: Understanding.,
BTL 1: Remembering
SYLLABUS
THEORY OF COMPUTATION – CS6503 (V SEMESTER)
UNIT I FINITE AUTOMATA 9
Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic
Definitions –Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular
Languages- Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA’s with
and without €-moves –Equivalence of finite Automaton and regular expressions –Minimization
of DFA- - Pumping Lemma for Regular sets – Problems based on Pumping Lemma.
UNIT II GRAMMARS 9
Grammar Introduction– Types of Grammar - Context Free Grammars and Languages–
Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees –
Simplification of CFG – Elimination of Useless symbols - Unit productions - Null productions –
Greiback Normal form – Chomsky normal form – Problems related to CNF and GNF.
UNIT III PUSHDOWN AUTOMATA 9
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic
pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL –
problems based on pumping Lemma.
UNIT IV TURING MACHINES 9
Definitions of Turing machines – Models – Computable languages and functions –Techniques
for Turing machine construction – Multi head and Multi tape Turing Machines - The Halting
problem –Partial Solvability – Problems about Turing machine- Chomskian hierarchy of
languages.
UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS 9
Unsolvable Problems and Computable Functions – Primitive recursive functions – Recursive
and recursively enumerable languages – Universal Turing machine. MEASURING AND
CLASSIFYING COMPLEXITY: Tractable and Intractable problems- Tractable and possibly
intractable problems - P and NP completeness - Polynomial time reductions.
Total= 45 Periods
TEXT BOOKS:
1. Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata
Theory, Languages and Computations”, Second Edition, Pearson Education,
2008. (UNIT 1,2,3)
2. John C Martin, “Introduction to Languages and the Theory of Computation”,
Third Edition, Tata McGraw Hill Publishing Company, New Delhi, 2007.
(UNIT 4,5)
REFERENCES:
1. Mishra K L P and Chandrasekaran N, “Theory of Computer Science -
Automata, Languages and Computation”, Third Edition, Prentice Hall of
India, 2004.
2. Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of
Computation”, Second Edition, Prentice Hall of India, Pearson Education,
New Delhi, 2003.
3. Peter Linz, “An Introduction to Formal Language and Automata”, Third
Edition, Narosa Publishers, New Delhi, 2002.
4. Kamala Krithivasan and Rama. R, “Introduction to Formal Languages,
Automata Theory and Computation”, Pearson Education 2009
NOTE :REFER NOTES FOR PART B PROBLEMS
Course Outcomes (COs)
C504.1
Design Finite State Automata and Regular Expression for any language
C504.2
Illustrate the design of Context Free Grammar for any language set
C504.3
Demonstrate the push down automaton model for the given language
C504.4
Make use of Turing machine concept to solve the simple problems
C504.5
Explain decidability or undesirability of various problems
INDEX
Unit #
Ref. Book
Unit 1
Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata
Theory, Languages and Computations”, Second Edition, Pearson
Education, 2008. (UNIT 1,2,3)
Mishra K L P and Chandrasekaran N, “Theory of Computer Science -
Automata, Languages and Computation”, Third Edition, Prentice Hall of
India, 2004.
Unit 2
Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata
Theory, Languages and Computations”, Second Edition, Pearson
Education, 2008. (UNIT 1,2,3)
Mishra K L P and Chandrasekaran N, “Theory of Computer Science -
Automata, Languages and Computation”, Third Edition, Prentice Hall of
India, 2004.
Unit 3
Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata
Theory, Languages and Computations”, Second Edition, Pearson
Education, 2008. (UNIT 1,2,3)
Mishra K L P and Chandrasekaran N, “Theory of Computer Science -
Automata, Languages and Computation”, Third Edition, Prentice Hall of
India, 2004.
Unit 4
John C Martin, “Introduction to Languages and the Theory of
Computation”, Third Edition, Tata McGraw Hill Publishing Company,
New Delhi, 2007. (UNIT 4,5)
Unit 5
John C Martin, “Introduction to Languages and the Theory of
Computation”, Third Edition, Tata McGraw Hill Publishing Company,
New Delhi, 2007. (UNIT 4,5)
UNIT I FINITE AUTOMATA 9
Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic
Definitions –Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – Regular
Languages- Regular Expression – Equivalence of NFA and DFA – Equivalence of NDFA’s with
and without €-moves –Equivalence of finite Automaton and regular expressions –Minimization
of DFA- - Pumping Lemma for Regular sets – Problems based on Pumping Lemma.
S.
No.
Question
Course Outcome
Blooms
Taxanomy
Level
1
Define
(a) Finite Automata (FA)
(b) Transition Diagram
NOV/DEC 2012
Finite Automata is a 5 tuples denoted by
A = (Q, ∑, δ, q
0
, 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
C504.1
BTL 1
2
State the Principle of induction.
NOV/DEC 2012
Refer notes
C504.1
BTL 1
3
What is proof by contradiction?
MAY/JUNE 2012 Refer notes
C504.1
BTL 1
4
Define ε-closure(q) with an example.
MAY/JUNE 2012
Refer notes
C504.1
BTL 1
5
Differentiate between proof by contradiction and
proof by contrapositive. APR/MAY 2011
If H then C will be proved by assuming ~H and then
proving falsehood of falsehood of C. This is proof by
contadiction. Proof by contrapositive is proved by
assuming ~H and proving ~C.
C504.1
BTL 1
6
Construct a DFA for the language over {0, 1}*
such that it contains “000” as a substring.
APR/MAY 2011
1
0,1
0 0
0
1
C504.1
BTL 1
7
What is structural induction?
NOV/DEC 2011
Let S(X) be a statement about the structures X that
are defined by some particular recursive definition.
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 Y
1
,
Y
2
,....Y
k
. Assume the statements S(Y
1
),...,S(Y
k
)
and use these to prove S(X).
C504.1
BTL 1
8
State the difference between NFA and DFA.
NOV/DEC 2011
DFA must emit one and only one vertex/line/edge for
each element of the alphabet. NFA do not have to
C504.1
BTL 1
Q0
Q1
Q2
Q3
obey this and can have multiple edges labeled with
the same letter (repetition) and /or edges labeled with
the empty string.
Both DFA and NFA recognize the same languages –
the regular languages.
9
1. Construct deterministic finite automata to
recognize odd number of 1’s and even
number of 0’s?
APR/MAY 2010
1
1
0 0 0 0
1
1
C504.1
BTL 1
10
State the relations among regular expression,
deterministic 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 defined by the finite automata. If a
Regular language ‘L’ is accepted by a NFA then
there exists a DFA that accepts ‘L’.
C504.1
BTL 1
11
What is inductive proof?
NOV/DEC 2010
Statement P(n) follows from
(a) P(0) and
(b) P(n-1) implies P(n) for n>=1
Condition (a) is an inductive proof is the basis and
Condition (b) is called the inductive step.
C504.1
BTL 1
12
Find the set of strings accepted by the finite
automata. NOV/DEC 2010
C504.1
BTL 1
A
C
D
B
0, 1
(0+1)* or L={ε, 0, 1, 00, 01, 10, 11,............}
13
What is meant by DFA
MAY/JUNE 2013
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.
C504.1
BTL 1
14
Define the term Epsilon transition
MAY/JUNE 2013
In the automata theory, a nondeterministic finite
automaton with ε-moves (NFA-ε)(also known as NFA-λ)
is an extension of nondeterministic finite
automaton(NFA), which allows a transformation to a new
state without consuming any input symbols
C504.1
BTL 1
15
Draw the transition diagram for an identifier
NOV/DEC 2013
letter letter,digit
C504.1
BTL 1
16
What is non deterministic finite automata?
NOV/DEC 2013
In automata theory, a nondeterministic finite automaton
(NFA), or 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
C504.1
BTL 1
17
Define Deductive Proof.
NOV/DEC 2014
A Deductive proof consists of a sequence of
statements whose truth leads us from some initial
C504.1
BTL 1
statement, called the ‘hypothesis’ to a ‘conclusion’
statement.
“if H then C”
Ex: if x >= 4 then 2
x
>= x
2
18
1. Design DFA to accept strings over ∑ = (0,1) with
two consecutive 0’s.NOV/DEC 2014
1
0,1
0 0
1
C504.1
BTL 1
19
What is a finite automaton?
NOV/DEC 2015
A finite automaton (FA) is a simple idealized
machine used to recognize 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, ∑, δ, q
0
, 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
C504.1
BTL 1
q0
q1
q3
20
Write Regular Expression for the set of strings over
{0.1} that have atleast one. NOV/DEC 2015
Regualr Expression = (0+1)*1
C504.1
BTL 1
21
Draw a Non-deterministic finite automata to accept
strings containing the substring 0101. MAY/JUNE
2016 Refer Notes
C504.1
BTL 1
22
State the pumping lemma for regular languages.
MAY/JUNE 2016Refer Notes
C504.1
BTL 1
23
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 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.
C504.1
BTL 1
24
Define extended transition function for a DFA.
The extended transition function δ‟: Qε∑ * εQ is
defined as follows.
(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)
C504.1
BTL 1
25
Give a regular expression for the set of all strings
having odd number of 1’s
RE= 1(0+11)*
C504.1
BTL 1
26
Give the regular expression for the set of all strings
ending in 00.
Regular expression = (0+1)*00
C504.1
BTL 1
27
When two states are equivalent and distinguishable?
We say that two states p and q are equivalent iff for
each input string x , δ(p,x) is an accepting state iff
C504.1
BTL 1
δ(q,x) is an accepting state. p is distinguishable from
q if there exists an x such that δ(p,x) is in F and v is
not in F or vice versa.
28
What are the applications of regular expression?
Regular expression in UNIX, Lexical analysis,
Pattern searching
C504.1
BTL 1
29
Write regular expressions for the following.
(i)Binary numbers that are multiple of 2. (0/1)*.
(ii)Strings of a‟s and b‟s with no consecutive a‟s
.b* (abb*)(a / ε) (iii) Strings of a‟s and b‟s
containing consecutive a‟s. (a/b)*aa(a/b)*
C504.1
BTL 1
30
State Arden’s theorem.
Let P and Q be two regular expressions over ∑. If P
does not contain null string ε over ∑ then R=Q+RP,
it has the solution R=QP*
C504.1
BTL 1
PART B
1
Explain the different forms of proof with
examples. (8) NOV/DEC 2012
C504.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, NOV/DEC
2013
C504.1
BTL 1
3
Prove that if n is a positive integer such that n
mod 4 is 2 or 3 then n is not a perfect square.
(6) NOV/DEC 2012
C504.1
BTL 1
4
Construct a DFA that accepts the following
(i) L={ x € {a,b}:|x|
a
= odd and |x|
b
= even}.
(10) NOV/DEC 2012
(ii) Binary strings such that the third symbol
from the right end is 1. (10) MAY/JUNE
2012
C504.1
BTL 1
(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
=
+=
n
i
nni
0
2/)1(
(6) MAY/JUNE 2012
C504.1
BTL 1
6
Construct an NFA without ε-transitions for the
NFA give below. (8) MAY/JUNE 2012
0 1
ε
C504.1
BTL 1
7
Construct an NFA accepting binary strings with
two consecutive 0’s. (8) MAY/JUNE 2012
8`
Show that a connected graph G with n vertices
and n-1 edges (n>2) has at least one leaf.
(6) APR/MAY 2011
• G has n vertices & (n-1) edges.
• Therefore ∑ deg(V) = 2(n-1) which is
impossible
• Therefore deg(V) = 1 for at least one vertex
and this vertex is a leaf.
9
Prove that there exists a DFA for every ε-NFA.
(8) APR/MAY 2011 Refer Notes
10
Distinguish NFA and DFA with examples.
MAY/JUNE 2013
Q0
Q1
UNIT II GRAMMARS 9
Grammar Introduction– Types of Grammar - Context Free Grammars and Languages–
Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees –
Simplification of CFG – Elimination of Useless symbols - Unit productions - Null productions –
Greiback Normal form – Chomsky normal form – Problems related to CNF and GNF.
S.
No
.
Question
Course
Outcom
e
Blooms
Taxanom
y Level
1
Give regular expressions for the following
L1=set of all strings of 0 and 1 ending in 00
L2=set of all strings of 0 and 1 beginning with 0 and ending with
1. NOV/DEC 2012
RE1=(0+1)
+
00
RE2=0(0+1)
+
1
C504.2
BTL 1
2
Differentiate regular expression and regular language.
NOV/DEC 2012
Refer notes
C504.2
BTL 1
3
Construct NFA for the regular expression a*b*.
MAY/JUNE 2012 Refer notes
C504.2
BTL 1
4
Is regular set is closed under complementation?Justify.
MAY/JUNE 2012
Closure under complement
• If L is a regular language, over alphabet ∑
Complement of L=∑* - L
• Let L = L(A) for DFA A = (Q, ∑, δ, q0, F)
• 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-
C504.2
BTL 1
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).
5
Prove that the complement of a regular language is also
regular.APR/MAY 2011
Complement of L
1
is constructed from L
1
by reversing the states and
the arrows in automata.
C504.2
BTL 1
6
Prove by pumping lemma, that the language 0
n
1
n
is not
regular.APR/MAY 2011
C504.2
BTL 1
7
Construct a DFA for the following:
(a) All strings that contain exactly 4 zeros.
(b) All strings that don’t contain the substring 110.
NOV/DEC 2011
1 1 1 1 1
0 0 0 0
0
0,1
1
0,1
1 1 0
0
0
C504.2
BTL 1
8
Is the set of strings over the alphabet {0} of the form 0n where n
is not a prime is regular? Prove or disprove.
NOV/DEC 2011
To prove this language is not regular, examine the complement
C504.2
BTL 1
because the set of regular languages is closed under complement.
Assume that the set is regular. Let p be the pumping length of the
language. Then, according to the pumping lemma, break the string
s=0
p
into s=xyz where y has positive length.
Then, s=xy
i
z=0
p+(i-1)|y|
must also be in the set for any i. In particular
let i=p+1.Then xy
p+1
z=0
p+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.
9
Let L = {w:w ε {0,1}* w does not contain 00 and is not empty}.
Construct a regular expression that generates L.
APR/MAY 2010
Regular Expression = (0+1)(1+10)*(101+1)*
C504.2
BTL 1
10
Prove or disprove that the regular languages are closed under
concatenation and complement. APR/MAY 2010
Closure under concatenation
• 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
Closure under complement
• If L is a regular language, over alphabet ∑
Complement of L=∑* - L
• Let L = L(A) for DFA A = (Q, ∑, δ, q0, F)
• 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).
C504.2
BTL 1
11
Give the regular expression for set of all strings ending in
00.NOV/DEC 2010
(0+1)*00
C504.2
BTL 1
12
State pumping lemma for regular set. NOV/DEC 2010,
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 UV
i
W is in L.
C504.2
BTL 1
13
What is a regular expression ?
MAY/JUNE 2013
A regular expression (abbreviated regex or regexp) is a sequence of
characters that forms a search pattern, mainly for use in pattern
matching with strings, or string matching, i.e. "find and replace"-like
operations
C504.2
BTL 1
14
Name any four closure properties of regular languages
MAY/JUNE 2013
union, intersection, complement, difference
C504.2
BTL 1
15
Construct NFA equivalent to the regular expression (0+1)01
NOV/DEC 2013
Refer notes
C504.2
BTL 1
16
Prove or disprove that (r+s)* = r* + s*
NOV/DEC 2014 Refer notes
C504.2
BTL 1
17
Let G be the grammar with
S→aB|bA
A→a|aS|bAA
B→b|bS|aBB
C504.2
BTL 1
18
What do you mean by null production and unit production? Give an
example. MAY / JUNE 2016
Refer notes
C504.2
BTL 1
19
Construct a CFG for set of strings that contain equal number of a’s
and b’s over ∑ = {a,b}. MAY / JUNE 2016
C504.2
BTL 1
S->A|B
A→aA|€
B→bB|€
20
What is unambiguity?
Refer notes
C504.2
BTL 1
21
Mention the application of CFG.
Refer notes
C504.2
BTL 1
22
Construct the Context free grammar representing the set of
palindromes over (0+1)* NOV/DEC 2015
S->0S0|1S1| ε
C504.2
BTL 1
23
What is meant by Context Free Grammar (CFG)? NOV/DEC
2016
C504.2
BTL 1
24
State Chomsky normal form theorem. NOV/DEC 2016
C504.2
BTL 1
25
Define Regular Expression.
Refer Notes
C504.2
BTL 1
26
What is null and unit production?
Refer Notes
C504.2
BTL 1
PART B
1
Prove that there exists an NFA with ε-transitions that accepts the
regular expression γ. (10)
MAY/JUNE 2012, NOV/DEC 2010
C504.2
BTL 1
2
Which of the following languages is regular? Justify.(Using
Pumping Lemma)
(i) L={a
n
b
m
| n,m>=1}
(ii) L={a
n
b
n
| n>=1} (8)
MAY/JUNE 2012
(iii) L={a
m
b
n
| m>n} (10)
NOV/DEC 2012
(iv) L={a
n
b
n
| n>=1} (6)
NOV/DEC 2010
C504.2
BTL 1
(v) L={0
n2
| n is an integer, n>=1} (6)
NOV/DEC 2014
3
Obtain the regular expression for the finite automata.
(8) MAY/JUNE 2012
a a
C504.2
BTL 1
4
Prove any two closure properties of regular
languages.(8)NOV/DEC 2012, NOV/DEC 2011, APRIL/MAY
2010
C504.2
BTL 1
5
Construct a minimized DFA from the regular expression
(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
C504.2
BTL 1
6
Construct a regular expression for the following DFA using
kleene’s theorem. (10) APR/MAY 2011
0 1
→*A A B
B C B
C A B
C504.2
BTL 1
7
Construct a ε-NFA for the following regular expression. (6)
q0
q1
q2
APR/MAY 2011
(i) (0+1)*(00+11)(0+1)*
C504.2
BTL 1
8
(i) What is the purpose of normalization? Construct the CNF and
GNF for the following grammar and explain 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
C504.2
BTL 1
UNIT III PUSHDOWN AUTOMATA 9
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic
pushdown automata – Equivalence of Pushdown automata and CFL - pumping lemma for CFL –
problems based on pumping Lemma.
S.
No.
Question
Course Outcome
Blooms
Taxanomy
Level
1
What is ambiguous grammar?
NOV/DEC 2012, MAY/JUNE 2013
Refer notes
C504.3
BTL 1
2
What are the diiferent types of language accepted
by a PDA and define them? NOV/DEC 2012
C504.3
BTL 1
• Accepted by null state
• Accepted by final state
3
Specify the use of context free grammar.
MAY/JUNE 2012
Refer notes
C504.3
BTL 1
4
Define parse tree with an example.
MAY/JUNE 2012
Refer notes
C504.3
BTL 1
5
Construct a CFG over {a,b} generating a language
consisting of equal number of a’s and b’s.
APR/MAY 2011
S→ aSbS | bSaS | SS
C504.3
BTL 1
6
Is the language of Deterministic PDA and Non –
deterministic PDA same? APR/MAY 2011
The language is not same. This language of NPDA is
a superset of the language of DPDA.
C504.3
BTL 1
7
Is the grammar below ambiguous S→ SS | (S) |
S(S)S | E?NOV/DEC 2011
• It is ambiguous
• The sentence such as E(E)E can have more
than one LMD (or) RMD (or) Parse tree.
C504.3
BTL 1
8
Convert the following grammar into an equivalent
one with no unit productions and no useless
symbols S→ABA A→aAA|aBC|bB B→
A|bB|Cb C→CC|Cc NOV 2011
Refer notes
C504.3
BTL 1
9
Consider the following grammar G with
productions APR/MAY 2010
S→ ABC | BaB
A→aA|BaC|aaa
C504.3
BTL 1
B→bBb|a
C→CA|AC
Give a CFG with no useless variables that
generates the same language.
Symbol C is non-generative, after removing
productions with C we have,
S→ BaB
A→ aA|aaa
B→bBb|a
CFG with no usless variables
{S→ BaB A→ aA|aaa B→bBb|a}
10
State the definition of Pushdown automata.
APR/MAY 2010
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
δ: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.
C504.3
BTL 1
11
Write down the context free grammar for the
language L = { a
n
b
n
|n>=1} NOV/DEC 2010,
NOV/DEC 2013
S→ aSb |ab
C504.3
BTL 1
12
Is the grammar E→E+E|id is ambigupus ?
Justify. NOV/DEC 2010
• It is ambiguous, The sentence such as
id+id+id can have more than one
LMD (or) RMD (or) Parse tree.
C504.3
BTL 1
13
What is a CFG ? MAY/JUNE 2013
A context-free grammar (CFG) is a formal
grammar in which 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.
C504.3
BTL 1
14
What are the different ways of language
acceptances by a PDA and define them?
NOV/DEC 2015
• Language accepted by a Empty store
• Language accepted by a Final state.
C504.3
BTL 1
15
Define pushdown Automaton MAY/JUNE
2016
A pushdown Automaton is a - NFA with
stack data structure where it can push strings
into and pop strings out of stack.
It consists of 7-tuples P = ( Q,,,,q0, z0
, F),Where Q is a finite set of states,is a
finite set of input symbols,is a finite set of
nonempty stack alphabets, is a transition
function,q0 is an initial state, Z 0 is the initial
start symbol of the stack , F is the set of
accepting states.is defined
as :Q()→Q*
C504.3
BTL 1
16
What are the different ways of language
acceptances by a PDA and define them
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 *
C504.3
BTL 1
17
Compare NFA and PDANOV/DEC 2013
Refer notes
C504.3
BTL 1
18
Give the general forms of CNF. NOV/DEC 2014
A→BC
A→a
C504.3
BTL 1
19
Show that CFLs are closed under substitutions
NOV/DEC 2014 Refer notes
C504.3
BTL 1
20
Convert the following CFG to a PDA.NOV/DEC
2015 S→aAA, A→aS|bS|a
C504.3
BTL 1
21
Does a Push down Automata have memory? Justify.
MAY/JUNE 2016 Refer Notes
C504.3
BTL 1
22
When is Push Down Automata (PDA) said to
be deterministic? NOV/DEC 2016
C504.3
BTL 1
23
What are the conventional notations of Push
Down Automata? NOV/DEC 2016
C504.3
BTL 1
24
List the main application of pumping Lemma
in CFL’s
C504.3
BTL 1
25
Compare Deterministic and Non deterministic PDA. Is
it true that non deterministic PDA is more powerful than
that of deterministic PDA? Justify your answer.
C504.3
BTL 1
26
Design the equivalence of PDA and CFG
C504.3
BTL 1
PART – B
Consider the following grammar for list
structures:
C504.3
BTL 1
1
S→a|^|(T) T→T,S|S
Find left most derivation, rightmost derivation
and parse tree for (((a,a),^(a)),a)(10) NOV/DEC
2012
2
Construct the PDA accepting the language
1. L={(ab)
n
|n>=1} by empty stack. (6)
NOV/DEC 2012
2. L={a
2n
b
n
|n>=1} Trace your PDA for the input
with n=3. (10) NOV/DEC 2012
3. L={ww
R
|w is in (a+b)*} (10)MAY/JUNE 2012
4. L={0
n
1
2n
} by empty stack(8)APR/MAY 2011
5. L={ww
R
w|w is in {0+1}*}(10)NOV/DEC 2010
C504.3
BTL 1
3
Find the PDA equivalent to the given CFG with
the following productions
1. S→A, A→BC, B→ba, C→ac (6) NOV/DEC
2012
2. S→aSb|A, A→bSa|S| ε (10) NOV/DEC 2011
C504.3
BTL 1
4
Is the following grammar is ambiguous? Justify
your answer.
1. E→ E+E |E*E | id (6) MAY/JUNE 2012
2. E→ E+E|E*E|(E)|a (4) APRIL/MAY 2011
C504.3
BTL 1
5
Find the context free languages for the following
grammars.
1. S→aSbS|bSaS| ε (10)
MAY/JUNE 2012
2. S→aSb|ab
3. S→aSb|aAb, A→bAa, A→ba (6)
NOV/DEC 2011
C504.3
BTL 1
6
Prove that if there exists a PDA that accepts by
final state then there exists an equivalent PDA
C504.3
BTL 1
that accepts by Null state. (8)
APRIL/MAY 2011
7
Is NPDA (Nondeterministic PDA) and DPDA
(Deterministic PDA) equivalent? Illustrate with
an example. (8) NOV/DEC 2011
C504.3
BTL 1
8
What are the different types of language
acceptances by a PDA and define them. Is it true
that the language accepted by a PDA by these
different types provides different languages?
(8) NOV/DEC 2011
C504.3
BTL 1
9
Construct PDA for the language
L = {ww
R
| W in (a+b)*)} MAY/JUNE
2013,NOV/DEC 2013, MAY/JUNE 2016
C504.3
BTL 1
UNIT IV TURING MACHINES 9
Definitions of Turing machines – Models – Computable languages and functions –Techniques
for Turing machine construction – Multi head and Multi tape Turing Machines - The Halting
problem –Partial Solvability – Problems about Turing machine- Chomskian hierarchy of
languages.
S.
No.
Question
Course Outcome
Blooms
Taxanomy
Level
1
State the pumping lemma for CFLs.
NOV/DEC 2012 Refer notes
C504.4
BTL 1
2
What are the applications of Turing Machine?
NOV/DEC 2012 Refer notes
C504.4
BTL 1
3
State pumping lemma for CFL.
MAY/JUNE 2012 Refer notes
C504.4
BTL 1
4
What is chomsky normal form?
MAY/JUNE 2012 Refer notes
C504.4
BTL 1
5
What is the height of the parse tree to represent a
string of length ‘n’ using Chomsky normal form?
APR/MAY 2011
n+1
C504.4
BTL 1
6
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)
q1 (q0,B,R) (q3,B,R)
q2 - -
representing even no
q3 - -
representing odd no
C504.4
BTL 1
7
Design a TM that accepts the language of odd
integers written in binary. NOV/DEC 2011
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 left one space and acepts if and only
if there is a 1 on the tape.
C504.4
BTL 1
8
State the two normal forms and give an example.
NOV/DEC 2011
1. Chomsky normal form A→BC |a
2. Greibach normal form X→bYXZ|a
C504.4
BTL 1
9
Convert the following grammar G in greibach
normal form.APR/MAY 2010
S→ABb|a A→aaA|B B→bAb
• No ε production in the given grammar
• Eliminating unit production A→B we have
S→ABb|a A→aaA|bAb B→bAb
• Eliminating useless variables A & B (non generating)
S→a
C504.4
BTL 1
Design a Turing machine with no more than three
states that accepts the language a(a+b)*. Assume
C504.4
BTL 1
10
∑ = {a,b} 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)
11
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
Г – A finite non empty set of tape symbols
δ - The transition function is given by
δ:Q X Г → Q X Г X {L,R,S}
q0 – Initial state
B ε Г – Blank Symbols
F - Final state
C504.4
BTL 1
12
What are the required fields of an instantaneous
description of a Turing machine? NOV/DEC 2016
C504.4
BTL 1
13
List the primary objectives of Turing Machine.
NOV/DEC 2016
C504.4
BTL 1
14
Is the language L={a
n
b
n
c
n
| n>=1} is context
free?Justify.NOV/DEC 2010
• It is not context free.
• Pumping Lemma for CFL is not satisfied.
C504.4
BTL 1
15
What is meant by Greibach Normal Form ?
MAY/JUNE 2013
A context-free grammar is in Greibach normal form
(GNF) if the right-hand sides of all production rules start
with a terminal symbol, optionally followed by some
variables. A non-strict form allows one exception to this
format restriction for allowing the empty word (epsilon,
ε) to be a member of the described language
C504.4
BTL 1
16
List the closure properties of Context Free
Languages MAY/JUNE 2013, NOV/DEC 2013
Union, intersection, kleene closure, substitution,
homomorphism
C504.4
BTL 1
17
List out the different techniques for turing
machine construction.NOV/DEC 2013
Refer notes
C504.4
BTL 1
18
Let G be the grammar S→aB|bA A→a|aS|bAA
B→b|bS|aBB. For the string aaabbabbba, Find (a)
LMD (b) RMD NOV/DEC 2014
Refer Notes
C504.4
BTL 1
19
Define Diagonalization (Ld) Language.
NOV/DEC 2014
Ld={wi | wi ∑ L(Mi)}
C504.4
BTL 1
20
Define a Turing Machine. OV/DEC 2015
Refer notes
C504.4
BTL 1
21
What is a multitape turing machine?
NOV/DEC 2015Refer notes
C504.4
BTL 1
22
What are the differences between a Finite automata
and a Turing machine? MAY/JUNE 2016
C504.4
BTL 1
23
What is Turing Machine? MAY/JUNE 2016
C504.4
BTL 1
24
What is multitape Turing machine? Explain in one
move. What are the actions take place in TM?
C504.4
BTL 1
25
What are the applications of Turing Machine?
C504.4
BTL 1
26
What are the techniques for TM construction?
C504.4
BTL 1
PART – B
1
Convert the following grammar into CNF
S→cBA, S→A, A→cB, A→AbbS, B→aaa
(6) NOV/DEC 2012
S→a|AAB, A→ab|aB| ε, B→aba| ε
(8) APR/MAY 2011
S→A|CB, A→C|D, B→1B|1, C→0C|0, D→2D|2
(16) APR/MAY 2010
S→aAD A→aB|bAB B→ b D→ d
(6) NOV/DEC 2014
C504.4
BTL 1
2
State and prove the pumping lemma for CFL.
What is its main application? Give two examples.
(10)
NOV/DEC 2012, NOV/DEC 2011, MAY/JUNE
C504.4
BTL 1
3
Design a Turing machine for the following
Reverses the given string {abb}. (8) NOV/DEC
2012
L={1
n
0
n
1
n
|n>=1} (10) MAY/JUNE 2012
C504.4
BTL 1
L={a
n
b
n
c
n
} (8) APR/MAY 2011
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
L={1
n
0
n
|n>=1} (8) NOV/DEC 2010
L={ww
R
| w is in (0+1)*} (8) NOV/DEC 2010
mplement the function “MULTIPLICATION”
using the subroutine “COPY”.
(12) NOV/DEC 2014
L={0
n
1
n
|n>=1} (10) NOV/DEC 2015
4
Write briefly about the programming techniques
for TM. (8) NOV/DEC 2012,MAY/JUNE
2013, NOV/DEC 2015
C504.4
BTL 1
5
Find Greibach normal form for the following
grammar
(i) S→AA | 1, A→SS |0
(10) MAY/JUNE 2012
(ii) S→a|AB, A→a|BC, B→b, C→b
(4) APR/MAY 2011
(iii) S→AA|0, A→SS|1
(8) NOV/DEC 2010
(iv) A
1
→A
2
A
3
, A
2
→A
3
A
1
|b, A
3
→A
1
A
2
|a
(10) NOV/DEC 2014
C504.4
BTL 1
6
Explain the different models of Turing machines.
(10) NOV/DEC 2011
C504.4
BTL 1
7
Discuss the various techniques for Turing
Machine Construction (16) NOV/DEC 2016
C504.4
BTL 1
8
(i) Write about Multi tape Turing Machines. (10)
NOV/DEC 2016
(ii) Explain highlight the implications of halting
problems (6) NOV/DEC 2016
C504.4
BTL 1
9
Describe the Chomsky hierarchy of languages.
NOV/DEC 2015
C504.4
BTL 1
UNIT V UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS 9
Unsolvable Problems and Computable Functions – Primitive recursive functions –
Recursive and recursively enumerable languages – Universal Turing machine. MEASURING
AND CLASSIFYING COMPLEXITY: Tractable and Intractable problems- Tractable and
possibly intractable problems - P and NP completeness - Polynomial time reductions.
PART - A
S.
No.
Question
Course Outcome
Blooms
Taxanomy
Level
1
When we say a problem is decidable? Give an
example of undecidable problem. NOV/DEC
2012 Refer notes
C504.5
BTL 1
2
What is recursively enumerable language?
NOV/DEC 2012, MAY/JUNE 2012, NOV/DEC
2010, MAY/JUNE 2013, NOV/DEC 2013
REL is the language accepted by a Turing Machine.
C504.5
BTL 1
3
Mention the difference between P and NP
problems. MAY/JUNE 2012
Refer notes
C504.5
BTL 1
4
How to prove that the Post Correspondence
problem is Undecidable. NOV/DEC 2011
Introduce a modified PCP and reduce the same to the
original PCP.
Again reduce L
u
to the modified PCP.
The chain of reduction infers if original L
u
is known
to be undecidable then conclude that PCP is
undecidable.
C504.5
BTL 1
5
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 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.
C504.5
BTL 1
6
State Rice’s theorem. APR/MAY 2010
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 language or is all RE languages, or
else it is non-trivial.
C504.5
BTL 1
7
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.
• Any Turing Machine can be encoded with a
binary string of 0’s and 1’s.
• 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
C504.5
BTL 1
If No: Ignore string
8
Mention the difference between decidable and
undecidable problems. NOV/DEC 2010
• Decidable Problem – Existence of an
algorithm
• Undecidable Problem – No algorithm
for solving it.
C504.5
BTL 1
9
What is universal turing machineNOV/DEC 2013
universal Turing machine (UTM) is a Turing
machine that can simulate an arbitrary Turing
machine on arbitrary input. The universal machine
essentially achieves this by reading both the
description of the machine to be simulated as well as
the input thereof from its own tape
C504.5
BTL 1
10
Define multiple turing machine.
NOV/DEC 2014
An extended TM model has more number of tapes. A
move is based on the state and on the vector of
symbols scanned by the hand on each of the tapes.
C504.5
BTL 1
11
Give example for NP-complete problems.
NOV/DEC 2014
Traveling Salesman Problem
C504.5
BTL 1
12
State when a problem is said to be decidable and
give an example of an undecidable problem.
NOV/DEC 2015
C504.5
BTL 1
13
What is a universal Language L
u
?
NOV/DEC 2015 Refer notes
C504.5
BTL 1
14
When is a Recursively Enumerable language said to
be Recursive? MAY/JUNE 2016
C504.5
BTL 1
15
Identify whether “Tower of Hanoi” problem is
tractable or intractable. Justify your answer.
MAY/JUNE 2016
C504.5
BTL 1
16
Define Universal Turing Machine NOV/DEC 2016
C504.5
BTL 1
17
Define NP-hard and NP-complete problems.
NOV/DEC 2016
C504.5
BTL 1
18
When a recursively enumerable language is said to
be recursive.
C504.5
BTL 1
19
Compare and Contrast recursive and recursively
enumerable languages.
C504.5
BTL 1
20
State when a problem is said to be decidable and give
an example of an undecidable problem
C504.5
BTL 1
21
Is it true that the language accepted by a non
deterministic Turing Machine is different from
recursively enumerable language?
C504.5
BTL 1
22
Give two properties of recursively enumerable sets
which are undecidable.
C504.5
BTL 1
23
Define the classes of P and NP
C504.5
BTL 1
24
When a language is said to be recursively
enumerable?
C504.5
BTL 1
25
Define Time and Space Complexity of TM.
C504.5
BTL 1
26
Distinguish between PCP and MPCP. What are the
concepts used in UTMs?
C504.5
BTL 1
PART – B
1
If L
1
and L
2
are recursive language then L
1
UL
2
is
a recursive language.(6)NOV/DEC 2012
C504.5
BTL 1
2
Prove that the halting problem is undecidable.(10)
NOV/DEC 2012, NOV/DEC 2010
C504.5
BTL 1
3
State and prove the Post’s correspondence
problem. (10)NOV/DEC 2012,
NOV/DEC 2010
C504.5
BTL 1
4
Write a note on NP problems.
(6) NOV/DEC 2012
C504.5
BTL 1
5
Explain undecidability with respect to post
correspondence problem. (8) MAY/JUNE2012
C504.5
BTL 1
6
State and prove Post Correspondence Problem
and Give example. (16) NOV/DEC 2014
C504.5
BTL 1
7
What is Post Correspondence problem (PCP)?
Explain with the help of an example. (16)
MAY/JUNE 2016
C504.5
BTL 1
8
(i) What are tractable problems? Compare it with
intractable problems. (10) NOV/DEC 2016
(ii) Outline the concept of polynomial time
reductions. (6) NOV/DEC 2016
C504.5
BTL 1
9
Prove that for two recursive languages L
1
and L
2
their union and intersection is recursive.
NOV/DEC 2013
C504.5
BTL 1
10
State and explain RICE theorem.
Prove that “MPCP reduces to PCP”.
C504.5
BTL 1