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 ({q_{0}, q_{1}}, {0, 1}, {0, 1, z_{0}}, δ, q_{0}, z_{0}, ϕ) where δ is
δ (q_{0}, ∧, z_{0}) = (q_{0}, ∧)
δ (q_{0}, 0, z_{0}) = (q_{0}, 0, z_{0})
δ (q_{0}, 0, 0) = (q_{0}, 00)
δ (q_{0}, 1, 0) = (q_{0}, 10)
δ(q_{0}, 1, 1) = (q_{0}, 11)
δ (q_{0}, 0, 1) = q_{1}, ∧), δ (q_{11}, 0, 1) = (q_{1}, ∧)
δ (q_{1}, 0, 0) = (q_{1}, ∧)
δ (q_{1}, ∧, z_{0}) = (q^{1}, ∧)
obtain CFG accepted by the above PDA.
δ (q_{0}, ∧, z_{0}) = (q_{0}, ∧)
δ (q_{0}, 0, z_{0}) = (q_{0}, 0, z_{0})
δ (q_{0}, 0, 0) = (q_{0}, 00)
δ (q_{0}, 1, 0) = (q_{0}, 10)
δ(q_{0}, 1, 1) = (q_{0}, 11)
δ (q_{0}, 0, 1) = q_{1}, ∧), δ (q_{11}, 0, 1) = (q_{1}, ∧)
δ (q_{1}, 0, 0) = (q_{1}, ∧)
δ (q_{1}, ∧, z_{0}) = (q^{1}, ∧)
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={a^{n}b^{n+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 i_{1}, i_{2}, i_{3} ...., i_{m} for m ≥ 1 such that wi_{1}, wi_{2}, ....., wi_{m} = xi_{1}, xi_{2}, ...., xi_{m}.
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