University of Pune 2006 B.E Information Technology TOC - Question Paper
TOC 2006
Total No. of Questions : 12]
3 0 MAY 2006
[Total No. of Pages : 3
[2963] - 450 T.E. (IT) (2003 Course) THEORY OF COMPUTATION
[Max. Marks : 100
Time: 3 Hours]
Instructions:
1) Attempt 3 questions from section I and 5 questions from section II.
2) A Mirers to the two sections must be in different answer hooks.
3) Figures to the right indicate full marks.
Ql) A) Consider the following - NFA
|
a |
b |
c | ||
|
p |
{Pi |
{q} |
{rj | |
|
q |
{q} |
{r} |
(P) | |
|
r |
{I'} |
(P> |
(ql |
03) A) State and prove Pumping Lemma for regular sets
B) Which of the following are true? Explain.
1) baaSa* b* a* b*
2) b* a* fl a* b* - a* U b*
3) a* b* fl b* c* ="(j>
4) abed (a (cd)* b)*
C) What language is represented by Regular Expression: (((a*a)b) U b)
OR
04) A) Convert following RE to DFA
(RE to NFA with S moves to DFA)
(ab + ba)* aa (ab +ba)*
B) Write a note on Kleens Theorem
05) A) Wrile an algorithm in C to convert Regular Grammar lo
Simulate it with an example.
B) Define Phase Structure Grammar
OR
06) A) Write CFG for the following languages
ii) Matching Parenthesis '
iii) All strings with atleast 2 as alphabet ~ {a, b}
B) Write a note on
Simplification of Grammar
Q7) A) With the help of PDA show that CFL are closed under union, concatenation and Klcens closure. [12]
B) Compare the power of Post machine and Push Down Automata. [4|
OR
QS) A) Construct PDA for
S -> ORB
B 0S/IS/O [8]
B) Draw a Post Machine that accepts even and odd palindrome [Sj
Q9) A) Write a TM for making copy of a string that consists of {a, b} (10)
B) Write short note on:
Halting Problem [8]
OR
QJO) A) Write a T M. to replace string 110 by 101 in a binary input string. [8]
B) Write Motes on:
i) Churchs Turing Hypothesis
ii) Unsolvable Problems [10]
QW Write short notes on:
a) Applications of FA
b) Chomsky Heirarchy
c) Limitations of TM [16]
OR
Q12) A) Compare DPDA, NPDA, DFA and NFA in terms of their powers. [8] B) Write a short note on Applications of TM |8]
ii) Give all strings of length 3 or less accepted by the automation, ii:) Convert the automation to DFA [12]
B) Define:
ii) Language
OR
OJ) A) Give Mealy and Moore machine for the following:
From input *, where {0,1,2} print the residue modulo 5 of the input treated as ternary (base 3). ' [12]
B) Define:
NFA, DFA in the Tuple Format
|
Attachment: |
| Earning: Approval pending. |
