0
1.1kviews
Theoretical Computer Science Question Paper - May 17 - Computer Engineering (Semester 4) - Mumbai University (MU)
1 Answer
0
45views

Theoretical Computer Science - May 17

Computer Engineering (Semester 4)

Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

Q1

a) Differentiate between NFA and DFA
(5 marks) 00

b) Explain Chomksy Hierarchy
(5 marks) 00

c) Explain Rice's Theorem
(5 marks) 00

d) Explain Pumping Lemma for CFG
(5 marks) 00

Q2

a) Design FA to check divisibility by 3 to binary number
(10 marks) 00

b) Using pumping lemma proove that following language is not regular :

L={$0^m 1^{m+1}$ | m>0}

(10 marks) 00

Q3

a) Design Morre machine to generate output A if string is ending with abb, B if string ending with aba and C otherwise over alphabet (a,b) and convert it to mealy machine
(10 marks) 00

b) simplify the given grammer: S----> aAa/bBb/BBA--->CB---> A/SC---->S/c
(10 marks) 00

Q4

a) a) Construct NFA for given regular expressions:

i) (a+b)*ab

ii) aa(a+b)*b

iii) aba(a+b)*,

iv) (ab/ba)/(aa/bb)

(10 marks) 00

b) Construct PDA accepting the language L={$a^{2n}b^n$| n>0}
(10 marks) 00

Q5

a) Design minimized DFA for accepting strings ending with 100 over alphabet (0,1)
(10 marks) 00

b) Design Turning machine to recognize wellformedness of parenthesis
(10 marks) 00

Q6 Write short note on (any four)

a) Greibach Normal form
(5 marks) 00

b) Deterministic PDA and Multistack PDA
(5 marks) 00

c) Variants of Turning Machine
(5 marks) 00

d) Halting Problem
(5 marks) 00

e) Church- Turning Thesis
(5 marks) 00

Please log in to add an answer.