CS 3452 - THEORY OF COMPUTATION

UNIT I AUTOMATA AND REGULAR EXPRESSIONS

PART-A

1. Define hypothesis.
2. Define inductive proof.
3. What is structural induction? May/June 2011
4. What is proof by contradiction? May/June 2012

5. Define deductive proof. Nov/Dec 2014

6. State the principle of induction.

7. Define Set, Infinite and Finite Set.

8. Give some examples for additional forms of proof.
9. Prove 1+2+3+…............................+n= n(n+1)/2 using induction method.

10. Write any three applications of Automata Theory.

11. Define i. Finite automaton (or) What is a finite automaton?

12. Draw transition diagram for an identifier. Nov/Dec 2013

13.

14. Define Deterministic Finite Automata. May/June 2013, Nov-Dec 2016,2019

15. Define Non-Deterministic Finite Automata. Nov/Dec 2013
16. Define NFA with € transition.
17. Design FA which accepts odd number of 1’s and any number of 0’s.

18. Design FA to check whether given unary number is divisible by three.

19. Design FA to check whether given binary number is divisible by three.

20. Design FA to accept the string that always ends with 00.

21. Design DFA to accept the strings over {0,1} with two consecutive 0’s. C Nov/Dec 2014

PART B

1. Prove the following by induction for all n≥0 A May/June 2014

i. 12+22+32+42+…….+n2=(n(n+1)(2n+1))/6 May/June 2016
ii. 13+23+….+n3=(n2(n+1)2)/4
2. Prove the following by mathematical induction method:
i. 2n>n for all n≥0
ii. X≥4,2x≥x2
3. Prove by Induction that
i. n3+(n+1)3+(n+2)3 is divisible by 3 and n>0
ii. S(n)=an-bn is divisible by a-b for all n>0
4. Prove
i. S(n)=52n -1 is divisible by 24 for n>0
ii. 1+2+……+n=(n(n+1))/2 Nov/Dec 2022
5. i. Design DFA to accept the Language
L={w/w has both even number of 0‘s and even number of
1‘s}
ii. Construct DFA that accepts input string of 0‘s and 1‘s that end with 11.
Construct DFA for the set of all strings {0,1} with strings ending with 01.
Construct DFA for the Language L={0n/n mod 3=2,n≥0}
Construct DFA for all the set of strings with {0,1} that has three consecutive 1‘s.
6. i. Construct an NFA for the set of strings with {0,1} ending with 01 draw the transition
table for the same and check whether the input string 00101 is accepted by above NFA.

ii. Construct NFA for set of all strings {0,1} that ends with three consecutive 1‘s
at its end.
iii. Construct NFA for set of all strings {a,b} with abb as substring.
7. If a Regular language ‗L‘ is accepted by a Non – deterministic Finite automata
then there exist a Deterministic Finite Automata that accepts ‗L‘
Nov/Dec 2013&Nov/Dec 2014
8. A Language ‗L‘ is accepted by some ε – NFA if and only if L is accepted by NFA
without ε transition May/June 2012 & Nov/Dec 2013

9. Convert to a DFA, the following NFA May/June 2013

a b
p(start) {p} {p,q}
q {r} {r}
r {Φ} {Φ}
10. Convert the following NFA-with ε, to a NFA- without ε
ε
0 1 2
q0
{q0} {φ} {φ} {q1}
(start)
q1 {φ} {q1} {φ} {q2}
* q2 {φ} {φ} {q2} {φ}

11. Convert the following NFA-with ε, to a NFA- without ε

a b ε
q0
{q0} {φ} {q1}
(start)
* q1 {φ} {q1} {φ}

12. Convert the following NFA-with ε, to a NFA- without ε

a b c ε
p(start) {q} {p} φ φ
q {r} Φ {q} φ
*r Φ Φ φ {r}
13. i. Prove that 2 is not rational.
ii. Construct a DFA accepting all strings w over {0,1} such that the number of 1‘s in w is 3 mod 4
Nov/Dec 2011
n

14. Prove by induction on n that  i  ( n ( n  1)) / 2 May/June 2012

i0
 15. Construct a DFA accepting binary strings such that the third symbol from the right end is
1 May/June 2012
16. Construct NFA without ε transitions for the NFA given below

17. Construct an NFA accepting binary strings with two consecutive 0‘s. May/June 2012
18. Explain different forms of proof with examples. May/June 2012
19. i. Prove that if n is a positive integer such that n mod 4 is 2 or 3 then n is not a
perfect square. May/June 2012
ii. Construct a DFA that accept the following language.

