UNIT-3

1. Define Deterministic PDA.Is NPDA and DPDA equivalent? Illustrate with an example

2. Construct PDA for the Language L= {WWR| where W is in (a+b) *}.

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

4. Construct the Pushdown Automata accepting the language L= { aibjci+j | i,j>0}.

5. what are the different types of language accepted by a PDA and define them? Is it true
that the language accepted by these different types provides different language?

6. Examine whether the language L={a2n bn c2n |n>0} designed using PDA. Justify your
answer.

7. Explain ambiguous grammar check whether the grammar X--> X+X/X*X/X/a is

8. Construct PDA for the given CFG

E-> I /E*E / E+E / (E) / ID

I -> a/ b/ Ia/ Ib/ I0/ I1

9. i)Construct a transition table for PDA which accepts the language L={(a2nbn/n>0} Trace
your PDA for the input with n=3

ii) Find the PDA equivalent to the give CFG with the following productions.

S→A, A→BC, B→ba, C→ac

10. Consider the grammar,S → bB / aA,A → b / bS / aAA ,B → a / aS / bBB.For the string w

Find1. Leftmost derivation

2. Rightmost derivation

3. Parse Tree

11. Construct CFG from PDA where p=({ q0, q1},{a,b}, q0,{ q1},{z, z0}, δ, z0) and δ is
defined by

δ(q0,b,z0)={( q0,zz0)}, δ(q0, ε, z0)={( q0,ε)}

δ(q1,b,z)={( q1, ε)}, δ(q1, a, z0)={( q1, z0)}

12. How PDA is converted into CFG? Convert the following PDA into CFG P=({ p, q},
{0,1}, p,{Z, X},δ, Z) and δ is defined by

δ(p,1,Z)={( p,XZ)}, δ(p, e,Z)={( p,ε)},

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

δ(p,0,x)={( q,X)}, δ(q,0,Z)={( p, Z)}

13. Construct a PDA which should accept the language L={a^n b^n|n>=1} by using empty
stack.
14. Construct a CFG for the language L= {0m1n|1<=m<=n}.

UNIT-4
1. Describe the construction of a Turing Machine to recognize the language L = {0^n 1^n |
n ≥ 0}.
2. Convert the following CFG to Chomsky Normal Form (CNF):
S -> AB | aB
A -> aa | ε
B -> bb | ε
3. Construct a pushdown automaton (PDA) to recognize the language of palindromes
overthe alphabet {a,b}
4. Define Ld the diagonalization language. Explain the kind of strings Ld accepts. Prove
that Ld is not recuesively ennumerable.
5. Construct TM that replaces all occurences of 111 by 101 from sequences of 0's and 1's.
6. Construct the CFG for the language L = {an | n is odd }.

7. Construct CNF for a given grammar

S-> aA/ aBB

A-> aaA/ε
 B-> bB/ bbC

C->B

8. Design a Turing Machine that can perform mulitiplication of two binary numbers.

9. Convert the following CFG into GNF.

A1 -> A2A3

A2 -> A3A1 / b

A3 -> A1A2 / a

10. Consider a CFG for L is converted into CNF accepting the same Language. Convert the
following CFG into GNF.

S-> bA/ aB

A->bAA/ aS/ a

B-> aBB/ bS/ b

11. Convert PDA to CFG for the language L = {a^n b^m c^(n+m) | n, m ≥ 0}

12. Prove that CFL closed under union, concatenation, closure, positive closure, reversal and
homomorphism.

13. If G is a CFG whose language contains atleast one string other than ε, prove that there is
a grammar G1 in CNF that L(G1)={L(G) - ε}.

UNIT-5
1. Explain the Modified Post Correspondence Problem (MPCP) with an example.

2. State and Prove Halting problem.

3. Explain P and NP complete problems, with proper examples.

4. State and prove that “Diagonalization language is not recursively enumerable".

5. Construct PCP for the following.

Index A B

1. 1 111

2. 10111 10

3. 10 0
6. Demonstrate the logic of solving the travelling salesman problem, with example.

7. State whether the instances of the PCP has a solution. The following are the instances
with Σ = {0,1}.

Index List 1 List 2

1. 10 01

2. 110 011

3. 110 01

4. 000 00

5. 10 010
8. State the difference between recursive and recursively enumerable language.

9. Consider and find the languages obtained from the following operations:

i) Union of two recursive languages

ii) Union of two recursively enumerable languages

iii) L if L and complement of L are recursively enumerable

10. Find the minimum spanning tree for the following figure using kruskal’s algorithm.

11.

iv) How PCP is reduced to MPCP?

v) Expalin about 3 CNF SAT Problems.

12. Demonstrate on travelling salesman problem with suitable example.

13. Evaluate the solution for the following system PCP convert into Modified post
correspondence problem.
A B
i wi xi
1 1 111
2 10111 10
3 10 0

14. Let ∑ = {0,1} and A and B be the lists of three strings each.

15. Does PCP with two lists x=(b, bab3, ba) and y=(b3, ba, a), have a solution. Analyze your
answer