 MORE IN Theory of Computation
SPPU Information Technology (Semester 5)
Theory of Computation
December 2015
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question from Q1 and Q2
1 (a) Design an FA for the languages that contain strings with next-to-last symbol O.
5 M
1 (b) Write formal definition of NFA - L. Also define L ? closure.
5 M

2 (a) Draw an FA recognizing the regular language corresponding to give regular expression
1(01 + 10)* + 0 (11 + 10)*
5 M
2 (b) Write a short note on the applications of Regular Expressions.
5 M

Solve any one question from Q3 and Q4
3 (a) State pumping Lemma for context - free languages. Also Define context - free language.
5 M
3 (b) Construct parse trees for the strings using specified derivation format for the given grammar G.G = ({S, A, B}, {a, b}, P, {S})
P = {S → a B | b A
A → a|aS | b AA
B → b | b S | a BB }
Strings:
i) aaabbb (rightmost derivation)
ii) aababb (leftmost derivation)
5 M

4 (a) Define
i) Ambiguous Grammar
ii) Regular Grammar with suitable example.
5 M
4 (b) Convert given CFG into Greibach Normal Form
S→ABA
A→aA|ε
B→ bB|ε
5 M

Solve any one question from Q5 and Q6
5 (a) Design a PDA which accepts only odd number of a's over ∑ = {a, b}. Simulate PDA for the string 'aabab'.
9 M
5 (b) Define PDA and Post machine with suitable example. Compare DPDA, NPDA and CFG.
9 M

6 (a) For the PDA ({q0, q1}, {0, 1}, {0, 1, z0}, δ, q0, z0, ϕ) where δ is
δ (q0, ∧, z0) = (q0, ∧)
δ (q0, 0, z0) = (q0, 0, z0)
δ (q0, 0, 0) = (q0, 00)
δ (q0, 1, 0) = (q0, 10)
δ(q0, 1, 1) = (q0, 11)
δ (q0, 0, 1) = q1, ∧), δ (q11, 0, 1) = (q1, ∧)
δ (q1, 0, 0) = (q1, ∧)
δ (q1, ∧, z0) = (q1, ∧)
obtain CFG accepted by the above PDA.
9 M
6 (b) Compare PDA and post machine. Design a post machine to accept the language L={anbn+1|n≥0}.
9 M

Solve any one question from Q7 and Q8
7 (a) Construct a TM for obtaining two's complement of a given binary number. Simulate TM for any string.
8 M
Write a short note on:
7 (b) (i) Multi - tape TM
4 M
7 (b) (ii) Universal TM
4 M

8 (a) Compare FM, PDA, PM and TM with respect to language, grammar, powerfulness and example.
8 M
8 (b) Design a Turing machine that accepts the language of all strings which contain 'aba' as a substring.
4 M
8 (c) Discuss categories of problems based on solvability with suitable example.
4 M

Solve any one question from Q9 and Q10
9 (a) Write a note on each of the following:
i) Recursively enumerable language.
ii) Recursive language.
iii) Recursive Functions.
iv) Partial Recursive function.
8 M
9 (b) Write a short note on Encoding of Turing Machine.
8 M

10 (a) Explain post-correspondence problem. Let ∑ = {0, 1} and let A & B defined as shown in the table. Find the post correspondence sequence of integers i1, i2, i3 ...., im for m ≥ 1 such that wi1, wi2, ....., wim = xi1, xi2, ...., xim.
 A B i wi xi 1 0 000 2 01000 01 3 01 1
8 M
10 (b) Define decidability of problem with suitable example. Describe undecidable problems for context-free Grammar.
8 M

More question papers from Theory of Computation