## 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^{n}10^{n} 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)