R.M.K.

ENGINEERING COLLEGE
RSM Nagar, Kavaraipettai – 601 206

Question Bank for the Units – I,II,III,IV & V

SE00 5rd Semester – B.E. / B.Tech.

BR00 Computer Science and Engineering

SU00 CS6503 – Theory of computation

Part-A (10 x 2 = 20 Marks)

1. Define Deductive Proof .

1. Differentiate Proof by contradiction and proof by contra positive.

1. Enumerate the difference between DFA and NFA.

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

1. Define epsilon closure.

2. State regular expression. What are the operators of Regular Expression?

2. Write down the relationship between FA and regular expression.

2. Write regular expression for the language accepting the strings which are starting with 1and
ending with 0, over the set  = {0,1}.

2. State the pumping lemma for regular languages.

3. Define Context Free Grammar and its components.

3. Find CFG for the L = { 0n1n / n>=1}

3. Find the LMD and Parse tree for the string w =aabbbb
S  AB A  aAA | aA | a B  bBB | bB | b .

3. Define Ambiguous Grammar with an example.

3. Define the sentential form and it types.

4. Write the procedure to eliminate the unit productions.

4. Define generating symbol and reachable symbol

4. How do you simplify the context free grammar?

4. Define Chomsky Normal Form

4. Define Greibach Normal Form.

5. Define pushdown Automaton.

5. What are the different ways of language acceptances by a PDA and Define them.

5. Define Deterministic PDA.

5. Is it true that Non deterministic PDA is more powerful than that of Deterministic PDA. Justify.

5. What is the additional feature a PDA has when compared with NFA?Is PDA superior over NFA in the
sense of language acceptance? Justify your answer.

6. What is meant by Equivalence of PDA and CFG?

6. Define the rule for construction of PDA from given CFG .

6. State the pumping lemma for CFL’s?

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

7. Define a Turing machine.

7. Define Instantaneous description of Turing machine.

7. Define the language of Turing machine.

7. Is it possible that a Turing machine could be considered as a computer of functions from integers to
integers? If yes justify.

7. Compare FA, PDA and TM.

8. What is meant by Partial function?

8. Differentiate multitape and multitrack Turing machine.

8. Define Halting Problem.

8. Define Chomsky Hierarchy.

8. Differentiate Decidable and Undecidable Language?

9. Define PCP and MPCP.

9. Define diagonal language.

9. What is meant by Primitive recursive functions ?

9. Define countable and Uncountable sets.

9. Differentiate Recursive and recursively enumerable languages

10. Define Universal Turing machine.

10. What is meant by Tractable Problem and Intractable problems ?

10. What are Class P and Class NP Problems?

10. Give examples for NP problems.

10. Define COOK'S theorem.

Part – B ( 5 x 13 = 65 Marks)

11.a. (i) Prove that all Natural numbers of the form 23n – 1 is divisible by 7 using Principle
of Induction. (6)
(ii) Give Deterministic finite automata accepting the following language over the
alphabet(0,1) (7)
1. Number of l's is a multiple of 3
2.Number of l's is not a multiple of 3

11.a. (i) Show that 1+2+3+……….+n = n(n+1)/2 by mathematical induction. (5)

(ii) Construct an NFA for the set of strings with {0,1} ending with 01 and draw the transition table
for the same and check whether the input string 00101 is accepted by NFA. (8)

11.a. (i) Prove that the language ‘L’ is accepted by some DFA if and only if ‘L’ is accepted by some NFA.(6)
(ii) Convert the following NFA to DFA. (7)

11.a. Consider the following Finite automata (13)

ε a b c d

q0 {q1} Φ Φ Φ Φ

q1 Φ { q1,q2} {q3} Φ Φ

q2 {q3} Φ Φ { q2 } { q2}

*q3 Φ { q3} {q3} Φ Φ

 a) Compute the ε-closure of each state.
b) Convert the above ε –NFA to DFA.

11.a. (i) Prove the following by the principle of induction,

12+22+32+……….+n2 = n(n+1)(2n+1) /6 (5)
(ii) Convert the following NFA to it’s equivalent DFA.
(8) Inputs

