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
S-----> ABA|AB|BA|AA|A|B
A------> aA|a
B------>bB|b
(10 marks)
00
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
i) Post Correspondence problem
ii) Chomsky Heirarchy
(10 marks)
00
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
P= {S------>aAS|a
A---->AbA|SS|ba
Perform both leftmost and rightmost derivation.
(10 marks)
00
b)
Briefly Explain the types of Turning Machine
(10 marks)
00