Subject
AJ - 2160707
DS - 2130702
DBMS - 2130703
OS - 2140702
SE - 2160701
TOC - 2160704
About
About Us
Contact Us
Paper Solution of
TOC
(2160704)
for
Winter
- 2018
Theory-Of-Computation-2160704
Winter-2018
Modal title
Widget settings form goes here
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - Semester - ____ EXAMINATION -
Winter-2018
Date:
27/11/2018
Total Marks :
70
NOTE:
Click on the Question to View Answer!
Q.1
(a)
Define one to one, onto and bijection function
3 marks
(b)
Explain reflexivity, symmetry, and transitivity properties of relations
4 marks
(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
7 marks
Q.2
(a)
What are the closure properties of regular languages?
3 marks
(b)
Explain moore machine and mealy machine.
4 marks
(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}
7 marks
OR
(c)
Define NFA-Λ .Explain how to convert NFA-Λ into NFA and FA with suitable example
7 marks
Q.3
(a)
State pumping lemma for regular languages.
3 marks
(b)
Explain Union Rule and Concatenation Rule for Context Free Grammar
4 marks
(c)
Write difference between DFA and NDFA. Convert the following NDFA to DFA.
7 marks
OR
Q.3
(a)
Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar?
S -> aTb | ab
aT -> aaTb | ac
3 marks
(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.
(ii) The language of all strings beginning with 1 and ending with 0.
4 marks
(c)
What is CNF? Convert the following CFG into CNF.
S -> ASA | aB,
A -> B | S,
B -> b | e
7 marks
Q.4
(a)
What is Turing Machine? Write advantages of TM over FSM
3 marks
(b)
Define CFG. When a CFG is called an ‘ambiguous CFG’?
4 marks
(c)
Define PDA. Describe the pushdown automata for language {0
^{n}
1
^{n}
| n >= 0}
7 marks
OR
Q.4
(a)
Write a short note on Universal Turing Machine.
3 marks
(b)
Describe recursive languages and recursively enumerable languages.
4 marks
(c)
Explain push down automata with example and their application in detail
7 marks
Q.5
(a)
Define grammar and chomsky hierarchy
3 marks
(b)
What are the applications of regular expressions and finite automata?
4 marks
(c)
Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}.
7 marks
OR
Q.5
(a)
Compare FA, NFA and NFA-^
3 marks
(b)
Write a short note on church-turing thesis
4 marks
(c)
Explain primitive recursive function by suitable example
7 marks