STUPIDSID
Solve any one question from Q1 and Q2
1 (a)
Write regular expressions for the following languages over the alphabet ∑ = {a, b}
i) All strings that do not end with 'aa'.
ii) All strings that contain an even number of 'b' s. iii) All strings which do not contain the substring 'ba'.
i) All strings that do not end with 'aa'.
ii) All strings that contain an even number of 'b' s. iii) All strings which do not contain the substring 'ba'.
6 M
1 (b)
Show that for two recursive languages L1 and L2, the language L is also
recursive, where L is given by L1 ∩L2.
4 M
2 (a)
Consider the following NFA with ∈ - transitions. Find ∈ - closures and then convert this into NFA without ∈ -moves.
6 M
2 (b)
Prove using mathematical induction the following:
20+21+22+....+2n=2n+1-1, for all integers n≥0.
20+21+22+....+2n=2n+1-1, for all integers n≥0.
4 M
Solve any one question from Q3 and Q4
3 (a)
Find the regular expression for the set of strings recognized by the given FA. Use Arden?s theorem.
6 M
3 (b)
Explain, with suitable examples, any two applications of context free
grammars.
4 M
4 (a)
Convert the following CFG into Chomksy Normal Form (CNF):
S-> AB
A -> CA | ^
B-> DB | ^
C-> 011 | 1
D-> 01
S-> AB
A -> CA | ^
B-> DB | ^
C-> 011 | 1
D-> 01
6 M
4 (b)
Prove the formula
i) (r * s*)* = (r + s)*.
ii) (ab)* z a* b*.
i) (r * s*)* = (r + s)*.
ii) (ab)* z a* b*.
4 M
Solve any one question from Q5 and Q6
5 (a)
Design Turing Machines for each of the following problems:
i) Given two unary numbers, m and n, display,
'G', if m>n, 'E', if m=n, 'L', if m ii) Given two unary numbers, find the Greatest Common Divisor (GCD) of the two numbers.
i) Given two unary numbers, m and n, display,
'G', if m>n, 'E', if m=n, 'L', if m
10 M
5 (b)
Justify how a Turing Machine can simulate a General Purpose computer
and vice-versa.
8 M
6 (a)
Explain : 'The halting problem in Turing Machines is undecidable'.
6 M
6 (b)
Design a Turing Machine to perform right shift operation on a binary
Number.
6 M
6 (c)
Design Post Machine to accept strings that belong to the language L, given by, L = {an b3n |n >= 0}.
6 M
Solve any one question from Q7 and Q8
7 (a)
Design PDA for language L={aibjck | i, j, k>1 and i+j=k} that accepts language via
i) Final state.
ii) Empty stack.
i) Final state.
ii) Empty stack.
10 M
7 (b)
Explain the equivalence of PDA with acceptance by final state and empty stack.
6 M
8 (a)
Write context free grammar for accepting palindrome strings (even and
odd). Also design PDA for the context free grammar.
8 M
8 (b)
Consider the PDA with following moves; obtain its equivalent CFG.
((q0, a, Z0) = (q0,aZ0),
(q0, a, a) = (q0, aa),
(q0, b, a) = (q1, ε),
(q1, b, a) = (q1, ε),
(q1, ε, Z0) = (q1, ε)
((q0, a, Z0) = (q0,aZ0),
(q0, a, a) = (q0, aa),
(q0, b, a) = (q1, ε),
(q1, b, a) = (q1, ε),
(q1, ε, Z0) = (q1, ε)
8 M
Solve any one question from Q9 and Q10
9 (a)
What do you mean by Polynomial-time reductions? Describe any problem
in detail that is solvable through polynomial time reduction.
8 M
9 (b)
What is Satisfiability (SAT) problem? Explain with a suitable example.
8 M
10 (a)
Explain the Vertex Cover problem in the context of polynomial-time
reductions. Justify with a suitable example.
8 M
10 (b)
Explain the following with example.
i) Computational complexity.
ii) 3-SAT problem.
i) Computational complexity.
ii) 3-SAT problem.
4 M
10 (c)
Differentiate between P-class problems and NP-class problems.
4 M
More question papers from Theory of Computation