Dr.A.P.J.Abdul Kalam University BE V SEM ALL BRANCH Theory of Computation [CS-505] Dec - 2020 Question Paper

Dr.A.P.J.Abdul Kalam University 

Bachelor of Engineering

Fifth Semester Main Examination, Dec-2020

Theory of Computation [CS-505]

Branch: CSE

Time: 3:00 Hrs Max Marks 70

Note : 1. Attempt any five questions out of eight.

2. All question carry equal marks.

Q.1 (a) Define language and Grammar give an example.

(b) Proof the equivalence of NFA and DFA? Write an example, which proof the conversion

from NFA to DFA?

Q.2 (a) Define Regular Expression. List the operators of Regular Expressions.

 (b) Explain Chomsky classification of Grammars.

Q.3 (a) Construct a minimal DFA, which accept set of all input strings over {0,1}, which when interpreted as

a binary number is divisible by 3.

 (b) Equivalence between Moore and Mealy machine-proof with example?

Q.4 (a) What is a context free grammar and explain closure properties of context free grammar?

 (b) Give the English description of the language of the following regular expression.

(i) (1+є) (00* 1)* 0

* (ii)(0+10)*1*

Q.5 (a) Demonstrate the working of your Turing Machine with example?

(b) Define a Deterministic Pushdown Automata for the string over {a,b} equal no. of a’s & b’s .

Q.6 (a) Explain with example Chomsky Normal form and Greibach Normal forms.

 (b) Obtain an NFA for the regular expression (a+b)*

aa (a+b)*

Q.7 (a) Convert the regular expression r=(11+0)*(00+1)* to є move.

 (b) Explain in detail notes on Universal Turing Machine with example?

Q.8 Short note on: (Any three define with example)

 (i) Traveling salesman problem

 (ii) NP Complete NP hard problems

 (iii) Hamiltonian path problem

 (iv) Regular Sets and Regular Grammars

Attachment & Scanned Copies:

Share This