Theoretical Computer Science - Dec 2015

Computer Engineering (Semester 4)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1 (a) Consider the following grammer G={V, T, P, S}, V={S, X}, T{0, 1} and productions P are
S→0| 0X1 | 01S1
X→ 0XXI| 1S
S is start symbol. Show that above grammer is ambiguous.(5 marks) 1 (b) State and prove the halting problem.(5 marks) 1 (c) Convert following ε-NFA to NFA without ε. (5 marks) 1 (d) Prove that Language L={0ⁿ10ⁿ for n=0, 1, 2, ....} is not regular.(5 marks) 2 (a) Consider the following grammer G=(V, T, P, S), V={S, X, Y}, T{a, b} and productions P are
S→XYX
X→aX|ε
Y→bY|ε
Convert this grammer in Chomsky Normal Form (CNF).(10 marks) 2 (b) Design DPDA to acept language L={x∈{a, b}* | N_a(x)>N_b(x)}, N_a(x)>N_b(x) means number of a's are greater than number of b's in string x:(10 marks) 3 (a) Design Turing machine to accept the language L=set of string with equal number of a's and b's.(10 marks) 3 (b) Design the DFA to accept the language containing all the strings over ∑={a, b, c} that starts and ends with different symbols.(10 marks) 4 (a) Design Moore Machine for the input from (0+1+2)* which print the residue modulo 5 of the input treated as ternary number.(10 marks) 4 (b) State and prove pumping lemma for context free language.(10 marks) 5 (a) Convert the following grammer into finite automata.
S→aX | bY | a | b
X→aS | bY | b
Y→aX | bS.(5 marks) 5 (b) Compare recursive and recursively enumerable languages.(5 marks) 5 (c) State and prove Rice's theorem.(10 marks) 6 (a) Write regular expression for the following languages.
language containing all the string in which every pair of adjacent a's appears before any pair of adjacent b's, over the alphabet ∑{a, b}:
ii) language containing all the string in which all possible combination of a's and b's is present but strings does not have two consecutive a's, over the alphabet ∑{a, b}.(10 marks) 6 (b) Write short note on 'Unversal Turing Machine'.(5 marks) 6 (c) Explain variation and equivalences of Turing machine.(10 marks)