STUPIDSID
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)*
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)
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.
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|ε
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.
δ (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.
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