www.studymaterialz.

in

SRM VALLIAMMAI ENGINEERING COLLEGE

(An Autonomous Institution)
SRM Nagar, Kattankulathur – 603 203

DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING

QUESTION BANK

V SEMESTER

CS8501–THEORY OF COMPUTATION
Regulation – 2017

Academic Year 2020 – 21

Prepared by
Mr. N. Leo Bright Tennisson, Assistant Professor/ CSE
Mr. S. Venkatesh, Assistant Professor/CSE
 www.studymaterialz.in

SRM VALLIAMMAI ENGINEERING COLLEGE

(An Autonomous Institution)
SRM Nagar, Kattankulathur – 603 203.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

QUESTION BANK
SUBJECT : CS8501 THEORY OF COMPUTATION

SEM / YEAR: V/III

UNIT I
AUTOMATA FUNDAMENTALS
Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic
Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions
PART – A

Q.No Questions BT Level Competence

1. Differentiate between DFA and NFA. BTL-2 Understand

2. Define DFA. BTL-1 Remember
3. Define inductive proof. BTL-1 Remember
4. Identify NFA- ε to represent a*b | c. BTL-1 Remember
5. Consider the String X=110 and y=0110. Find BTL-4 Analyze
i) XY ii) X2 iii) YX iv) Y2
6. Describe the following language over the input set A={a,b}
L={ anbn | n>=1}. BTL-4 Analyze

7. Describe what is non-deterministic finite automata and the

applications of automata theory. BTL-1 Remember
8. Prove by induction on n≥1 that :
𝑛 BTL-3 Apply
1 𝑛
∑ =
𝑖(𝑖 + 1) 𝑛 + 1
𝑖=1

9. What is proof by contradiction? BTL-1 Remember

10. Describe an identifier with a transition diagram (automata). BTL-2 Understand
11. Define ε-NFA. BTL-1 Remember
12. Summarize minimization of DFA. BTL-5 Evaluate
13. Give the non-deterministic automata to accept strings containing
the substring 0101. BTL-2 Understand
14. Illustrate if L be a set accepted by an NFA then there exists a
DFA that accepts L. BTL-3 Apply
15. Define the term epsilon transition. BTL-2 Understand
16. Summarize the extended transition function for a ε-NFA. BTL-5 Evaluate
 www.studymaterialz.in

17. Create a FA which accepts the only input 101 over the input set:
Z={ 0,1} BTL-6 Create
18. Describe a Finite automata and give its types.
BTL-4 Analyze
19. Illustrate deductive proof.
BTL-3 Apply
20. Create a FA which checks whether the given binary number is
even. BTL-6 Create

PART - B
1. (i) Explain if L is accepted by an NFA with ε-transition then show
that L is accepted by an NFA without ε-transition. (6)

(ii) Construct a DFA equivalent to the NFA. M= ({p, q, r},{0,1},δ,

p,{q, s}) Where δ is defined in the following table.
(7)
BTL-5 Evaluate
0 1
p {q, s} {q}
q {r} {q, r}
r {s} {p}
s - {p}
2. Prove for every n>=1 by mathematical induction Apply
∑ (i)= {n(n+1)/2}. (13) BTL-3

3.
Let L be a set accepted by a NFA then show that there exists a
BTL-1 Remember
DFA that accepts L. (13)

4. Give non-deterministic finite automata accepting the set of

strings in (0+1)* such that two 0’s are separated by a string
whose length is 4i, for some i ≥ 0. (13)
BTL-2 Understand

5.
Construct DFA equivalent to the NFA given below: (13)

BTL-2 Understand
 www.studymaterialz.in

6. (i) Compose that a language L is accepted by some ε–NFA if

and only if L is accepted by some DFA. (6)
(ii) Consider the following ε–NFA. Compute the ε–closure of
each state and find it‟ s equivalent DFA. (7)
ε a b C BTL-6 Create
p ф {p} {q} {r}
q {p} {q} {r} ф
*r {q} {r} ф {p}

7. (i)Classify how a language L is accepted by some DFA if L is

accepted by some NFA. (7)
(ii)Convert the following NFA to its equivalent DFA. (6)

0 1 BTL-3 Apply
p {p, q} {p}
q {r} {r}
r {s} ф
*s {s} {s}

8. i) Construct the DFA to recognize odd number of 1’s and even

