and 4 others joined a min ago.
0
476views
Theory Of Computation Question Paper - Dec 17 - Computer Engineering (Semester 5) - Pune University (PU)
1 Answer
0
1views
written 6.9 years ago by
teamques10
★ 70k
|
Theory Of Computation - Dec 17
Computer Engineering (Semester 5)
Total marks: 70
Total time: 2 Hours 30 min
INSTRUCTIONS
(1) Attempt questions Q.1 or Q.2,Q.3 or Q.4 , Q.5 or Q.6 , Q.7 or Q.8.
(2) Neat diagram must be drawn whenever necessary.
(3) Assume suitable data , if necessary.
1.a.
Construct DFA for language defined by $\sum$ = {0,1} where
(6 marks)
00
S = {strings ending with 0 always}
S = {strings representing odd binary numbers}
S = {strings over $\sum$* with total number of 0's even}
1.b.
Let 
be an NFA
(6 marks)
00
be an NFA
Where
Construct an equivalent DFA.
1.c.
Write short notes on :
(8 marks)
00
i) Chomsky Normal form
ii) Greibach Normal Form
OR
2.a.
Design a FA which checks the divisibility by 4 for a decimal number.
(6 marks)
00
2.b.
Construct a Moore and Mealy Machine to generate 1's compliment of a given binary number.
(6 marks)
00
2.c.
Write CFG's for given CFLs :
(8 marks)
00
i) Language containing the strings with equal number of a's and b's.
ii) Language containing the string containing a's and b's with a least 2 a's.
3.a.
Define Turing machine. Comment on language acceptance by Turing Machine.
(4 marks)
00
3.b.
Write short notes on :
(6 marks)
00
i) Universal Turing Machine.
ii) Multi-Tape Turing Machine.
iii) Limitation of Turing Machine.
3.c.
Construct a Turing Machine to accept the language of even number of 1's and even number 0's over $\sum$ = {0,1}
(8 marks)
00
OR
4.a.
Explain the representation of TM
(4 marks)
00
4.b.
Design a Turing Machine to add two unary numbers.
(6 marks)
00
4.c.
Construct TM for -
(8 marks)
00
L = {all strings with equal no. of a's and b's}
5.a.
Differentiate between FA and PDA.
(4 marks)
00
5.b.
Construct NPDA that accepts the language generated by S=S+S|S*S|4.
(6 marks)
00
5.c.
Illustrate the working of shift reduce parser for id+id*id.
(6 marks)
00
Consider the following grammar :
E $\rightarrow$ E + E | T
T $\rightarrow$ T * F | F
F $\rightarrow$ {E} | id
OR
6.a.
What are the two different ways to define PDA acceptability.
(4 marks)
00
6.b.
Construct PDA that accept language generated by following CFG :
(6 marks)
00
S $\rightarrow$ SS | (S)|( )
6.c.
Explain closure property of CFL with suitable example.
(6 marks)
00
7.a.
What do you mean by NP-problems ? Justify that Travelling Salesman problem is NP problem.
(8 marks)
00
7.b.
Define Undecidability. Let 
where M is TM and M halts on input w} Prove that 
is Undecidable.
(8 marks)
00
where M is TM and M halts on input w} Prove that is Undecidable.
OR
8.a.
Define and explain Recursive and recursively enumerable languages.
(8 marks)
00
8.b.
What is a Kruskal's Algorithm ? How can we solve this problem using Turing Machine?
(8 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.