Theoretical Computer Science - May 2014

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) Differentiate between NFA and DFA.(5 marks) 1(b) Explain CNF and GNF with example.(5 marks) 1(c) state and prove closure properties of context free languages.(5 marks) 1(d) Give Applications of Regular Expression and finite Automata(5 marks) 2(a) Construct an NFA with epsilon transition for following RE.
(00+11)(10)(5 marks) 2(b) Give formal definition of regular expression.Give R>E for following:
Set of all strings over {1,0}that end with and has no substring 00.
Set of all strings over {1,0}with even number of 1's followed by odd number of 0's(5 marks) 2(c) Compare and Construct Moore and Melay Machine.Construct Moore Machine to find out the residue-modulo-3 for binary numbers.(10 marks) 3(a) Consider the following grammar:
S$\rightarrow$I C t S |I C t S e S|a
C$\rightarrow$b
For the string 'ibtibtaen find the following:
i)Leftmost derivation
ii)Rightmost derivation
iii)Parse tree
iv)Check if the above grammar is Ambiguous. (10 marks) 3(b) Design PDA that checks for well-formed parentheses.(10 marks) 4(a) Design a TM that recognizes palindrome strings where $\sum$={0,1} (10 marks) 4(b) Construct NFA that accept a set of all strings over {a,b}ending with "abb"Covert this NFA to Equivalent DFA.(10 marks) 5(a) Convert the following Grammar to CNF form:
S$\rightarrow$ ABA
A$\rightarrow$aA|bA| $\epsilon$
B$\rightarrow$ bB|aA|$\epsilon$(10 marks) 5(b) Give and explain the formal statement of pumping lemma for languages and use it to prove that the following languages is not regular:
L={a^{n}b^{n}|n>=1}(10 marks)

Write short notes on:

6(a) Chomsky Hierarchy of Grammar(5 marks) 6(b) Variants of Turning machine(5 marks) 6(c) Rice's Theorem(5 marks) 6(d) Recursive and Recursively enumerable languages.(5 marks)