number 0’s . (7)
ii) Construct the DFA over {a, b} which produces not more than BTL-1 Remember
3 a’s. (6)

9. (i) Point out the steps in conversion of NFA to DFA and for the
following convert NFA to a DFA : (7)

BTL-4 Analyze
(ii) Infer the following to a regular expression. (6)

0 1
q q
q

0 0,1
 www.studymaterialz.in

10. Identify and explain the algorithm for minimization of DFA.

Using the above algorithm minimize the following DFA.
(13)

BTL-1 Remember

11. Tabulate the difference between the NFA and DFA .Convert the
following ε-NFA to DFA. (13)
states ε a b c
p Ф {p} {q} {r} BTL-1 Remember
q {p} {q} {r} Ф
*r {q} {r} ф {p}

12. (i).Describe the extended transition function for NFA ,DFA and
– ε-NFA. (6)

(ii) Consider the following ε-NFA for an identifier .Consider the

ε-closure of each state and give its equivalent DFA. (7)

BTL-2 Understand

13. (i)Given ∑ = {a, b} Analyze and construct a DFA which

recognize the language L= {bm a bn: m, n>0}. (13) BTL-4 Analyze
 www.studymaterialz.in

14. (i) Analyze and 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)
BTL-4 Analyze
(ii) Construct a DFA that accept the string {0, 1} that always
ends with 00. (7)

PART – C
1. (i) Draw and explain the transition diagram for recognizing the set
of all operators in c Language. (8)
(ii) Evaluate a DFA from the given NFA : (7)
M=({qo,q1},{a, b},δ,q0,{q1} with the state table diagram for δ given
BTL-5 Evaluation
below:
δ a b
qo {qo,q1} q1
q1 Ф {qo,q1}
2. Construct the following ε-NFA to DFA. (15)

states ε a b c
BTL-6 Create
p Ф {p} {q} {r}
q {p} {q} {r} {p, q}
*r {q} {r} ф Ф
3. Infer the DFA which is accepting the following language over the
alphabet{0,1}.The set of all the strings beginning with a1 that when
interrupted as a binary integer , is multiple of 5, For example strings BTL-4 Analyze
101,1010 and 1111 are in the language 0,100 and 111 are not.
(15)
4. Rewrite the basic approach to convert from NFA to regular
BTL-6 Create
expression. Illustrate with an example. (15)

UNIT II
REGULAR EXPRESSION AND LANGUAGES

Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties
of Regular Languages – Equivalence and Minimization of Automata.
.
PART - A
Q.No Questions BT Level Competence

1. List the operators of Regular Expressions. BTL-1 Remember

2. Differentiate between regular expression and regular. BTL-1 Remember
3. Tabulate the regular expression for the following BTL-4 Analyze
L1=set of strings 0 and 1 ending in 00.
4. What are the closure properties of regular languages? BTL-2 Understand
 www.studymaterialz.in

5. Explain a finite automaton for the regular expression 0*1*. BTL-1 Remember

6. Identify a regular expression for the set of all the strings. BTL-1 Remember
7. Construct a regular expression for the set of all the strings
have odd number of 1’s R.E=1(0+11)*. BTL-3 Apply

8. Compose the difference between the + closure and * closure. BTL-4 Analyze
9. Illustrate a regular expression for the set of all strings of 0’s. BTL-2 Understand
10. What is the Closure property of regular set S.? BTL-2 Understand
11. Construct regular expression corresponding to the state BTL-2 Understand
diagram:

12. Find out the language generated by the regular expression

(0+1)*. BTL-5 Evaluate

13. Name the four closure properties of RE.

BTL-1 Remember
14. Is it true the language accepted by any NFA is different from
the regular language? Justify your answer. BTL-4 Analyze
15. Show the complement of a regular language is also regular. BTL-3 Apply
16. Construct a DFA for the regular expression aa*bb*.
BTL-3 Apply
17. State the precedence of RE operator. BTL-5 Evaluate
18. Construct RE for the language over the set z= {a, b} in which
total number of a’s are divisible by 3. BTL-6 Create
19. Define RE.
BTL-1 Remember
20. Create RE to describe an identifier and positive integer. BTL-6 Create
PART - B
1.
Demonstrate how the set L= {abn/n>=1} is not a regular.
BTL5 Evaluate
(13)
2. Express that the regular languages are closed under: (13)
(a)union (b)intersection (c) Kleene Closure (d)Complement BTL-1 Remember
(e)Difference
3.
Examine whether the language L= (0n1n| n>=1) is regular or BTL-2 Understand
not? Justify your answer. (13)
 www.studymaterialz.in

4. (i) Describe a Regular Expression. Write a regular Expression

for the set of strings that consists of alternating 0’s and 1’s.
(6)
BTL1 Remember
(ii) Construct Finite Automata equivalent to the regular
expression (ab+a)*. (7)
5. (i) Describe the closure properties of regular languages. (6)

(ii) Describe NFA with epsilon for the RE=(a/b)*ab and BTL1 Remember
convert it into DFA and further find the minimized
DFA. (7)
6. Show that the following languages are not regular. BTL-3 apply
(i) {wϵ{a,b}* |w=wR }. (7)
(ii) Set of strings of 0’s and 1’s, beginning with a 1, whose
value treated as a binary number is a prime (6)

7. Verify the whether L ={ a 2n| n>=1} regular. (13) BTL-3 Apply

8. i) Prove the reverse of a regular language is regular. (6)

