and 2 others joined a min ago.
0
750views
Theoretical Computer Science Question Paper - May 18 - Computer Engineering (Semester 4) - Mumbai University (MU)
1 Answer
0
7views
written 7.3 years ago by
teamques10
★ 70k
|
Theoretical Computer Science - May 18
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)
Diffentiate between DFA and NFA
(5 marks)
00
b)
Show that L={$0^n1^n$|n>0} is not regular using pumping lemma
(5 marks)
00
c)
Define FA. List down the applications of FA
(5 marks)
00
d)
Explain Recursively Enumerable Language
(5 marks)
00
Q2
a)
Construct the NFA with c-moves for the regular expression
(10 marks)
00
a) for the language which ends in either 01 or 101 over E={0,1}.
b) for the R.E (ab + (ab)*) over E = {a,b}
b)
Construct the DFA that accepts the language represented by 012*
(10 marks)
00
Q3
a)
convert the given grammer into Griebach Normal Form
(10 marks)
00
S-----> ABA|AB|BA|AA|A|B
A------> aA|a
B------>bB|b
b)
Design Mealy Machine for the language represented as (0+1)*(00+11)
(10 marks)
00
Q4
a)
State and prove pumping lemma for context free languages
(10 marks)
00
b)
Write short note on
(10 marks)
00
i) Post Correspondence problem
ii) Chomsky Heirarchy
Q5
a)
Design PDA that accepts the language L={$a^nb^ma^n$|m,n>=1}
(10 marks)
00
b)
Design turning machine to accept languages over E={0,1} where L={$0^n1^n$|n>0}
(10 marks)
00
Q6
a)
Draw a parse tree for the string aabbaa for the CFG given by G where
(10 marks)
00
P= {S------>aAS|a
A---->AbA|SS|ba
Perform both leftmost and rightmost derivation.
b)
Briefly Explain the types of Turning Machine
(10 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.