Question Paper: Theory Of Computation : Question Paper Jun 2015 - Computer Engineering (Semester 6) | Gujarat Technological University (GTU)
0

## 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

<colgroup span="4" width="85"> </colgroup>
 Q δ(q,^) δ(q,0) δ(q,1) A {B} {A} Ø B {D} {C} Ø C Ø Ø {B} D Ø {D} Ø
(7 marks) 3 (b) Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show that following languages are not regular.
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 Ø Ø Ø
(7 marks)
3 (d) Find CFG from given PDA that accepts the language {0n 1n }. PDA is
(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 ^
(7 marks)
4 (a) (i) Given the Context Free Grammar G, find a CFG G' in Chomsky Normal Form generating L(G) ? }
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)