ii) A homomorphism of regular language is regular. (7) BTL-4 Analyze

9. Discuss on regular expressions. (13) BTL-2 Understand

10 i) Prove that any language accepted by a DFA can be BTL-6 Create

represented by a regular expression. (7)
ii) Construct a finite automata for the regular expression
10+(0+11)0*1. (6)

11 Explain the DFA Minimization algorithm with an example. BTL-1 Remember

(13)
12
Demonstrate how the set L= {anbm| m,n>=1} is not a regular. BTL 2 Understand
(13)

13 i) Prove the L1 and L2 are two languages then L1- L2 is BTL 4 Analyze
regular. (7)
ii) Prove the L1 and L2 are two languages then L1 . L2 is
regular. (6)

14 i) Prove the L1 and L2 are two languages then L1 U L2 BTL-4 Analyze

is regular. (7)
ii) Prove the L1 and L2 are two languages then L1
intersection L2 is regular. (6)

PART C

1. (i) Deduce into regular expression that denotes the BTL-5

Evaluate
language accepted by following DFA. (7)
 www.studymaterialz.in

(ii) Evaluate the equalities for the following RE and prove

for the same: (8)
a. b+ab* +aa*b+aa*ab*
b. a*(b+ab*).
c. a(a+b)*+aa(a+b)*+aaa(a+b)*

2 Set the algorithm for minimization of a DFA. Develop a BTL-6 Create

minimized DFA for the RE (a+b)(a+b)* and trace for the
string baaaab. (15)
3 Point out about the regular expression and regular Language. BTL-4 Analyze
(15)
4 Develop the procedure for minimizing DFA with example. BTL-6 Create
(15)

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.

PART - A
Q.No Questions BT Level Competence

1. Express the ways of languages accepted by PDA and BTL 2 Understand

define them?
2. Understand
Summarize PDA .Convert the following CFG to PDA BTL 2
S aAA , A aS|bS|a.
3. Define ambiguous grammar and CFG. BTL 1 Remember

4. Define parse tree and derivation. BTL 1 Remember

5. BTL 2 Understand
Examine the context free Grammar representing the set
of Palindrome over (0+1)*
6. Compare Deterministic and Non deterministic PDA. Is it BTL 2 Understand
true that non deterministic PDA is more powerful than that
of deterministic PDA? Justify your answer.
7. BTL 1 Remember
When is PDA said to be deterministic?

8. Examine the string aaabbabbba for the Grammar G with BTL 5 Evaluate
SaB|bA
A a|aS|bAA
B b|bS|aBB
9. Examine whether a pushdown automata has a memory? BTL 1 Remember
 www.studymaterialz.in

10. Design equivalence of PDA and CFG. BTL 6 Create

11. Point out the languages generated by a PDA using final BTL 4 Analyze
state of the PDA and empty stack of that PDA.
12. Illustrate the rule for construction of CFG from given BTL 3 Apply
PDA.
13. Give a CFG for the language of palindrome string over
BTL 5 Evaluate
{a,b}.Write the CFG for the language ,L=(anbn|≥n).
14. What is Instantaneous Descriptions ( ID ) ? BTL 1 Remember

15. Show that L={ap/p is prime} is not context free. BTL 3 Apply

