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

FirstRanker.com

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

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

Subject Code:160704 Date:29/01/2021
Subject Name:Theory Of Computation
Time:02:00 PM TO 04:00 PM Total Marks:56

Instructions:
1. Attempt any FOUR questions out of EIGHT questions.

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

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

Q.1 (a) Answer the following 07
1.Define regular language and regular expressions.
2.Find regular expression for the following: Language of all string that do not end with 01.

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

3. Describe the language corresponding to following: (1+01)*(0+01)*

(b) Answer the following:
1 Define One-to-one and Onto Functions. Also explain Compositions and Inverse of 04 Functions.
2 Define Mathematical Induction Principle and Prove that for every n > 1, 03
? i²=n(n+1)(2n+1)/6

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

i=1

Q.2 (a) Answer the following 07
1.Draw FA for regular expression: (111+100)*0
2. Let M1 and M2 be the FA in fig below for the language L1 and L2, find L1 U L2 and L1 L2.

(b) 07

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

Q.3 (a) State the pumping lemma for regular language. Prove that {0ⁿ1ⁿ | n >= 0} is not a regular language (7

(b) Convert the Given NFA into its equivalent DFA-

FirstRanker.com

Q.4 (a) Give the context free grammar for the following languages. 07
1. L={aⁿbⁿ|n>=0}

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

2. Language for Palindromes.
3. Language for Non-Palindromes.
4. Language for Algebraic Expressions
5. L={x belongs to {0,1}* | n₀(x) = n₁(x) }
6. L={x belongs to {0,1}* | n₀(x) ? n₁(x) }

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

7. The set of odd-length strings in {a,b}* with middle symbol a.

(b) Define NFA and NFA-?. Convert the following NFA to DFA 07

Q.5 (a) Differentiate Turing machine, PDA and FA with example. 07

(b) Write Short note on Universal Turing Machine. 07

Q.6 (a) Draw the PDA for the following language 07

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

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

(b) Define CFG. Prove that the following CFG-is Ambiguous. 07
S->S+S|S*S|(S)|a
Write the unambiguous CFG for the above grammar.

Q.7 (a) Define a Turing Machine. Design a Turing machine for deleting nth symbol from a string w from the alphabet X = {0,1}. 07

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

(b) Prove that any Regular Language can be accepted by FA. 07

Q.8 (a) Draw Turing machine which accept palindrome language. 07

(b) Prove The Theorem: “ If L1 and L2 are context — free languages, then the languages L1 U L2, L1L2, L1* are also CFL.” 07

FirstRanker.com

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