B.Sc. (Computer Science) Sem 3 Theory of Computation Oct 2025 Question Paper - Mumbai University | munotes

Questions asked in this paper

SECTION I - Q1) (Attempt any two) 10 Marks

1. A) Explain uses of Automata.
   Read the model answer
2. B) Construct a Moore machine that takes set of all strings over {a, b} and count number of occurrence of substring 'baa'.
   Read the model answer
3. C) What is a derivation tree? Explain it with example.
   Read the model answer
4. D) Show that grammar is ambiguous: G : S -> aB | ab, A -> aAB | a, B -> ABb | b
   Read the model answer

SECTION II - Q2) (Attempt any two) 10 Marks

1. A) Explain Turing machine construction techniques.
   Read the model answer
2. B) Design Turing machine that accepts { a^n b^n | n >= 1 }.
   Read the model answer
3. C) Write a short note on Recursive Enumerable Languages.
   Read the model answer
4. D) Write a short note on Linear Bound Automaton and Linear Bound Automaton Model.
   Read the model answer

SECTION III - Q3) (Attempt any two) 10 Marks

1. A) Construct NFA that accepts set of all strings over {0, 1} of length 2. Σ = {0, 1}, L = {00, 01, 10, 11}
   Read the model answer
2. B) Find reduced grammar equivalent to the grammar G whose productions are, S -> AB | CA, B -> BC | AB, A -> a, C -> aB | b
   Read the model answer
3. C) Write Arden's Theorum.
   Read the model answer
4. D) What are the languages accepted by Linear Bound Automaton.
   Read the model answer

Read from the scan above, so a character or two may differ. The scan is the original.