16. Infer the CFG for the set of strings that contains equal number
BTL 4 Analyze
of a’s and b’s over ∑ ={a,b}.
17. List the various types of grammar with example BTL 1 Remember

18. Illustrate the rightmost derivation (a+b)*c for using the

grammar and also state whether a given grammar is
BTL 3 Apply
ambiguous one or not.
EE+E/E*E/(E)/id

19. Point out the additional features a PDA has when compared
BTL 4 Analyze
with NFA.
20. Convince your answer of acontext free grammar for the given
BTL6 Create
expression (a+b) (a+b+0+1)* .

PART - B
1. (i) Discuss about PDA and CFL Prove the equivalence of PDA
and CFL. (6) BTL 2 Understand
(ii) If L is Context free language then prove that there exists
PDA M such that L=N(M). (7)
2.
(i) Describe the different types of acceptance of a PDA. Are
they equivalent in sense of language acceptance? Justify your BTL 1
answer. (7) Remember
n n
(ii) Design a PDA to accept {0 1 |n>1}.Draw the transition
diagram for the PDA and identify the instantaneous
description (ID) of the PDA which accepts the string ‘0011.
(6)
3. (i) Identify that deterministic PDA is less powerful than
non-deterministic PDA. (7)
n m n BTL 1 Remember
(ii) Construct a PDA accepting {a b a / m, n>=1} by empty
stack. Also tell the corresponding context-free grammar
accepting the same set. (6)
 www.studymaterialz.in

4. (i) Construct the parse tree for the string 1+2*3 Given
the grammar G=(V,  ,R,E)where
V={E,D,1,2,3,4,5,6,7,9,0,+,-,*,/,9,)}
 ={1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)} where R contains the
following rules :
E D|(E)|E+E|E-E|E/E BTL 6
D 0|1|2|…9 (6) Create

(ii)Let G=(V,T,P,S) be a Context Free Grammar then prove

that if the recursive inference procedure call tells us that
terminal string W is in the language of variable A ,then there is
a parse tree with a root A and yield w. (7)

5. (i)Define Non Deterministic Push Down Automata. Is it true

that DPDA and NDPDA are equivalent in the sense of
language acceptance is concern? Justify Your answer. (5)
(ii)Convert PDA to CFG.PDA is given by
P=({p, q},{0,1},{X,Y},δ, q, Z}, δ is defined by
δ(p,1,z)={(p, XZ)}, BTL 1 Remember
δ(p, ε, Z)={p, ε)},
δ(p,1,X)={(p, XX)},
δ(q,1,X)={(q, ε)},
δ(p,0,X)={(q,X0}
δ(q,0,Z)={(p, Z)} (8)
6. (i) Define PDA. Give an Example for a language accepted by
PDA by empty stack. (7)
(ii) Convert the grammar
BTL 2 Understand
S ->0S1|A
A ->1A0|S| ε into PDA that accepts the same language by the
empty stack .Check whether 0101 belongs to N(M). (6)

7. (i) Analyze the theorem: If L is Context free language then

prove that there exists PDA M such that L=N (M). (7) Analyze
(ii) Prove that if there is PDA that accepts by the final state BTL 4
then there exists an equivalent PDA that accepts by Null
State. (6)
8. Solve the following grammar
SaAa | bBb | BB
A C
B S | A
C  S | ε for the string abaaba .Give BTL 5 Evaluate
i) Left most derivation (3)
ii)Right most derivation (3)
iii)Derivation Tree (3)
iv) For the string abaabbba, find the right most derivation.(4)
 www.studymaterialz.in

9. (i) Examine Construct the grammar for the following PDAM.

M=({q0, q1},{0,1},{X,z0},δ,q0,Z0,Φ) and where δis given by
δ(q0,0,z0)={(q0,XZ0)},
δ(q0,0,X)={(q0,XX)},
δ(q0,1,X)={(q1, ε)},
δ(q1,1,X)={(q1, ε)}, BTL 3 Apply
δ(q1,ε,X)={(q1, ε)},
δ(q1, ε, Z0)= {(q1,ε)}. (7)
(ii) Prove that if L is N(M1) for some PDA M1 then L is
L(M2 ) for some PDA M2. (6)

10. Construct a PDA that recognizes and analyzes the

