and 3 others joined a min ago.
0
646views
Theory of Computation Question Paper - Jun 18 - Information Technology (Semester 5) - Pune University (PU)
1 Answer
0
5views
written 6.9 years ago by
teamques10
★ 70k
|
Theory of Computation - Jun 18
Information Technology (Semester 5)
Total marks: 70
Total time: 2 Hours 30 min
INSTRUCTIONS
(1) Attempts questions Q.1 or Q.2, Q.3 or Q.4 , Q.5 or Q,6 and Q.7 or Q.8 .
(2) Neat diagrams must be drawn whenever necessary.
(3) Assume suitable data , if necessary.
1.a.
Define pumping lemma. Prove that the language L = {aⁿbⁿ⁺¹|n>0} is non regular
(6 marks)
00
1.b.
Construct FSM for divisibility by 3 tester for binary number.
(4 marks)
00
OR
2.a.
Comstruct the Mealy machine to accept strings ending with '00' or '11' over Σ={0,1). Covert Mealy Machine into equivalent Moore machine.
(8 marks)
00
2.b.
If L(r)={∈,x,xx,xxx,xxxx,xxxxx} What is r?
(2 marks)
00
3.a.
Simplify the following grammar
(5 marks)
00
S→a|Xb|aYa
X→Y|∈
Y→b|X
3.b.
Write an equivalent left-linear grammar for the right-linear grammar which is defined as:
(5 marks)
00
S→0A | 1B
A→0C|1A|0
B→1B|1A|1
C→0|0A
OR
4.a.
Check whether or not the following grammar is ambiguous : if it is ambiguous, remove the ambiguity and write an equivalent unambiguous grammar
(6 marks)
00
E→E+E|E−E|E*E|E|E|(E)|id
4.b.
Convert the given CFG G=({s}, {a}, p,s) into CNF.
(4 marks)
00
S→aaaaaaS|aaa
5.a.
Construct PDA to accept the strings containing equal no. of a's & b's over Σ={a,b}
(8 marks)
00
Write ID for
i. abbaab.
ii. aabb.
5.b.
Design a PM that checks if the given strings contains well-formed parenthesis.
(8 marks)
00
Simulate for
(() ())
OR
6.a.
Construct a PDA that accepts the language L={aⁿbᵐzⁿ|m,n≥1}.
(8 marks)
00
Write ID for
i. aabbaa.
ii. abbba
6.b.
Construct PDA for the following language
(8 marks)
00
L = {a²ⁿbⁿ|n≥1}
7.a.
Design a TM which compares two positive integers m & n and produces output Gt if m > n ; Lt if m < n; and Eq if m = n;
(12 marks)
00
Write simulation for the input
i. m = 1, n = 2.
ii. m = n = 2.
7.b.
Write short note on UTM.
(6 marks)
00
OR
8.a.
Construct TM for the language L = {aⁿbⁿcⁿ | n > 0}.
(10 marks)
00
8.b.
Design a TM to find the value of log₂(n) where n is any binary number and a perfect power of 2
(8 marks)
00
9.a.
Prove that following are decidable languages.
(10 marks)
00
i. 
= {⟨G, W⟩| G is a CFG that generates string W}.
ii. 
= (⟨G, W⟩| G is CFG & L (G) = 
}
9.b.
Define the class P & Class NP problems with example.
(6 marks)
00
OR
10.a.
Prove that
(8 marks)
00
PCP = {⟨P⟩| P is an instance of the post correspondence problem with a match}
is undecidable
10.b.
Explain Turing Reduciability with example.
(8 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.