{x { a , b } : |x|a=odd and |x|b= even.

20. i. Construct DFA to accept the language L= { w / w I of even length and begins with 11}

ii. Write a note on NFA and compare with DFA. May/June 2013
21. Construct DFA equivalent to the NFA given below: Nov/Dec 2013

22. Give FA accepting the following language over the alphabet

i. Number of 1‘s is a multiples of 3

ii. Number of 1‘s is not a multiples of 3 Nov/Dec 2013
23. Discuss the application of FA. Nov/Dec 2013

24. Construct a DFA that accepts all strings on {0,1} except those containing the substring 101.
May/June 2014

25. i. Construct a NFA accepting the set of strings over {a,b} ending in aba. Use it to
construct a DFA accepting the same set of strings. May/June 2014

ii. Construct NFA with ε moves which accepts a language consisting the stings of any
number of a‘s, followed by any number of b‘s, followed by any number of c‘s.

2
26. Prove that L={0 i / i is an integer; i>0} is not regular.A Nov/Dec 2014, 2015

27. i. Prove that every tree has ‗e‘ edges and ‗e+1‘ nodes. A Nov/Dec 2014
 ii. Prove that for every integer n  0 the number 42n+1+3n+2 is a multiple of 13. A

28. Construct a DFA equivalent to the the NFA M=({a,b,c,d},{0,1}, δ,a,{b,d}) where δ is
defined as Nov/Dec 2014

δ 0 1
a {b,d} {b}
b c {b,c}
c d a
d - a

29. Design a DFA accepts the following strings over the alphabets {0, 1} that contain a pattern
11. Prove this using mathematical induction. April/May 2015

30. Design a NFA accept the following strings over the alphabets {0,1} that begins with 01
and ends with 11. Check for the validity of 01111 and 0110 strings. April/May 2015

31. Prove that ―A language L is accepted by some DFA if and only if L is accepted by
some NFA‖.

32. Consider the following ε-NFA for an identifier. Consider the ε-closure of each state and
find it‘s equivalent DFA. (10) Nov/Dec 2015

33. Construct a NFA that accepts all strings hat end in 01. Give its transition table and extend
transition function for the input string 00101. Also construct a DFA for the above NFA using
subset construction method. May-June2016

34. Construct DFA which recognize L={bmabn/ m,n>0} Nov-Dec2016

35. Determine the DFA from a given NFA Nov-Dec2016

36. Prove for the every n>=1 by mathematical induction ∑ ={n(n+1)/2}2

May-June 2017

37. Convert the epsilon NFA and list the difference between NFA and DFA.
Nov-Dec2017
38. Convert the following E-NFA to NFA and then convert the resultant NFA to DFA.
Nov-Dec 2018

39. Prove that a language L is accepted by some NDFA if and only if L is accepted by
some DFA. Nov-Dec 2018

40. Prove by induction on n>=1 that Nov-Dec 2019.

41. Convert to a DFA, the following NFA Nov-Dec 2019

0 1
P(start) {p,q} {p}
Q {r} {r}
R {s} -
S {s} {s}

42. Give NFA 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. U Nov-Dec 2019
*
43. Construct a minimized DFA from R.E (x+y)x(x+y) . Trace for a string w=xxyx.
Nov/Dec 2011
 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.

PART A

1. Differentiate regular expression and regular language Nov/Dec 2012

(Or)
2. What is regular expression? May/June 2013

3. Give the regular expression for set of all strings ending in 00. Nov/Dec 2010

4. State pumping lemma for regular language. Nov/Dec 2022

Nov/Dec 2010, 2013 , 2014 & 2017 , May-June 2016, Nov/Dec
2018,2019
5. Give the regular expression for the following Nov/Dec 2012
6. Name any four CFG. May/June 2013& May/June 2014 Nov-Dec 2016

7. Is regular set is closed under complement? Justify. May/June 2012

8. Construct NFA for the regular expression (0+1)01 Nov/Dec 2013

9. Prove or disprove that (r+s)*=r*+s*. Nov/Dec 2014

10. Give English description of the following language (0+10)*1*. April/May 2015

11. Write RE for the set of strings over {0,1} that have atleast one. Nov/Dec 2015
12. Show whether a language L=(0n12n/n>0} is regular or not using pumping Lemma.
E May-June 2017

13. Suppose L is regular. We then have some p>0 and some |

m|>p apb2p m=uvw and |uv|≤p and uviw∈L for all i>0
As |uv|≤p
then it follows that v=al. However, as uviw≡ap+lb2p it shows that as p+l≠2p therefore L is not
regular.
 PART-B

1. State and explain the conversion of DFA into R.E using Arden‘s theorem. Illustrate with an
example. Nov/Dec 2011

2. i. Define regular expression. R Nov/Dec 2011

ii. Show that (1+00*1)+(1+00*1)(0+10*1)*(0+10*1)=0*1(0+10*1)*
3. Obtain minimized finite automata for the R.E (b/a)*baa. May/June 2012s
4. Prove that there exists an NFA with €- transition that accepts the regular expression r.
May/June 2012
5. Which of the following language is regular? Justify. May/June 2012
i. L={ anbm/n,m>0}
ii. L={ anbn/n,>0}

6. Obtain the regular expression for the finite automata. May/June 2012

7. i. Using pumping lemma for the regular sets, prove that the language L={ambn/m>n} is not
regular.
ii. Prove any two closure properties of regular languages. Nov/Dec 2012
8. Construct a minimized DFA from R.E 0*(01)(0/111)*. C Nov/Dec 2012
9. Discuss on the relation between DFA and minimal DFA May/June 2013
10. i. Discuss on regular expression. May/June 2013
ii. Discuss in detail about the closure properties of regular languages.
11. Prove that the following languages are not regular May/June 2013
i. {02n/n>0}
ii. {ambnam+n/m>0and n>0} Nov/Dec 2013
12. Discuss on equivalence and minimization of automata. May/June 2013
13. Convert the following NFA into a R.E Nov/Dec 2013

14. i. Design a FA for the R.E (0+1)*(00+11)(0+1*) May/June 2014 ii. Prove
2
that L={0 i / i is an integer; i>0} is not regular. An
Nov/Dec 2014, 2015
15. Prove that the class of regular sets is closed under complementation.
May/June 2014
16. Construct a minimized DFA for the RE 10+(0+11)0*1. Nov/Dec 2014
17. Explain the DFA minimization algorithm with an example. Nov/Dec 2014
18. Find the min- state DFA for (0+1)*10. April/May 2015
19. Find the regular expression of a language that consists of set of strings with 11 as well
as ends with 00 using Rij formula. April/May 2015
20. Construct FA equivalent to the regular expression(ab+a)*
Nov/Dec 2015
21. What is Regular Expression? Write a regular expression for set of strings that consists of
alternating 0's and 1's. May-June2016

22. Minimize the FA shown in fig below and show both the given and the reduced one are
equivalent. May/June 2014

23. Write and explain the algorithm for minimization of a DFA. Using the above
algorithm minimize the following DFA. A May-June2016

24. Construct NFA with epsilon for the R.E=(a/b)*ab and convert into DFA and further find
the minimized DFA. C May-June 2017
25. Show that the regular language are closed under : E Nov-Dec2017
o Union
o Intersection
o Kleen closure
o Complement
o Difference
26. Minimize the following automaton E Nov-Dec 2018

27. Construct RE for C Nov-Dec 2019

28. Prove that any language accepted by a DFA can be represented by regular expression.
Nov-Dec 2019
29. Construct a finite automata for the RE 10+(0+11)0*1 Nov-Dec 2019

30. Prove that the following languages are not regular: E Nov-Dec 2019
r
i. {w€{a,b}*/w=w }
ii. Set of string of 0‘s and 1‘s beginning with a 1, whose value treated as binary
number is a prime.

UNIT III

CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA

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

1. Define CFG .Give an example. Nov-Dec 2016

2. What is CFL? May/June 2013

3. What is derivation?

4. What are the 2 types of derivation?

5. What is parse tree (or) derivation tree?
6. What is ambiguous grammar? Or When do you say grammar is ambiguous?
Nov/Dec 2012,2019, May/June 2013 , May/June 2014 & Nov/Dec 2022

7. For the grammar defined by the productions recognize the string 1001 and also
construct the parse tree.

8. Consider the alphabet Σ = { a,b,(,),+,*,-, . ,ξ }. Construct a CFG that generate all the
strings in Σ* that are regular expression on the alphabet, Σ. C
Nov/Dec 2007

S for the following grammar.

9. Find LMD & RMD, parse tree May/June 2007
 10. Define sentential form

11. Let G = ( {S,C}, {a,b}, P,S} where P consists of S  aCa, C aCa, Find L(G))?
12. Write a grammar to recognize all prefix expressions involving all binary arithmetic
operators. Construct the parse tree for the sentence “-*+abc/de” from your grammar.
Nov/Dec 2006