States 0 1

p {p,q} {p}

q {r} {r}

r {s} ф

*s {s} {s}

11.b. Find the regular expression for the set of all strings denoted by R 13 from the deterministic
finite automata given below: (13)

11.b. (i) Prove that if there is a Regular Expression R, then there is a NFA with ε transition M,
Such that L(M) = L(R). (7)
(ii)What is regular expression? Write a regular expression for the language L which
accepts all the strings which begin or end with either 00 or 11. (6)

11.b. (i)Consider the following finite Automata and find the equivalence and minimized state (7)
equivalent DFA.
Inputs
States 0 1
A B A
B A C
D B
C
D A
*D
D F
E
G E
F
F G
G
G D
 (ii) Construct an NFA equivalent to the regular expression ((0+1)(0+1)(0+1))*. (6)

11.b. (i) Construct a minimal state DFA. (7)

Inputs
States 0 1
A B E
B C F
D G
*C
E H
D
F I
E
G B
*F
H B
G
I C
H
A E
*I

(ii) Check whether the language L= {ap/ p is prime} is regular or not? Justify your answer. (6)

11.b. (i) Find the regular expression corresponding to the finite automaton given below. (8)

Inputs
States 0 1

q1 {q2} {q1}

*q2 {q2} {q2}

 (ii) Check whether the language L={0n1n/n>=1}is regular or not? Justify your answer. (5)

12.a. (i) Let G be a grammar S0B/1A, A0/0S/1AA, B1/1S/0BB. For the string (8)
00110101 find its leftmost and rightmost derivation and also construct derivation tree.
(ii) Construct the context-free grammar representing the set of palindromes over (0+1) *. (5)

12.a. (i) Prove that if there is a parse tree for the grammar G that has ‘w’ as its yield of the parse tree, then
there exist a left most derivation for the same grammar G such that A ==> w. (8)

(ii) For the grammar G is defined by the productions S  A1B A  0A / ε

B  0B /1B / ε . Find the Parse tree for the Yield 1001. (5)

12.a. (i) The following grammar generates prefix expressions with operands x and y and binary (7)
operators +,- and * and the grammar is as follows, E  +EE / *EE / -EE / x / y
(a) Find the leftmost and rightmost derivation and derivation tree for the string “+*-xyxy “
(b) Prove that this grammar is Unambiguous.
(ii) Construct a CFG for the language L= {wcw R / w is a string in (a+b)*}. (6)

12.a. (i) Derive the string b*(b+a11) using leftmost and rightmost derivation for the following (6)
production E  I / E + E / E * E / ( E ) I a / b / Ia / Ib / I0 / I1
(ii) Define Ambiguous grammar. Check whether the following grammar is ambiguous or not. (7)

S  aSbS / bSaS / ε

12.a. (i) Define ambiguity. Show that the grammar is ambiguous. S  a / abSb /aAB AbS / aAAb. (8)
(ii) For the grammar G is defined by the productions E  E + E / E * E / (E) / a.
Find the Parse tree for the Yield (a+a)*(a+a). (5)

12.b. Consider the following grammar and eliminate useless symbols, ε-productions,
unit production and find CNF. (13)
S0A0 / 1B1 / BB , A C , B S / A , CS / ε

12.b. (i) Construct a equivalent grammar G in CNF for the grammar G1

where G1 =({S,A,B},{a,b},{ SbA / aB, AbAA / aS / a , BaBB / bS / b }, S) (7)
(ii) Find a Context free grammar with no useless symbol equivalent to

SAB/CA, BBC/AB, Aa, CaB/b (6)

12.b. (i) Find CNF for the following grammar, S aAD A aB / bAB B b D  d (8)
(ii) Eliminate ε-production for the following grammar G, SCD CcCC / ε DdDD / ε (5)

12.b. Convert the following Grammar into Chomsky Normal Form (13)
 S aAa / bBb / ε

AC / a

BC / b

CCDE / ε

DA / B /ab

12.b. (i)Find a grammar in chomsky normal form equivalent to

