and 4 others joined a min ago.
0
730views
Theoretical Computer Science Question Paper - Dec 17 - Computer Engineering (Semester 4) - Mumbai University (MU)
1 Answer
0
3views
written 5.3 years ago by
teamques10
★ 64k
|
Theoretical Computer Science - Dec 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)
Explain Chomsky Hierarchy
(5 marks)
00
b)
Differentiate Between DFA and NFA
(5 marks)
00
c)
Explain Recursive and Recursively enumerable languages
(5 marks)
00
d)
Define regular Expression. Design RE for strings ending in consecutive 1's over E={0,1}
(5 marks)
00
Q2
a)
Design a Finite state Machine to determine whether ternary number(base 3) is Divisible by 5
(10 marks)
00
b)
Give and Explain formal definition of Puraping lemma for regular language and prove that the following language is not regular.
(10 marks)
00
L= {$a^n b^n$| n>=1}
Q3
a)
Design a PDA that checks for well- formed paretheis
(10 marks)
00
b)
Consider the following grammer
(10 marks)
00
S ---> i C t S| i C t S e S | a
C ----> b
For the string 'ibtibtaea' find the following:
i) Leftmost Derivation
ii) Rightmost Derivation
iii) Parse tree
iv) Check if above grammer is ambigous.
Q4
a)
Design a Turning Machine that recognizes palindrome string where E={a,b}
(10 marks)
00
b)
Reduce following grammer to GNF
(10 marks)
00
S---> AB
A----> BSB|BB|b
B---->a
i) S----> 01S|01
S-----> 10S|10
S------> 00|c
Q5
a)
Convert (0+c)(10)*(c+1) into NFA with c-mober and obtain DFA
(10 marks)
00
b)
Design a PDA to accept language {$a^{n-1} b^{2n+1} | n\gt=1$}
(10 marks)
00
Q6 Write short note on following (any four)
a)
Applications of Regular expression and finite automata
(5 marks)
00
b)
Rice's Theorem
(5 marks)
00
c)
Moore and Mealy Machine
(5 marks)
00
d)
Differntiate between DPDA and NPDA
(5 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.