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

Enrolment No.___________

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**BE - SEMESTER? VI EXAMINATION ? SUMMER 2020**

**Subject Code: 2160704**

**Date:28/10/2020**

**Subject Name: THEORY OF COMPUTATION**

**Time: 10:30 AM TO 01: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)**What is a proposition? Which logical connectives do we use to generate

**03**

compound proposition?

**(b)**Out of these two statements which one is true and which is false. Justify your

**04**

answer.

1. ((( - )2 < 4 ))

2. ((( - )2 < 4 ))

**(c)**Develop an FA corresponding to following regular expression

**07**

= (11 + 110)0

Explain the properties of Distinguishability of Strings and Equivalence

classes, show minimum numbers of states necessary for this FA.

**Q.2 (a)**Write the strong principle of mathematical induction and show that () is

**03**

true for every 2, where () is the statement: n is either a prime or a

product of two or more primes.

**(b)**Define a CFG for language having strings with equal number of 0's and 1's.

**04**

= { {0,1} | 0() = 1()}

**(c)**L1 is a language over {0, 1}* that accepts strings ending in 11. L2 is a

**07**

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.

**OR**

**(c)**Apply the subset construction technique to convert the given NFA to FA.

**07**

1

**Q.3 (a)**What is an Ambiguous CFG? Explain with reference to dangling else

**03**

problem.

**(b)**Explain Moore machine and Mealy machine. Give example of two

**04**

equivalent machines of each type performing similar function.

**(c)**Derive a CFG equivalent to following regular expression

**07**

(011 + 1)(01)

**OR**

**Q.3 (a)**What are Nullable variable in a CFG? How can we remove them from a

**03**

production?

**(b)**Draw NFA- for ((0+1)*10 + (00)*(11)*)*

**04**

**(c)**What are the steps to convert a CFG to Chomsky Normal Form?

**07**

**Q.4 (a)**Define a Turing Machine.

**03**

**(b)**What language will be generated by this CFG:

**04**

S aT | bT |

T aS | bS

**(c)**Develop a DPDA that accepts following language:

**07**

= { {, } |() > ()}

**OR**

**Q.4 (a)**What is the difference between accepting a Language and Recognizing a

**03**

Language?

**(b)**Give transition tables for PDA recognizing the language of all non-

**04**

palindromes over {a,b}*

**(c)**Write the pumping lemma for Context-Free Languages and prove that =

**07**

{ | 1} is not a CFL.

**Q.5 (a)**Define Primitive Recursive Functions.

**03**

**(b)**Draw a Turing Machine to accept a regular language

**04**

{a, b}*{aba}

**(c)**Develop a Turing Machine to accept even length palindromes over {a,b}*

**07**

**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

**07**

of the input but with a blank space separating the copy from the original.

*****************

2

This post was last modified on 04 March 2021