Download GTU BE/B.Tech 2019 Summer 6th Sem Old 160704 Theory Of Computation Question Paper

FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY

SEMESTER-VI(OLD) - EXAMINATION - SUMMER 2019

--- Content provided by‌ FirstRanker.com ---

Subject Code: 160704 Date: 18/05/2019

Subject Name: Theory Of Computation

Time: 10:30 AM TO 01:00 PM Total Marks: 70

Instructions:

1. Attempt all questions.

--- Content provided by⁠ FirstRanker.com ---

2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

Q.1 (a) Write Principle of Mathematical Induction. Using Principle of Mathematical 07 Induction, prove that for every n>1,

? i = n(n+1)(2n+1) / 6

i=1

--- Content provided by‍ FirstRanker.com ---

(b) Define reflexivity, symmetry, and transitivity properties of relations. Consider the 07 relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2, 3}. Is it reflexive? Symmetric? Transitive? Justify each of your answers.

Q.2 (a) Convert NFA to NFA and DFA. Initial State: A, Final State : D 07

(b) Suppose that L1 and L2 are the subsets 07

Draw the FAs recognizing the following Languages:

1. L1 n L2

--- Content provided by​ FirstRanker.com ---

2. L1 - L2

FirstRanker.com

OR

Q.3 (a) Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show 07 that the following languages are not regular.

1. L={0n1n|n>0}

--- Content provided by FirstRanker.com ---

2. L={ww^R|we{0,1}*}

(b) Define Ambiguous grammar. Write Unambiguous grammar for following 07 grammar :

E->E+E|E*E|(E)|id

Derive string “id+id*id” using unambiguous grammar.

Q.4 (a) Given the CFG G, find a CFG G’ in Chomsky Normal form generating L(G) — { 07 ?}

--- Content provided by‌ FirstRanker.com ---

S->A|B|C

A->aAa|B

B -> bB|bb

C -> aCaa|D

D - baD | abD | aa

--- Content provided by‍ FirstRanker.com ---

OR

(b) Design Context Free Grammar for following Language : 07

L={0^j1ⁱ0^k|j>i+k}

Q.5 (a) Write Regular Expressions corresponding to each of the following subsets of 07 {0,1}*

1. The language of all strings in {0,1}* that containing at least two 0’s.

--- Content provided by​ FirstRanker.com ---

2. The language of all strings containing both 101 and 010 as substrings.
3. The language of all strings that do not end with 01.

(b) Design PDA for the language L = { x ? {a;b}* | n_a(x) > n_b(x) }. 07

OR

(a) Explain Cook’s Theorem. 07

--- Content provided by FirstRanker.com ---

(b) Design PDA for the language L ={xcx^R | x ? {a, b}* } 07

(a) Write Short note on Any Two: 07

1. The Primitive Recursion Function
2. P and NP Completeness
3. Equivalence Relation

--- Content provided by‍ FirstRanker.com ---

(b) Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as 07 odd.

OR

(a) Write Short note on Following: 07

1. Halting Problem
2. Church Turing Thesis

--- Content provided by‌ FirstRanker.com ---

(b) Design Turing Machine to copy string. 07

(a) Explain Time Complexity and Space Complexity. 07

FirstRanker.com