written 7.7 years ago by |
Theory Of Computation - Jun 2015
Computer Engineering (Semester 6)
TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.
1 (a) Define Mathematical Induction Principle and Prove that for every n ≥ 0,
[sum_{i=0}^{N} i=n(n+1)/2].(7 marks)
1 (b)(i) Suppose that Languages L1 and L2 are the subsets given below.
Where Σ={0,1}
L1 = { x | 00 is not a substring of x }
L2 = { x | x ends with 01 }
Draw FAs recognizing the following languages
1) L1-L2 2) L1∩L2.(5 marks)
1 (b)(ii) Show that the function f1(x,y) = x + y is primitive recursive(2 marks)
2 (a) Write definition of finite automata and draw FA for the strings:
(i) The string in {0,1}* ending in 10 or 11
(ii) The string corresponding to Regular expression {11}{00}(7 marks)
2 (b) Define Context Free Grammar(CFG). Design CFG for Generating Following
Language:
(1) For Balanced Parenthesis
(2) Set of even length strings in {a, b, c, d}* with two middle symbol equal.(7 marks)
2 (c) Design an ambiguous grammar for if-then-else statement that also generates
if-then statement. Re-write an equivalent unambiguous grammar. Prove that
Grammar is Unambiguous by tracing 'ic1 tic2 taea'.(7 marks)
3 (a) Convert NFA-^ to NFA and DFA. Initial State: A , Final State: D
Q | δ(q,^) | δ(q,0) | δ(q,1) |
A | {B} | {A} | Ø |
B | {D} | {C} | Ø |
C | Ø | Ø | {B} |
D | Ø | {D} | Ø |
L = { 0n 12n / n > 0 }
L = { wwR / w ε {0,1}* }(7 marks) 3 (c) Convert NFA-^ to NFA and FA. Initial State: A , Final State: E
<colgroup span="4" width="85"> </colgroup>
Q | δ(q,^) | δ(q,0) | δ(q,1) |
A | {B,D} | {A} | Ø |
B | Ø | {C} | {E} |
C | Ø | Ø | {B} |
D | Ø | {E} | {D} |
E | Ø | Ø | Ø |
(Q,Σ,Γ,δ,q,Z,F) where Q={q,r},Σ={0,1},Γ={Z,X},δ
<colgroup span="5" width="85"> </colgroup>
State | Input | Stack | New State | Stack |
q | 0 | Z | q | XZ |
q | 0 | X | q | XX |
q | 1 | X | r | ^ |
r | 1 | X | r | ^ |
r | ^ | Z | r | ^ |
S → SS | A | B
A → SS | AS | a
B→Λ(5 marks) 4 (a) (ii) Convert following CFG to PDA,br> S → 0S1 | 00 | 11.(2 marks) 4 (b) For the language L={set of strings over alphabet {a, b} with exactly twice as many a's as b's} design a PDA (Push Down Automata) and trace it for the sring "abaabbaaaaabaab".(7 marks) 4 (c) Given the Context Free Grammar G, find a CFG G' in Chomsky Normal Form generating L(G) - { }
1) S → aY | Ybb | Y
X → Λ | a
Y → aXY | bb | XXa
2) S → AA
A → B | BB
B → abB | b | bb.(7 marks) 4 (d) For the language L={ ai bj ck | i, j, k ≥ 0 and i + j = k } design a PDA (Push Down Automata) and trace it for String "bbbbbccccc".(7 marks) 5 (a) Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as Odd.(8 marks)
Write short note on following:
5 (b) (i) Universal TM(3 marks) 5 (b) (ii) NP-Hard and NP-Complete Language(3 marks) 5 (c) Draw Turing Machine(TM) which recognizes words of the form { an bn cn | n≥ 1 }.(8 marks) 5 (d) (i) Halting Problem(3 marks)
Write short note on following:
5 (d) (ii) Church Turing Thesis(3 marks)