SaAbB AaA / a BbB / b (8)
(ii) Eliminate unit production for the grammar SAB / A AB Ba /ab /d (5)

13.a. (i) Prove that if there exists a PDA that accepts by empty stack than there exists an equivalent PDA
that accept by final state. (6)
(ii)Construct a PDA for the language L= { wwR / w is in (0 + 1)*}}.Find the instantaneous
description for the string “0110”. (7)

13.a. (i) Construct a PDA to accept the language L={anbn+mcm / m,n>0 } by empty stack. (7)
3n n
(ii) Construct a PDA to accept the language L={ a b / n≥0}by final state. (6)

13.a. Construct a PDA PN that accepts the language L={ anbma2(n+m) / m≥1,n≥0}by empty stack .Convert it into
PF accepting by final state and show the string “abaaaa” in accepted by PDA(PF). (13)

13.a. (i) Prove that if there exists a PDA that accepts by final state than there exists an equivalent PDA
that accept by empty stack. (6)
(ii) Explain Deterministic Pushdown Automaton with example. (7)

13.a. (i) Construct a PDA to accept the language L={ a3nbn / n≥0}by final state. (7)

(ii) Construct a PDA to accept the language L={anbman / m,n>0 } by empty stack. (6)

13.b. (i) If L is context free Language Prove that there exists a PDA M,such that L=N(M). (6)
(ii) Construct the PDA for the grammar S->aB /bA , B->b /bS /aBB , A->a /aS /bAA .
Find Instantaneous description for the string bbaabba . (7)

13.b. (i) Construct the PDA for the grammar S->aB /bA , B->b /bS /aBB ,A->a /aS /bAA
Find Instantaneous description for the string bbaabba . (7)
(ii) Show that L={anbncn /n≥1} is not context free language. (6)

13.b. Convert the PDA P=({q0, q1},{a,b},{Z0,Z1},δ, q0, Z0 ) to a CFG, if δ is given by, (13)

δ(q0,b, Z0)={(q0,Z1 Z0)} δ(q0,a, Z1)={(q1, Z1)}

δ(q0 ,ε, Z0)={(q0, ε)} δ(q1, b, Z1)={(q1,ε)}

 δ(q0, b, Z1)={(q0, Z1 Z1)} δ(q1, a, Z0)={(q0, Z0)}

13.b. Convert the PDA P=({p, q},{0,1},{X,Z0},δ, q, Z0 ) to a CFG, if δ is given by, (13)

δ(q,1, z0)={(q,xz0)} δ(q,ε, z0)={(q,ε)}

δ(q,1, x)={(q,xx)} δ(p,1, x)={(p,ε)}

δ(q,0, x)={(p,x)} δ(p,0, z0)={(q,z0)}

13.b. (i) Let M=(Q, ,,,q0,Z0) be a PDA .Then there is a context free grammar G such that L(G)=N(M). (7)
(ii) Construct the PDA for the grammar S->aB /bA , B->b /bS /aBB ,A->a /aS /bAA . (6)

14.a. (i)Design a Turing machine to accept the language L={0 n1n /n≥1}and simulate its action on
the input 00111. (9)
(ii) Construct a Turing machine that accept strings over{1} containing even number of 1's. (4)

14.a. (i)Design a Turing machine to accept the language L={a nbn cn /n≥1}and simulate its action on
the input aabbcc. (9)
(ii) Construct a Turing machine to compute the function f:NN such that f(x)=x+2. (4)

14.a. Construct a Turing Machine to accept palindromes in an alpabet set ∑={a,b}.

Trace the string "abab" and "baab" (13)

14.a. (i) Design a TM for the language L: The set of strings with an equal number of 0's and 1's.
Find Instantaneous description for the string w=1010. (9)
(ii) Construct a Turing machine that accept all strings contains a substring aba. (4)

14.a. Explain in detail:” The Turing Machine as a Computer of integer functions”

for proper addition and subtraction (13)

14.b. Design a Turing machine M to implement the function "MULTIPLICATION" using the
subroutine copy. (13)

