Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2018 Winter 6th Sem Old 160704 Theory Of Computation Previous Question Paper
1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VI (OLD) EXAMINATION ? WINTER 2018
Subject Code:160704 Date: 30/11/2018
Subject Name: Theory of Computation
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
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
(2) What is the regular expression of following FA?
04
Q.2 (a) Convert following NFA-? to NFA, draw the NFA. {E} ? A.
q ?(q, ?) ? (q,0) ? (q,1)
A {B,D} {A} ?
B ? {C} {E}
C ? ? {B}
D ? {E} {D}
E ? ? ?
07
(b)
Draw NFA ? ? for ((0 + 1)*10 + (00)*(11)*)*
Show step by step construction.
07
OR
(b) State part-1 and part-2 of Kleens theorem and show the proof. 07
Q.3 (a) L1 and L2 are two languages:
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\
07
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
FirstRanker.com - FirstRanker's Choice
www.FirstRanker.com
1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VI (OLD) EXAMINATION ? WINTER 2018
Subject Code:160704 Date: 30/11/2018
Subject Name: Theory of Computation
Time: 02:30 PM TO 05:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
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
(2) What is the regular expression of following FA?
04
Q.2 (a) Convert following NFA-? to NFA, draw the NFA. {E} ? A.
q ?(q, ?) ? (q,0) ? (q,1)
A {B,D} {A} ?
B ? {C} {E}
C ? ? {B}
D ? {E} {D}
E ? ? ?
07
(b)
Draw NFA ? ? for ((0 + 1)*10 + (00)*(11)*)*
Show step by step construction.
07
OR
(b) State part-1 and part-2 of Kleens theorem and show the proof. 07
Q.3 (a) L1 and L2 are two languages:
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\
07
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
www.FirstRanker.com
2
(b) An NFA with states 1-5 and input alphabet {a, b} has the following transition
table.
q ?(q,a) ?(q,b)
Q.1 Draw its transition diagram
Q.2 Calculate ?* (1,a)
Q.3 Calculate ?* (1,aaabaab)
1 {1,2} {1}
2 {3} {3}
3 {4} {4}
4 {5} ?
5 ? {5}
07
OR
Q.3 (a) Convert this NFA to FA
07
(b) A language L {a, b}* is defined as follows:
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
4. No other strings are in L.
Prove that every element of L has more a?s than b?s.
07
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
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
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?
Write short note on recursively enumerable languages.
07
*************
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
FirstRanker.com - FirstRanker's Choice
This post was last modified on 20 February 2020