language BTL 4 Analyze
{aibjck| i,j,k>0 and i=j or i=k} and also
explain about PDA acceptance
(i) From empty Stack to final state. (6)
(ii From Final state to Empty Stack. (7)
11. Suppose L=L(G) for some CFG G=(V,T,P,S), then prove that BTL-1 Remember
L-{ ϵ} is L(G’) for a CFG G’ with no useless symbols or ϵ-
productions. (13)
12. (i) Describe the PDA that accept the given CFG (7)
S→xaax BTL-2 Understand
X→ax/bx/€
(ii) Express a PDA for the language anbman+m (6)
13. (i) Illustrate a PDA for the language {WCWR/W€{0,1}}. (7)
BTL-3 Apply
(ii) Illustrate a CFG for the constructed PDA. (6)
14. (i) Identify CFG for the language L={0 i1j 0k | j>i+k} (7)
(ii) Define derivation tree. Explain its uses with an example.
BTL-4 Analyze
(6)

PART – C
1. (i) Design and Explain a PDA to accept each of the following
language BTL-5 Evaluation
{aibjck|i=j or j=k} (7)
(ii) The set of all string with twice as many 0’s and 1’s. (8)
2. (i) Let P be a PDA with empty stack language L=N(P) and
suppose that ε is not in L. Design how you would modify P so BTL-6 Create
that it accepts L U { ε} by empty stack. (8)
(ii) Design a DPDA for even length palindrome. (7)
3. (i) Convert the following CFG to PDA and analyze the answer
(a+b) and a++. (8)
Ia|b|Ia|Ib|I0|I1
EI|E+E|E*E|(E) BTL-4 Analyze
(ii) Convert the following CFG to PDA by empty stack. (7)
S0S1/A;
A1A0/S/ ε Infer whether 0101 belongs to N(M).

4. (i)If L is a CFL then prove that there exists PDA M, such that
L=N(M) , language accepted by empty stack. (7) BTL-6 Create
m n
(ii)Construct a PDA empty store , L= {a b |n<m}. (8)
 www.studymaterialz.in

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.
PART - A
Q.No Questions BT Level Competence

1. Conclude the procedure for converting CNF to GNF with an BTL 2 Understand
example.
2. Illustrate the Basic Turing Machine model and explain in one
BTL 3 Apply
move. What are the actions take place in TM?

3. Define the two normal forms of CFG. BTL 1 Remember

4. Point out the hierarchy summarized in the Chomsky BTL 4 Analyze
hierarchy.
5. Define the pumping Lemma for CFLs. BTL1 Remember
6. Define Turing Machine. When do you say a Turing machine is BTL1 Remember
an algorithm?
7. Discuss the applications of Turing machine. BTL 2 Understand
8. When do you say a CFG is ambiguous? BTL 1 Remember
9. What is the class of language for which the TM has both
accepting and rejecting configuration? Can this be called a BTL 2 Understand
Context free Language? Discuss.
10. Show the following grammar into an equivalent one with no
unit productions and no useless symbols
SABA
BTL 3 Apply
AaAA|aBC|bB
BA|bB|Cb
CCC|cC

11. Explain the special features of TM? Define universal TM. BTL 5 Evaluate
Define Instantaneous description of TM.
12. Define GNF. BTL 1 Remember
13. Prepare the difference between finite automata and turing BTL 6 Create
machine.
14. List the three ways to simplify a context free grammar. What
BTL 5 Evaluate
are the properties of the CFL generated by a CFG?

15. Draw a transition diagram for a Turing machine to identify BTL 1 Remember
n mod 2.
16. Express the techniques for TM construction. BTL 2 Understand
17. Develop the short notes on two-way infinite tape TM. BTL 6 Create
18. Differentiate TM and PDA. BTL 4 Analyze
19. Point out the role of checking off symbols in a Turing BTL 4 Analyze
Machine.
20. Illustrate Halting Problem. BTL 3 Apply
 www.studymaterialz.in

PART - B
1. Express the following grammar G into Greibach Normal
Form(GNF) (13)
SXA|BB BTL 1 Remember
Bb|SB
Xb
Aa
2. Use the CFL pumping lemma to show how each of these
languages not to be context-free {aibjck| i<j<k}. (13) BTL 2 Understand

3. (i) Discuss a TM to accept the language LE={1n 2n 3n|n >=

1} BTL 2 Understand
(6)
(ii) Construct a turing machine that estimate unary
multiplication (Say 111 X 11 = 11111) (7)
4. (i) Illustrate the Turing machine for computing f(m, n)=m-n
( proper subtraction). (7)
BTL 3 Apply
(ii) Demonstrate a Turing Machine to compute f(m+n)=m+n,
m, n>=0 and simulate their action on the input 0100. (6)

5. (i) Examine the role of checking off symbols in a Turing

Machine. (6) BTL 1 Remember
(ii) Describe a Turing Machine M to implement the function
“multiplication” using the subroutine copy. (7)
6. (i) Demonstrate the implications of halting problem. (7)
(ii) Show that if a language is accepted by a multitape turing BTL 3 Apply
machine, it is accepted by a single-tape TM . (6)
7. (i) Summarize in detail about multihead and multitape TM with
an example. (7) BTL 5 Evaluate
(ii) Construct a Turing Machine to accept palindromes in an
alphabet set ∑={a, b}.Trace the strings “abab” and “baab”. (6)
8. (i) Explain the TM as computer of integer function with an
example. (7) BTL 4 Analyze
(ii) Design a TM to implement the function f(x)= x+1. (6)
9. (i) Design a TM to accept the set of all strings {0,1} with 010
as substring. (7) BTL 6 Create
(ii) Write shot notes on Two –way infinite tape TM. (6)
10. (i) Describe computing a partial function with a TM. (6) BTL 1 Remember
n n n
(ii) Design a TM to accept the language LE={a b c |n >1}. (7)
11. (i) Define Turing machine for computing f(m, n)=m*n, n€N. (7)
(ii) Write notes on Partial solvability. (6) BTL -1 Remember

12. (i) Construct a TM to reverse the given string {abb}. (6)

(ii) Explain Multi tape and Multi head Turing machine with BTL 2 Understand
suitable example. (7)
 www.studymaterialz.in

13. (i) Analyze and Construct a TM to compute a function f(w)

=WR where W€{a,b}. (7) BTL 4 Analyze
(ii) Construct Turing machine (TM) that replace all
occurrence of 111 by 101 from sequence of 0’s and 1’s. (6)
14.(i) Infer the Chomsky grammar classification with necessary
example. (6) BTL 4 Analyze
(ii) Explain a TM with no more than three states that accepts
the language. a(a+b)*.Assume €={a,b}. (7)
PART – C
1. (i)Compose the limitation of automata for Type 3, Type 2, type
0 languages. (7)
(ii) Consider two-tape Turing Machine (TM) and determine
BTL-6 Create
whether the TM always writes a nonblank symbol on its second
tape during the computation on any input string ‘w’. Formulate
this problem as a language and show it is undecidable. (8)

2. i) Define pumping lemma for CFL. Show that L={aibjck, i<j<k}

