Scribd
Upload
54 views2 pages

mca-304-theory-of-computation-jun-2020

The document is an examination paper for the MCA-304 Theory of Computation course from June 2020, consisting of eight questions. Students are required to attempt any five questions, covering topics such as Moore and Mealy machines, finite automata, context-free grammars, pushdown automata, Turing machines, and undecidability. Each question carries equal marks, and the paper includes both theoretical and practical components related to computation theory.

Uploaded by

oxfordmeera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views2 pages

mca-304-theory-of-computation-jun-2020

The document is an examination paper for the MCA-304 Theory of Computation course from June 2020, consisting of eight questions. Students are required to attempt any five questions, covering topics such as Moore and Mealy machines, finite automata, context-free grammars, pushdown automata, Turing machines, and undecidability. Each question carries equal marks, and the paper includes both theoretical and practical components related to computation theory.

Uploaded by

oxfordmeera
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

https://www.rgpvonline.

com

Total No. of Questions : 8] [1] [Total No. of Printed Pages : 2

Roll No ..................................

MCA-304
M.C.A. III Semester
Examination, June 2020
Theory of Computation
Time : Three Hours
Maximum Marks : 70
Note : i) Attempt any five questions.
ii) All questions carry equal marks.

1. a) Construct Moore machine to calculate residue mod 5 for


each binary string treated as binary integer.
n n ( n + 1)
b) Prove by principle of induction ∑i = 2
.
i =1

2. a) Design Finite automata for the given regular expression


( a + b ) * ba .
b) What are the basic difference between Mealy machine
and Moore machines? How a Moore machine can be
converted into a mealy machine?

3. a) State and prove Pumping lemma for regular sets. What


are its applications?
b) Show that regular languages are closed under union,
concatenation, complement and intersection.

4. a) Construct a CFG (Context Free Grammar) for the


following languages
i) L = a nb 2 n c m d 3m n, m > 1

ii) L = a nb m c m d n n, m > 1
MCA-304 PTO

https://www.rgpvonline.com
https://www.rgpvonline.com

[2]

b) Convert the following Grammar into GNF


E→E+T T
T→T * F F
F → (E) a

5. a) For all string ‘s’ over the alphabet {0, 1} construct a PDA
to accept ‘s’ where s = Reverse (s).
b) Show that for every context free language there exist an
accepting PDA.

6. a) Construct Turing Machine for following language


i) Reverse of string i.e. f ( w ) = W R W ∈ {a, b} *
b) What is Halting problem of Turing machines and what is
its significance? Explain.

7. a) Find the context sensitive grammar for the following


language
L = a nb n c n n ≥ 1
b) What is Undecidability? Describe post correspondence
problem.

8. Write short notes on any three of the following:


a) Linear Bounded Automata
b) 2DFA
c) Chomsky classification
d) CNF
e) Recursively enumerable sets

******
MCA-304 PTO

https://www.rgpvonline.com

You might also like