13. Write the CFG for the following CFL L(G) = { / m+n=p, m&n>1}
Nov/Dec 2006
14. Let G = ( {S,C}, {a,b}, P,S} where P consists of S  aCa, C aCa, Find L(G))?

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

P={S->aSb, S->ab}?
16. If S->aSb | aAb , A->bAa , A->ba .Find out the CFL

17. What are the properties of the CFL generated by a CFG?

18. Find the grammar for the language L={a2n bc ,where n>1 }
19. Find the language generated by :S->0S1 | 0A | 0 |1B | 1

20. Construct the grammar for the language L={ an b an | n>=1}.

21. Construct a grammar for the language L which has all the strings which are all palindrome
over _={a, b}. May/June 2014 , Nov/Dec 2015

22. Differentiate sentences Vs sentential forms.

23. What is a formal language?

24. What is Backus-Naur Form(BNF)?

25. Give the general forms of CNF. (Or) State CNF. R Nov/Dec 2014, Nov-Dec 2016
26. Construct the CFG for the language. L(G) = { / n > 1} C Nov/Dec 2013

27. What is meant by GNF? May/June 2013

28. Is the grammar ambiguous SSS/(S)/S(S)S/ ξ? Nov/Dec 2011

29. 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/Dec 2011

30. Generate CFG for (011+1)* April/May2015

