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

Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Winter 6th Sem 160704 Theory Of Computation Previous Question Paper

Seat No.: ________
Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER?VI (OLD) EXAMINATION ? WINTER 2020
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.

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.
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
n
i2 = n (n+1)(2n+1) / 6
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) For following NFA find minimum FA accepting same language
07



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

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

1

---

Q.4 (a) Give the context free grammar for the following languages.
07
1. L = { anbn |n>=0 }
2. Language for Palindroms.
3. Language for Non-Palindroms.
4. Language for Algebraic Expressions
5. L = { x belongs to {0,1}* | no(x) = n1(x) }
6. L = { x belongs to {0,1}* | no(x) n1(x) }
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
L = {aibjck | i = j+k}

(b) Define CFG. Prove that the following CFG is Ambiguous.
07
SS + 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 07
string w from the alphabet = {0,1}.

(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
07
languages 1 2, 12 , 1* are also CFL."

*************
2

---