Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2018 Winter 6th Sem New 2160704 Theory Of Computation Previous Question Paper
1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VI (NEW) EXAMINATION ? WINTER 2018
Subject Code:2160704 Date:27/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.
MARKS
Q.1 (a) Define one-to-one, onto and bijection function. 03
(b) Explain reflexivity, symmetry, and transitivity properties of relations. 04
(c) State the principle of mathematical induction and prove by mathematical
induction that for all positive integers n 1+2+3+??..+n = n (n+1)/2.
07
Q.2 (a) What are the closure properties of regular languages? 03
(b) Explain moore machine and mealy machine. 04
(c) What are the applications of finite automata? Draw Finite Automata to accept
following.
(i) the language accepting strings ending with ?01? over input alphabets ? =
{0, 1}
(ii) the language accepting strings ending with ?abba? over input alphabets ?
= {a, b}
07
OR
(c) Define NFA-?. Explain how to convert NFA-? into NFA and FA with
suitable example.
07
Q.3 (a) State pumping lemma for regular languages. 03
(b) Explain Union Rule and Concatenation Rule for Context Free Grammar. 04
(c) Write difference between DFA and NDFA. Convert the following NDFA to
DFA.
07
OR
Q.3 (a)
Define Context-Sensitive Grammar. What is the language of following
context-sensitive grammar?
S ? aTb | ab
aT ? aaTb | ac.
03
(b) Find a regular expression corresponding to each of the following subsets of
{0, 1}*
(i) The language of all strings that begin or end with 00 or 11.
04
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 (NEW) EXAMINATION ? WINTER 2018
Subject Code:2160704 Date:27/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.
MARKS
Q.1 (a) Define one-to-one, onto and bijection function. 03
(b) Explain reflexivity, symmetry, and transitivity properties of relations. 04
(c) State the principle of mathematical induction and prove by mathematical
induction that for all positive integers n 1+2+3+??..+n = n (n+1)/2.
07
Q.2 (a) What are the closure properties of regular languages? 03
(b) Explain moore machine and mealy machine. 04
(c) What are the applications of finite automata? Draw Finite Automata to accept
following.
(i) the language accepting strings ending with ?01? over input alphabets ? =
{0, 1}
(ii) the language accepting strings ending with ?abba? over input alphabets ?
= {a, b}
07
OR
(c) Define NFA-?. Explain how to convert NFA-? into NFA and FA with
suitable example.
07
Q.3 (a) State pumping lemma for regular languages. 03
(b) Explain Union Rule and Concatenation Rule for Context Free Grammar. 04
(c) Write difference between DFA and NDFA. Convert the following NDFA to
DFA.
07
OR
Q.3 (a)
Define Context-Sensitive Grammar. What is the language of following
context-sensitive grammar?
S ? aTb | ab
aT ? aaTb | ac.
03
(b) Find a regular expression corresponding to each of the following subsets of
{0, 1}*
(i) The language of all strings that begin or end with 00 or 11.
04
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
www.FirstRanker.com
2
(ii) The language of all strings beginning with 1 and ending with 0.
(c) What is CNF? Convert the following CFG into CNF.
S ? ASA | aB,
A ? B | S,
B ? b | ?
07
Q.4 (a) What is Turing Machine? Write advantages of TM over FSM. 03
(b) Define CFG. When a CFG is called an ?ambiguous CFG?? 04
(c) Define PDA. Describe the pushdown automata for language {0
n
1
n
| n? 0}. 07
OR
Q.4 (a) Write a short note on Universal Turing Machine. 03
(b) Describe recursive languages and recursively enumerable languages. 04
(c) Explain push down automata with example and their application in detail. 07
Q.5 (a) Define grammar and chomsky hierarchy. 03
(b) What are the applications of regular expressions and finite automata? 04
(c) Draw a transition diagram for a Turing machine for the language of all
palindromes over {a, b}.
07
OR
Q.5 (a) Compare FA, NFA and NFA-^. 03
(b) Write a short note on church-turing thesis. 04
(c) Explain primitive recursive function by suitable example. 07
*************
www.FirstRanker.com www.FirstRanker.com
www.FirstRanker.com
FirstRanker.com - FirstRanker's Choice
This post was last modified on 20 February 2020