SAB/BA/
ξ A1
B011
31. Construct a parse tree of (a+b)*c for the grammar EE+E/E*E/(E)/id
April/May2015
32. What do you mean by null production and unit production? Give an example.
 May-June 2016
33. Construct a CFG fro set of strings that contain equal number of a's and b's over
∑={a,b}. C May- June 2016
S  aSbS | bSaS | ε
34. Give language of regular expression a(b+c)*. May- June 2017

35. Generate CFG for a signed integer constant in C language. May- June 2017
36. Derive the string “aabaab” for the following CFG Nov/Dec 2017
SaSX/b
XXb/a

SaSXaaSXXaabXXaabaXaabaXbaabaab

37. Define PDA. May-June2016,Nov-Dec 2019

38. Draw PDA accepting the language L= { ancbn/n>0} Nov/Dec 2022

39. Construct a PDA that accepts the language generated by the grammer S →

aSbb

S → aab

40. What are the different ways of language acceptance by a PDA and define them?
. Nov/Dec 2012 ,April/May2015, Nov/Dec 2015

41. Define the language accepted by final state in PDA.

42. How do you covert CFG to PDA.

43. Define Deterministic PDA. Nov-Dec 2016

44. Is it true that non – deterministic PDA is more powerful that deterministic
PDA?Justify?
45. What is the additional feature PDA has when compared with NFA?Is PDA
superior over NFA in the sense of language acceptance? justify? (Or)
Compare NFA & PDA. Nov/Dec 2013

46. Does a Push down Automata have memory? Justify. May-June2016

47. What are the conventional notations of PDA? Nov-Dec2016

48. Construct a RMD of (a+b)*c using the grammar and also state that whether a given
grammar is ambiguous or not. May- June 2017
EE+E
 EE*E
E(E)
Ea|b| c

49. Differentiate PDA acceptance by empty stack with acceptance by final state.
May- June 2017

50. What is an instantaneous description of PDA? - Nov-Dec 2018

51. When pushdown automata is said to be deterministic?

PART-B

1. What is deterministic PDA? Explain with an example. Nov/Dec 2010

