## 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 'ic_{1} tic_{2} 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} | Ø |

**3 (b)**Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show that following languages are not regular.

L = { 0

^{n}1

^{2n}/ n > 0 }

L = { ww

^{R}/ 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 | Ø | Ø | Ø |

**3 (d)**Find CFG from given PDA that accepts the language {0

^{n}1

^{n}}. 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 | ^ |

**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={ a

^{i}b

^{j}c

^{k}| 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
{ a^{n} b^{n} c^{n} | n≥ 1 }.(8 marks)
**5 (d) (i)** Halting Problem(3 marks)

### Write short note on following:

**5 (d) (ii)** Church Turing Thesis(3 marks)