Download GTU BE/B.Tech 2019 Winter 6th Sem New 2160704 Theory Of Computation Question Paper

FirstRanker.com

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER- VI (New) EXAMINATION - WINTER 2019

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

Subject Code: 2160704 Date: 09/12/2019

Subject Name: Theory of Computation

Time: 02:30 PM TO 05: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.

MARKS

Q.1 (a) Define — bijection function. Check whether the function f : Z — Z defined by f(x) = 2x is a bijection function or not. Justify your answer. 03

(b) Draw an FA that recognizes the language of all strings containing even no of 0’s and even no of 1’s over S = {0,1}. Also write a regular expression for the same language. 04

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

(c) Write the principle of Mathematical Induction. Prove using mathematical induction that for every n > 0,

? i / (i+1) = n / (n+1) (Consider the sum on the left is 0 for n = 0) 07

i=1

Q.2 (a) Find regular expression and also derive the words corresponding to the language defined recursively below over S = {a, b} . 03

1. a ? L

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

2. For any x ? L, xa and xb are elements of L

(b) Define — Equivalence relation. A relation on the set {1,2,3} is given as R = {(a,b) | a— b is an even no}. Check whether R is equivalence relation or not. Give reasons. 04

(c) Give transition table for PDA recognizing the following language and trace the move of the machine for input string abcba: L = {xcx^R | x ? {a,b}*} 07

OR

(c) Give transition table for PDA accepting the language of all odd-length strings over {a, b} with middle symbol a. Also draw a PDA for the same. 07

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

Q.3 (a) Let FA₁ and FA₂ be the FAs as shown in the figure recognizing the languages L₁ and L₂ respectively. Draw an FA recognizing the language, L₁ ? L₂. 03

(b) Define — Moore machine. Convert the following Moore machine into its equivalent Mealy machine: 04

(c) Convert the following NFA - ? into its equivalent DFA that accepts the same language: 07

OR

Q.3 (a) Prove that—“If there is a CFG for the language L that has no ?-productions, then there is a CFG for L with no ?-productions and no unit productions”. Support your answer with the help of the following CFG: 03

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

S ? A | bb

A ? B | b

B ? S | a

(b) Write CFG for the following languages : 04

1. {aⁱb^jc^k | i=j+k}

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

2. {aⁱb^jc^k | j=1 or j=k}

(c) Define — ambiguous grammar, leftmost derivation. Check whether the following grammars are ambiguous or not. Justify your answer with proper reason. 07

1. S ? ABA
2. S ? A | B
3. A ? aA | A

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

4. A ? aAb | aabb
5. B ? bB | A
6. B ? abB | A

Q.4 (a) Describe the language generated by the following grammars: 03

1. S ? aA | bC | b

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

2. S ? aT | bT | ?
3. A ? aS | bB
4. T ? aS | bS
5. B ? aC | bA | a
6. C ? aB | bS

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

(b) Discuss — Nondeterministic Turing Machines and Universal Turing Machines 04

(c) Minimize the following states of DFA and draw the minimum-state DFA that is equivalent to the following DFA. 07

Q.4 (a) Prove that the language L = {aⁿbⁿaⁿbⁿ | n=1,2,3,...} is nonregular using pumping lemma. 03

OR

(a) Find the CFG for the regular expression : (011 + 1)* (01)* 03

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

(b) Convert the following CFG into its equivalent CNF: 04

S ? TU | V

T ? aTb | ?

U ? cU | ?

V ? aVc | W

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

W ? bW | ?

(c) Convert the following CFG into its equivalent PDA. 07

S ? AB

A ? BB

B ? AB

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

A ? a

B ? a | b

(b) Show using the pumping lemma that the following language is not a CFL. L= {aⁱb^jc^k | i < j < k} 04

(c) Draw a Turing Machine that accepts the language {aⁿb^maⁿ | n > 0} over {a, b}*. Also trace the TM on input string aaabbbaaa. 07

(b) Define Context Sensitive Language and Context Sensitive Grammar. Write CSG for L ={aⁿbⁿcⁿ | n = 1}. 04

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

OR

(b) Define - Primitive recursive functions and also give complete primitive recursive derivations for the function, f: N ? N defined by Add(x,y) = x+y. 04

(c) Draw a Turing Machine that accepts the language {xx | x ? {a,b}*}. Also trace the TM on input string aa. 07

FirstRanker.com

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