2. Is NPDA and DPDA equivalent? Illustrate with an example. Nov/Dec 2011
3. (i) Construct the PDA for the Language L= {WCWR | W is in (0+1)*.
Nov/Dec 2010, May/June 2012, Nov/Dec 2013
(i) Let L is a context free language. Prove that there exists a PDA that accepts L.
4. Construct the PDA accepting the language { (ab)n/n>0} by empty stack.
Nov/Dec 2012
5. a. Construct a transition table for PDA which accepts the language L={ (a2nbn/n>0}
Trace your PDA for the input with n=3. Nov/Dec 2012
b. Find the PDA equivalent to the give CFG with the following productions.
SA ABC Bba Cac
6. Construct PDA for the Language L= {WWR | W is in (a+b)*}.
May/June 2013 & 2016
n n
7. Construct the PDA accepting the language L= { a b /n>0} by empty stack and final state.
May/June 2014
8. Convert the grammar S0S1/A: A1A0/S/ ε into PDA that accepts the same language
by empty stack. Check whether 0101 belongs to N(M). May/June 2014
9. Prove that If L is N(M1) (the language accepted by empty stack) for some PDA M1, then L
is N(M2) (the language accepted by final state) for some PDA M2.
Nov/Dec 2014,2019
10. What are the different types of language acceptances by a PDA and define them. Is it true
that the language accepted by PDA by these different types provides different languages?
Nov/Dec 2011
11. Convert the grammar SaSb/A, AbSa/S/ε to PDA that accepts the same language by
empty stack. Nov/Dec 2011
12. Discuss the equivalence between PDA and CFG.
May/June 2012, May/June 2013, Nov/Dec 2013, May/June 2014

13. Construct a PDA for the language L={x€{a,b}*/ na(x)>nb(x)} April/May 2015

14. Convert the following CFG to a PDA. Nov/Dec 2015

SaAA, AaS|bS|a
15.Design a PDA to accept {0n1n|n>1}. Draw the transition diagram for the PDA. Show by
instantaneous description that the PDA accepts the strings‘0011‘. CNov/Dec 2015
16.Convert PDA to CFG.PDA is given by P=({p,q},{0,1},{X,Z}, δ,q,Z), δ is defined by
δ(p,1,Z)={(p,XZ)}, δ(p, ε,Z)={(p, ε)}, δ(p,1,X)={(p,XX)}, δ(q,1,X)={(q, ε,)},
δ(p,0,X)={(q,X)}, δ(q,0,Z)={(p,Z)}. Nov/Dec 2015
17. What are deterministic PDA‘s? Give example for non-deterministic and deterministic PDA.
Nov/Dec 2015
18. What is an instantaneous description that the PDA? How will you represent it? Also give
three important principles of ID and their transactions. May-June2016
19. Explain acceptance by final state and acceptance by empty stack of a Push down Automata.
May-June2016
20. Outline an ID of a PDA. Nov-Dec2016
21. With an example, explain the procedure to obtain a PDA from the given CFG.
Nov-Dec2016
22. Construct a DPDA for even length palindrome. May- June 2017
23. Prove ―If PDA P is constructed from CFG G by the above construction, then N(P)=L(G)‖.
May- June 2017
24. Convert the CFG to PDA and Verify for (a+b) and a++ May- June 2017
Ia/b/Ia/Ib/I0/I1
EI/E+E/E*E/(E)
25. Find PDA that accept the given CFG May- June 2017
SXaaX
XaX/bX/ ε
26. Construct PDA for the language anbman+m. May- June 2017
27. Prove that deterministic and non-deterministic PDA are not equivalent.
May- June 2017
28. a. Write a grammar G to recognize all prefix expressions involving all binary arithmetic
operator. Construct a parse tree for the sentence ‗-*+abc/de‘ using G. C

b. Show that the grammar G is ambiguous SSbS/a May/June 2014

c. Construct a CFG for{0m1n/1  m  n} Nov/Dec 2014

29. Explain about parse tree. For the following grammar. May/June 2013

For the string aaabbabbba, Find i. LMD ii. RMD iii. Parse tree Nov/Dec 2015

30. a. Is the grammar EE+E/E*E/id is ambiguous? Justify your answer.

b. Find the CFL for the following grammars May/June 2012

31. If SaSb/aAb, AbAa/ba is CFG. Determine CFL Nov/Dec 2011

32. Let G=(V,T,P,S) be a CFG then prove that if the recursive inference procedure tells us that
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
33. Given the Grammar G=(V,∑, R,E), Where
V= {E,D,1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)}
∑={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
34. What is ambiguous grammar? Explain with an example.
Nov/Dec2015, May-June2016
35. Show the derivation steps and construct derivation tree for the string ababbb' by using left
most derivation with the grammar. May-June2016
S —> AB / ξ, A—> aB, B—> Sb
36. Construct a CFG for the regular expression (011+1) (01). May-June2016
37. Construct CFG for the language L={an/n is odd} Nov-Dec2016

38. Define derivation tree. Explain its uses with an example. Nov-Dec2016

39. Construct a CFG to generate even and odd set of palindrome over alphabet {a,b}.
Nov-Dec2017
40. Generate CFG for the language L={0i1j0k/j>i+k} Nov-Dec2017
41. Show that the following grammar is ambiguous: SSbS/a. Nov-Dec 2018

42. Convert the CFG to PDA : SaS/bS/a/b Nov-Dec 2018

43. What is DPDA? Comment on the language accepting capabilities of DPDA.
Nov-Dec 2018
44. Give the regular expression of the language generated by the CFG given
below: S aS/bS/a/b. Convert the RE to E-NFA
45. Convert the PDA to CFG Nov-Dec 2018
 UNIT IV

NORMAL FORMS AND TURING MACHINES

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).

PART A

1. What are the three ways to simplify a context free grammar?

2. What are the closure properties of CFG? Nov/Dec 2017

3. State the pumping lemma for CFL.R

May/June 2012, Nov/Dec 2012, May/June 2014, April/May2015
4. Give the steps to eliminate useless symbols. Nov/Dec 2017
5. Show that CFLs are closed under substitutions Nov/Dec 2014
6. Show that L={ap/ P is prime } is not context free. Nov/Dec 2017
7. List the closure properties of CFL.

8. Define Turing Machine. Nov/Dec 2010,2015& 2017 , May/June 2014 & 2016
9. What are the required fields of an instantaneous description or configuration of a TM?
Nov-Dec2016
10. What is multiple tracks Turing machine?

11. What is multidimensional Turing machine?

12. When is a function f said to be Turing computable?

13. What is off line Turing machine?

14. List out the different techniques for TM construction. R Nov/Dec 2013

15. What is Universal Turing machine? Nov/Dec 2013, 2016

16. Define multitape TM. Nov/Dec 2014, Nov/Dec 2015

17.List the primary objectives of TM. R Nov-Dec2016

18. What are the differences between a Finite automata and a Turing machine? A
May-June2103

19.What is halting problem. May-June2107

20.Write short note on chomskian hierarchy of languages.

 May-June2107 Nov/Dec 2018

21. Give the configuration of Turing Machine. Nov/Dec 2017

22.Differentiate multihead and multi tape Turing machine. Nov/Dec 2018

23.What are the advantages of having a normal form for a grammar?

Nov/Dec 2019, Nov/Dec 2022

24.Define the language recognized by the TM. Nov/Dec 2019

25. When do you say a TM is an algorithm? Nov/Dec 2019

PART B
n n n
1. Is the language L = {a b c | n>=1} is context free? Justify. AN Nov/Dec 2010
(Or) Show that the Language L={ a i b i c i/ i  1} is not context free. A May/June 2014

2. Discuss the closure properties of CFL. U Nov/Dec 2010,May/June 2012, Nov/Dec

2012, May/June 2013
3. Show that language {0n1n2n/n>=1} is not CFL. A Nov/Dec 2014& Nov/Dec 2015
4. State the pumping lemma for CFL. Use pumping lemma to show that the language L=
{aibjck/i<j<k} is not a CFL. A May-June2016
5. State and explain the pumping Lemma for CFG. U Nov-Dec2016
6. Explain pumping Lemma for CFL. U May- June 2017
7. Convert the following grammar into GNF A Nov/Dec 2013
SXY1/0, X00X/Y,Y1X1
8. Construct the following grammar in CNF

9. Construct the following grammar in CNF Nov/Dec 2012

10. Find GNF for the grammar May/June 2012

11. Construct a equivalent grammar G in CNF for the grammar G1 where G1=({S,A,B}, {a,b},
{ SASB/£, AaAS/a, BSbS/A/bb},S). Nov/Dec 2015

12. Given the CFG G, find CFG G‘ in CNF generating the language L(G)-{^}
SAACD
AaAb/^
 CaC/a
DaDa/bDb/^ April/May 2015
13. Construct a reduced grammar equivalent to the grammar G = (N, T, P, S) where,
N = {S. A, C, D, E} T= {a, b}
P = { S —> aAa, A —> Sb, A —> bCC, A —> DaA, C —> abb. C —> DD, E
aC, D —> aDA}. May-June2016
14. What is the purpose of normalization? Construct the CNF and GNF for the following
grammar and explain the steps. May-June2016

15. Obtain a Grammar in CNF Nov-Dec2016

16. Given the CFG G, find CFG G‘ in CNF generaring the language L(G)- { ξ}
SAACD May- June 2017
AaAb\ ξ
CaC\a
DaDa\bDb\ ξ
17. Convert the following grammar G into Greibach Normal Form SXA\
BB May- June 2017
Bb\SB
Xb, Aa
18. Find an equivalent grammar in CNF for the grammar:
SbA/aB Nov-Dec2017
AbAA/aS/a BaBB/bS/b
19. Eliminate the unit production of the following grammar
SA/bb Nov-Dec2017
AB/b
BS/a
20. Design a TM that accepts the language of odd integers written in binary.
Nov/Dec 2011
21. What are the applications of TM. Nov/Dec 2012
n n
22. Construct the Turing machine for the language L = {0 1 |n >=1 } C
Nov/Dec 2010
23. i. Explain the difference between tractable and intractable problems with examples. A
ii. What is halting problem? Explain. Nov/Dec 2010, Nov/Dec 2015
24. i. State the techniques for TM construction. Illustrate with a simple language.U
ii. Explain the different models of TM. Nov/Dec 2011
25. State the halting problem of TMs. Prove that the halting problem of TM over {0,1}* as
unsolvable. Nov/Dec 2011
26. Explain any two higher level techniques for TM construction.May/June 2012
27. Construct the Turing machine for the language L = {1n0 n 1 n |n >=1 } C
May/June 2012
28. a. Design TM which reverses the given string {abb}. Nov/Dec 2012
b. Write briefly about the programming techniques for TM. May/June 2013
29. Explain TM as a computer of integer functions with an example. Nov/Dec 2013
30. Write short notes on the following: Nov/Dec 2013
a. Two way infinite tape TM
b. Multiple tracks TM
31. a. Design a TM to accept the language L0 n 1 n /n>=1} and stimulate its action on the input
0011. May/June 2014, Nov/Dec 2015
b. Write shot note on checking off symbols.
32. Design a TM, M to implement the function ―multiplication‖ using the subroutine ―copy‖.
Nov/Dec 2014
33. Construct TM to perform copy operation. April/May 2015
34. Explain the programming techniques for TM construction. Nov/Dec 2015,2016
35. Describe the Chomsky hierarchy of languages. Nov/Dec 2015&2017 , May- June 2017
36. Construct a Turing Machine to accept palindromes. Trace the string "abab" and "baab".
May-June2016
37. Explain the variations of Turing Machine. May-June2016
38. Explain Halting problem. Is it solvable or unsolvable problem? Discuss.
39. Describe the Chomsky hierarchy of languages with example. What are the devices
that accept these languages?
40. Write about Multi-tape TM. Nov-Dec2016
41. Highlight the implications of halting problems. Nov-Dec2016
42. Construct a TM to reverse the given string. May-June2107
43. Explain Multi tape and Multi head Turing machine with suitable example.
May-June2107
44. Construct TM that replace all occurrence of 111 by 101 from sequence of 0‘s and 1‘s.
Nov-Dec2017
45. Explain techniques for TM construction. Nov-Dec2017
46. Prove that Halting problem is undecidable. Nov-Dec2017
47. Consider two tape TM and determine whether the TM always write 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. Nov-Dec2017
48. Simply the following grammar by eliminating null productions, unit production and
useless symbols and then convert to CNF. Nov-Dec2018
SABC/BaB
AaA/ BaC/aaa
 BbBb/a/D
