Dr. A.P.J. Abdul Kalam University MCA III SEM Theory of Computation [MCA304] Dec 2020 Question Paper

Dr. A.P.J. Abdul Kalam University

Master of Computer Application

Third Semester Main Examination, Dec-2020

Theory of Computation [MCA304]

Time: 3:00 Hrs Max Marks 70

Note: Answer any five questions. All questions carry equal marks.

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

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

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) (a+є) (aa* b)*

a

* (ii) (a+ba)*b*

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) CFG

(ii) NP Complete NP hard problems

(iii) Hamiltonian path problem

 (iv) Regular Sets and Regular Grammars

Scanned Copies:

Share This