is not context free and Judge your answer. (6)
ii) Construct a TM to move an input string over the alphabet A= BTL-5 Evaluate
{a} to the right one cell. Consider that the tape head starts
somewhere on a blank cell to the left of the input string to the
right one cell , leaving all the remaining cell blank. (9)

3. (i) Design and explain a TM to compute f(m,n) = m*n , for all

m,n€ N. (6) BTL-4 Analyze
(ii) Explain how a multi-track in a TM can be used for testing
given positive integer is a prime or not. (9)

4.(i) Prepare a subroutine to move a TM head from its current

position to the right, skipping over all 0’s until reaching a 1 or
a blank. If the current position does not hold 0, then the TM
should halt. You may assume that there are no tape symbol other BTL-6 Create
than 0, 1 and B(blank). Then, use this subroutine to design to
TM that accepts all strings of 0’s and 1’s that do not have two
1’s in a row. (8)
(ii) Write short notes on checking off symbols. (7)
 www.studymaterialz.in

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
Q.No Questions BT Level Competence

1. Distinguish between PCP and MPCP? What are the concepts BTL 2 Understand
used in UTMs?
2. List out the features of universal turing machine. BTL 1 Remember
3. When a recursively enumerable language is said to be
BTL 2 Understand
recursive? Discuss on it.

4. Compare and contrast recursive and recursively enumerable BTL 4 Analyze

languages
5. State when a problem is said to be decidable and give an
example of an undecidable problem. BTL 1 Remember

6. Define NP hard and NP completeness problem. BTL 1 Remember