CCA/AC
D ξ
52. Convert the following grammar G into Greibach Normal Form
SAB, ABS/b, BSA/a Nov-Dec2018

53. Prove that the language L={anbncn/n>=1} is not context free using pumping lemma
Nov-Dec2018
54. Give the five tuple representation of a TM and explain the representation. Define
the language accepted by a TM. U Nov-Dec2018
55. Design TM that accepts the language L={SS/ S is in {a,b}* Nov-Dec2018

56. Design TM for L={anbncn/n>=1} Nov-Dec2018

57. Suppose L=L(G) for some CFG G=(V<T<P<S) then prove that L-{ ξ } is L(G‘) for CFG G‘
with no useless symbols or ξ- production. Nov-Dec2019
58. State and prove GNF. E Nov-Dec2019
59. Design TM to compute proper subtraction. Nov-Dec2019

UNIT V UNDECIDABILITY

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.

PART A
1. When a language is said to be recursively enumerable? Nov/Dec 2010, May/June
2012, Nov/Dec 2012, May/June 2013, Nov/Dec 2013,May/June 2014,
April/May2015

2. Define Non Recursive language. Nov/Dec. 2022

3. When a language is said to be recursive?

4. Define decidable problems.
5. Define undecidable problems.
6. Define universal language.

7. Define problem solvable in polynomial time.

8. Define the class P and NP. R May/June 2013, 2014 & Nov-Dec 2019

9. Define NP – Complete Problem. Nov-Dec2016

10. Write the Significance of NP-Complete Problem. Nov-Dec2022

11. What are tractable problems? Nov-Dec2017 W

12. hat are the properties of recursively enumerable sets which are undecidable?
13. What are the properties of recursive and recursively enumerable language?
Nov-Dec2017
14. Mention the difference between decidable and undecidable problems.
Nov/Dec 2010

15. Show that any PSPACE-hard language is also NP-hard. Nov/Dec 2010
16. Mention the difference between P and NP problems. May/June 2012

17. When we say a problem is decidable? Give example of undecidable problem.

Nov/DEC 2012, Nov/Dec 2015

18. Give examples for NP – Complete Problem. Nov/Dec 2014

19. Differentiate Recursive and Non-recursive language. April/May2015

20. When is a Recursively Enumerable language said to be Recursive?

May-June2016

21. Identify whether 'Tower of Hanoi' problem is tractable or intractable. Justify your
answer. May-June2016

22. What is primitive recursive function? May-June2107

Define the primitive recursion operation. Nov-Dec 2018
23. Define NP completeness. May-June2107
PART B
1. Prove that ‗If ‗L‘ is a recursive language, then L‘ is also a Recursive Language‘.
2. Prove that ‗If a language L and L‘ are recursively enumerable (RE) , then L is
Recursive‘.
3. Prove that (i) Lu is recursively enumerable but not recursive.
(ii) Non empty language Lne is recursively enumerable.
4. Find the languages obtained from the following operations:
(i) Union of two recursive languages. (6) Nov/Dec 2014
(ii) Union of two recursively enumerable languages (6)
(iii) L if L and complement of L are recursively enumerable (4)
5. a) Show that the following language is not decidable. L={<M>|
M is a TM that accepts the string aaab}. (8)
b) Discuss the properties of Recursive and Recursive enumerable
languages. (8)
6. Prove that the universal language Lu is recursively enumerable.
May/June 2014 , Nov/Dec 2014, Nov/ Dec 2015
7. Define the universal language and show that it is recursively enumerable
but not recursive.
8. Whether the problem of determining given recursively enumerable
language is empty or not? Is decidable? Justify your answer.
 9. Define Universal language Lu. Show that Lu is recursively enumerable but not
