THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2011 COMPUTER SCIENCE SEMESTER 5
(3 Hours) [Total Marks:-100]
(b) Convert the following NFA to a DFA. [5 Marks]
R = (1(00)*1 + 0 1*0)*
(d) Write a short note on Ambiguity Resolution. [5 Marks]
2. (a) Obtain DFA to accept the strings which contains exactly three a's over ∑ ={a,b} [8 Marks]
(b) Give Mealy and Moore machine to change each occurrence of substring 120 to 121
over ∑={0,1,2} [10 Marks]
(c) Give the statement of Pumping Lemma for regular Languages. [2 Marks]
3. (a) Minimize the following DFA, where is the q0 start state and q3 and q5 are final
states:- [10 Marks]
(b) Using Pumping Lemma, show that following grammars are not regular:- [10 Marks]
(i) 
(ii)
4. (a) Consider the grammar:- [10 Marks]
S -> OB|1A
A -> O|OS|1AA
B -> 1|1S|OBB
For the string 00110101 find the follwoing:-
(i) Leftmost Derivation
(ii) Rightmost derivation
(iii) Parse tree
(b) Convert the follwoing grammar into CNF :- [10 Marks]
S -> ASB|ϵ
A -> aAS|a
B -> SbS|A|bb
5. (a) Convert the following grammar in GNF :- [8 Marks]
S -> AA | 0
A -> SS | 1
(b) Construct PDA for the following language: - [8 Marks]
(c) Differentiate between DPDA and NPDA. [4 Marks]
6. (a) Define PDA and construct PDA grammar:- [10 Marks]
E -> E+E|E-E|(E)|id
(b) Design Turing machine for recognising the following language: - [10 Marks]
(i)
(ii)
7. Write short notes on any four of the following:- [20 Marks]
(a) Chomsky hierarchy
(b) Post Correspondence Problem
(c) Universal Turing Machine
(d) Halting Problem
(e) Closure properties of context free language.
No comments:
Post a Comment