Subject Code: 2160704
GUJARAT TECHNOLOGICAL UNIVERSITY
--- Content provided by FirstRanker.com ---
BE - SEMESTER- VI EXAMINATION — SUMMER 2020
Subject Name: THEORY OF COMPUTATION
Time: 10:30 AM TO 01:00 PM Date:28/10/2020 Total Marks: 70
Instructions:
- Attempt all questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
Q.1
(a) What is a proposition? Which logical connectives do we use to generate compound proposition? 03
(b) Out of these two statements which one is true and which is false. Justify your answer. 04
--- Content provided by FirstRanker.com ---
- ?x(?y((x— y)² < 4))
- ?y(?x((x — y)² < 4))
(c) Develop an FA corresponding to following regular expression r= (11+110)*0 07
OR
Q.2
--- Content provided by FirstRanker.com ---
(a) Explain the properties of Distinguishability of Strings and Equivalence classes, show minimum numbers of states necessary for this FA. 03
(b) Write the strong principle of mathematical induction and show that P(n) is true for every n > 2, where P(n) is the statement: n is either a prime or a product of two or more primes. 04
(c) Define a CFG for language having strings with equal number of 0’s and 1’s. L={x €{01}* |no(x) =ni(x)} 07
OR
L1 is a language over {0, 1}* that accepts strings ending in 11. L2 is a language over {0, 1}* that accepts strings containing 101 as sub-string. Write the regular expressions, draw FA for L1 and L2 and derive FA for L1 U L2. 07
--- Content provided by FirstRanker.com ---
Apply the subset construction technique to convert the given NFA to FA.
Q.3
(a) What is an Ambiguous CFG? Explain with reference to dangling else problem. 03
(b) Explain Moore machine and Mealy machine. Give example of two equivalent machines of each type performing similar function. 04
(c) Derive a CFG equivalent to following regular expression (011 + 1)*(01)* 07
--- Content provided by FirstRanker.com ---
OR
Q.3
(a) What are Nullable variable in a CFG? How can we remove them from a production? 03
(b) Draw NFA-? for ((0+1)*10 + (00)*(11)*)* 04
(c) What are the steps to convert a CFG to Chomsky Normal Form? 07
--- Content provided by FirstRanker.com ---
Q.4
(a) Define a Turing Machine. 03
(b) What language will be generated by this CFG: 04
S?aT|bT|?
T?aS|bS
--- Content provided by FirstRanker.com ---
(c) Develop a DPDA that accepts following language: L={x €{a,b}* |na(x) >nb(x)} 07
OR
Q.4
(a) What is the difference between accepting a Language and Recognizing a Language? 03
(b) Give transition tables for PDA recognizing the language of all non-palindromes over {a,b}* 04
--- Content provided by FirstRanker.com ---
(c) Write the pumping lemma for Context-Free Languages and prove that L = { aibici|i > 1} is not a CFL. 07
Q.5
(a) Define Primitive Recursive Functions. 03
(b) Draw a Turing Machine to accept a regular language {a, b}*{aba} 04
(c) Develop a Turing Machine to accept even length palindromes over {a,b}* 07
--- Content provided by FirstRanker.com ---
OR
Q.5
(a) Define Bounded Minimalization of a predicate P. 03
(b) What important points do we derive from Church-Turing thesis? 04
(c) Develop a Turing Machine that creates a copy of its input string to the right of the input, but with a blank space separating the copy from the original. 07
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU BE 2020 Summer Question Papers || Gujarat Technological University
--- Content provided by FirstRanker.com ---