Monday, January 23, 2023

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


* (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
Previous Post
Next Post

B.E Civil Engineer Graduated from Government College of Engineering Tirunelveli in the year 2016. She has developed this website for the welfare of students community not only for students under Anna University Chennai, but for all universities located in India. That's why her website is named as . If you don't find any study materials that you are looking for, you may intimate her through contact page of this website to know her so that it will be useful for providing them as early as possible. You can also share your own study materials and it can be published in this website after verification and reviewing. Thank you!


Pen down your valuable important comments below

Search Everything Here