7. Define a universal language Lu? BTL 1 Remember
8. Is it true that the language accepted by a non-deterministic
Turing Machine is different from recursively enumerable BTL 5 Evaluate
language? Judge your answer.
9. Formulate the two properties of recursively BTL 6 Create
enumerable sets which are undecidable
10. When a problem is said to be decidable? Give an example of BTL 4 Analyze
undecidable problem. Analyze it.
11. What is (a) recursively enumerable languages (b) recursive BTL 6 Create
sets? Generalize your answer.
12. Define the classes of P and NP. BTL 1 Remember
13. Is it true that complement of a recursive language is recursive? BTL 2 Understand
Discuss your answer.
14. Describe an example of an undecidable problem. BTL 1 Remember
15. Point out the properties of recursive and recursive enumerable BTL 4 Analyze
language.

16. Illustrate on Primitive Recursive Function. BTL 3 Apply

17. Show the Properties of Recursive Languages. BTL 3 Apply
18. Explain about tractable problem. BTL 5 Evaluate
19. Describe post correspondence problem. BTL 2 Understand

20. Illustrate about Time and space complexity of TM. BTL 3 Apply
PART - B
 www.studymaterialz.in

1. (i)Describe about the tractable and intractable problems. (7) BTL 1 Remember
(ii)Identify that “MPCP reduce to PCP”. (6)
2. (i) Describe about Recursive and Recursive Enumerable
languages with example. (7) BTL 1 Remember
(ii) State and describe RICE theorem. (6)
3. (i) Summarize diagonalization language. (6)
(ii) Discuss the significance of universal turing machine and BTL 2 Understand
also construct a turing machine to add two numbers and encode
it. (7)
4. Discuss post correspondence problem .Let ∑={0,1}.Let A and
B be the lists of three strings each ,defined as
List A List B
i wi xi
1 1 111 BTL 2 Understand
2 10111 10
3 10 0
(i) Does the PCP have a solution? (7)
(ii) Prove that the universal language is recursively
enumerable. (6)
5. (i)Explain computable functions with suitable example. (6) BTL 4 Apply
(ii)Explain in detail notes on Unsolvable Problems. (7)
6. (i) Describe in detail notes on universal Turing machines with
example. (7) BTL 1 Remember
(ii) Collect and write the short notes on NP-complete
problems. (6)
7. (i) Show that the diagonalization language (Ld) is not a
recursively enumerable. (7) BTL 3 Apply
(ii) Illustrate about unsolvability. (6)
8. Prove that Post Correspondence Problem is undecidable. (13)
BTL 5 Evaluate
9. (i) Explain about Universal Turing machine and show that the
universal language (Lu) is recursively enumerable but not
recursive. Generalize your answer. (8) BTL 6 Create
(ii) Design and explain how to measure and classify
complexity. (5)
10. (i) Explain about the recursively Enumerable Language with
example. (6)
BTL 4 Analyze
(ii) Point out that the following problem is undecidable. Given
two CFGs G1 and G2 is L(G1) L(G2) =∅ . (7)
11. (i) Show that the characteristic function of the set of all even
number is recursive. (7) BTL-3 Apply
(ii) Illustrate in detail notes on primitive recursive functions
with examples. (6)
 www.studymaterialz.in

12. (i)Point out the Measuring and Classifying Complexity. (7)

BTL-4 Analyze
(ii)Does PCP with two lists x=(b,b ab3,ba) and y=(b3,ba,a)
have a solution. Analyze your answer. (6)
13. (i) Discuss in detail about Time and Space Computing of a
Turing Machine. (6)
BTL-2 Understand
(ii) Express two languages which are not recursively
enumerable. (7)
14. (i) Describe in detail Polynomial Time reduction and NP-
completeness. (7) BTL 1 Remember
(ii) List out the short notes on NP-Hard Problems. (6)
PART – C
1. Consider and find the languages obtained from the following
operations:
(i) Union of two recursive languages. (5) BTL-5 Evaluate
(ii) Union of two recursively enumerable languages. (5)
(iii) L if L and complement of L are recursively enumerable. (5)
2. Prove that the universal language is recursively enumerable but BTL-6 Create
not recursive. Generalize your answer. (15)

3. (i) Plan and explain on decidable and un-decidable problems

with an example (7) BTL-6 Create
(ii) Design and prove that for two recursive languages L1 and
L2 their union and intersection is recursive. (8)
4. (i) Compare and write about tractable and untractactable
problems with an example. (10) BTL-4 Analyze
(ii) Explain the language Lu and show that Lu is RE language.
(5)