14.b. Write briefly about the programming techniques for TM. (13)

14.b. (i) Explain briefly Chomskian hierarchy of languages. (7)

(ii) Prove that the Accepts and Halts (Halting problem) are undecidable. (6)

14.b. Design a Turing Machine M for f(x, y) = x * y where x, y are stored in the tape in
the form 0X10Y1. (13)
14.b. (i) State the halting Problems of Turing machine. Prove that the halting problem of
Turing machine over {0, 1}* as unsolvable. (7)
(ii) Explain briefly Chomskian hierarchy of languages. (6)

15.a. (i) Explain about Undecidability of PCP. (7)

(ii) Show that If a language L and L' are Recursively Enumerable (RE),
then L is Recursive. (6)

15.a. (i) Describe about Recursive languages and Recursive Enumerable languages with example (7)
(ii) Prove that "MPCP reduces to PCP". (6)

15.a. (i) What is Post Correspondence Problem? Explain with the help of example. (7)
(ii)Prove Ld is not a Recursive Enumerable Language. (6)

15.b. (i) Explain Universal Turing machine. Show that Lu is RE but not recursive. (6)
(ii) Briefly discuss the Tractable and Intractable problems with examples (7)

15.b. Explain the class P and NP complete problem with examples. (13)

15.b. (i) Define COOK’S Theorem and prove that the language CNF – Satisfiable (7)
is NP – Complete.
(ii)Show that the 3-sat Problem is NP- Complete . (6)

Part – C ( 1 x 15 = 15 Marks)

16.a. Construct a minimized DFA for the RE (a +b)*abb. (15)

16.a. (i)Let G=(V,T,P,S) be a context free grammar then prove that if the recursive inference procedure
tells us that terminal string w is the language if variable A ,then there is a parse
tree with root A and yield w. (10)
(ii) Given the grammar G=(V,∑,R,E),where
V={E,D}
T={1,2,3,....,9, + , - , * , / , ( , ) } and R contains the following rules:
E D (E) E+E E-E E*E  E/E
D 0 1 2 .....9
Find the parse tree for the string 1+2*3. (5)

16.a. (i) Construct the context free grammar for the language L= {a i b jck / i,j, k≥ 0, i=2j or j=2k} use (10)
the above CFG to create PDA by empty stack.

(ii) Show that L={ / i is an integer, i>=1} is not context free language. (5)

16.a. (i) Design the Turing machine to compute the partial function that reverse the string{a,b}*->{b,a}*.(10)
(ii) Construct a Turing machine to compute the function f:NN such that f(x)=x+2. (5)

16.a. (i) Obtain code for the following Turing Machine (8)
M=({q1, q2, q3},{0,1},{0,1,B},δ, q1,B,{ q2}) where δ is given as
δ(q1,1)= (q3,0,R)
 δ(q3,0)= (q1,1,R)
δ(q3,1)= (q2,0,R)
δ(q3,B)= (q3,1,L)
(ii) Prove Ld is not a Recursive Enumerable Language. (7)

16.b. Construct a minimized DFA for the RE (01)*01. (15)

16.b. (i) Convert to Greibach Normal Form the grammar G= ({A1, A2, A3}, {a, b},P,A1 ) where P
consists of the following. A1A2 A3, A2 A3 A1 /b, A3A1 A2 /a. (11)
(ii) Explain how to eliminate ε-productions. (4)

16.b. Construct PDA to accept the language L= { wcwR / w is in (a + b)*}and use the transition
function of PDA to construct the CFG . (15)

16.b. (i) Consider a TM M=(q,{0,1},{0,1,B},,[q0,B],[q1,B]) that looks at the first input symbol,
records in the finite control and checks that the symbol does not appear elsewhere on its input. (9)
(ii) Prove that if there is a reduction from P1 to P2, then If P1 is undecidable,
then So is P2 (6)

16.b. (i) Discuss the concepts of Complexity classes. (7)

(ii) Define CNF-SAT Problem. Prove that For any given graph G,
and an integer ‘k’ does the graph ‘G’ has complete subgraph with k vertices? (8)