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

FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER-VI (OLD) EXAMINATION - WINTER 2018

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

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) (1) State the properties of Equivalence Relations. 03
(2) State the strong principle of mathematical induction and show how will you give proof by induction? 04

(b) (1) Prove that the statements: (p v q) ? r and (p ? r) v (q ? r) are logically equivalent. 03

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

Q.2 (a) Convert following NFA-? to NFA, draw the NFA. {?} ? A. 07

 q\d(q,A) | d(q,?) A| {B,D} ? B {C} {E} C {B} D {E} {D} E 

(b) Draw NFA - ? for((0+1)*10 + (00)*(11)*)* 07
Show step by step construction.

OR

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

(b) State part-1 and part-2 of Kleens theorem and show the proof. 07

Q.3 (a) L1 and L2 are two languages: 07
L1={x| 11 is not a substring of X}
L2 = {x | x starts with 0 and ends with 0}
Draw FA for both L1 and L2 and construct FA for L3 = L2 - L1

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

(b) An NFA with states 1-5 and input alphabet {a, b} has the following transition table. 07

 q\d(q,a) | d(q,b) 1 {1,2} {1} 2 {3} {3} 3 {4} {4} 4 {5} 5 {5} 

Q.1 Draw its transition diagram
Q.2 Calculate d* (1,a)
Q.3 Calculate d* (1,aaabaab)

OR

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

Q.3 (a) Convert this NFA to FA 07

 0\1 1 0\1 Koo 

(b) A language L ? {a, b}* is defined as follows: 07

1. a ? L
2. For any x ? L, ax ? L
3. For any x and y in L, all the strings bxy, xby and xyb are in L

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

4. No other strings are in L.

Prove that every element of L has more a’s than b’s.

Q.4 (a) Define PDA and give PDA to accept strings of palindrome. Show trace on the string baab 07

(b) Write a short note on parsing. 07

OR

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

Q.4 (a) Define deterministic pushdown automata. Construct an example of DPDA that accepts strings with more 'a’s than b’s 07

(b) (1) Give recursive definition for Language Pal of palindromes. 03
(2) Give CFG equivalent to regular expression (011 + 1)* (01)* 04

Q.5 (a) Define Turing Machine and draw a TM to accept {a,b}*{aba} {a,b}* 07

(b) Write a short note on Universal Turing Machines. 07

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

OR

Q.5 (a) Write a note on models of computation and The Church Turing Thesis. 07

(b) What is the difference between accepting a language and recognizing a language? 07
Write short note on recursively enumerable languages.

FirstRanker.com

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