Download GTU B.Tech 2020 Winter 6th Sem 2160704 Theory Of Computation Question Paper

FirstRanker.com

Subject Code: 2160704

GUJARAT TECHNOLOGICAL UNIVERSITY

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

BE- SEMESTER-VI (NEW) EXAMINATION - WINTER 2020
Subject Name: Theory of Computation
Time: 02:00 PM TO 04:00 PM

Instructions:

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

1. Attempt any FOUR questions out of EIGHT questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

Q.1 (a) Discuss Recursive definition. Also define the language L defined by the following recursive definition over S = {a, b}:
e ? L;

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

For every x ? L, xa, bx, and abx are in L;
Nothing else is in L. [03]

(b) Let relation R = {(a,b) : a+ b =10 and a, b ? N}. Decide whether R is an equivalence relation or not. Justify your answer with proper reason. [04]

(c) Using the principle of mathematical induction, for all n > 0, prove that, 1x2 + 3x4 + 5x6 +....+ (2n—1) x2n = n(n+1) [07]

Q.2 (a) Write regular expressions for the following languages defined over S = {0, 1}:

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

(i) The language of all the strings that do not end with 01.
(ii) The language of all the strings containing even number of 0’s and even number of 1’s. [03]

(b) Draw DFA for the following languages defined over S = {a, b}:
(i) The language of all the strings with next-to-last symbol is a.
(ii) The language of all the strings containing substring bba. [04]

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

(c) Convert the following NFA into its equivalent DFA using the subset construction. [07]

This download link is referred from the post: GTU B.Tech 2020 Winter Question Papers || Gujarat Technological University