recursive.
10. Explain the Halting problem. Is it decidable or undecidable problem?
Nov/DEC 2011 , Nov/Dec 2012
11. Explain the difference between tractable and intractable problems with examples.
Nov/Dec 2010
12. Write short notes on: i. Recursive and recursively enumerable language
ii. NP hard and NP complete Problems Nov/Dec 2011
13. Discuss the properties of recursive languages. May/June 2012
14. Explain any two undecidable problems with respect to TM.
May/June 2012 , May/June 2013
15. Discuss the difference between NP-complete and NP-hard problems. May/June 2012

16. Write note on NP problems. Nov/Dec 2012, Nov/Dec 2013

17. Explain about ―A language that is not Recursively Enumerable‖.
May/June 2013
18. Prove that for two recursive language L1 and L2 their union and intersection is
recursive. Nov/Dec 2013.
19. Explain post correspondence problems and decidable and undecidable problems with
examples. April/May 2015
20. Explain the class P and NP problems with suitable example. April/May 2015
21. Prove that ―MPCP reduce to PCP‖. Nov/Dec 2015
22. Discuss about the tractable and intractable problems. Nov/Dec 2015
23. State and explain RICE theorem. Nov/Dec 2015
24. Describe about Recursive and Recursively Enumerable languages with examples.
Nov/Dec 2015
25. What is Universal Turing Machine? Bring out its significance. Also construct a TM to
add two numbers and encode it. May-June 2016
26. What is post correspondence problem (PCP) Explain with the help of an
example. May-June 2016, Nov-Dec2018
27. Elaborate on primitive recursive functions with an example. Nov-Dec2016
28. Compare recursive language with recursively enumerable languages.
Nov-Dec2016
29. What are tractable problems? Compare with intractable problems.
Nov-Dec2016
30.Outline the concept of polynomial time reductions. Nov-Dec2016
31. Explain recursive and recursively enumerable languages with suitable
example.
May-June2107
32. Explain tractable and intractable problem with suitable example.
May-June2107
33.Explain universal TM. Nov-Dec2017
34.Explain how to measure and classify complexity. Nov-Dec2017
35.If L and its complement are recursively enumerable language, prove that L is
recursive. E Nov-Dec 2018