Skip to content
SmartFigureEdu

CS 3452 Theory of Computation question paper, April/May 2024

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 50903

B.E./B.Tech. DEGREE EXAMINATIONS, APRIL/MAY 2024.

Fourth Semester

Computer Science and Engineering

CS 3452 — THEORY OF COMPUTATION

(Common to : Computer Science and Engineering (Artificial Intelligence and Machine Learning)/Computer Science and Engineering (Cyber Security)/Information Technology)

(Regulations 2021)

Time : Three hoursMaximum : 100 marks

Answer ALL questions.

PART A — (10 × 2 = 20 marks)

  1. 1.

    How will you prove the group of statements together? Justify.

  2. 2.

    Draw the transition diagram to recognize a constant.

  3. 3.

    Write the regular expression for the language L = {Set of string with even number of 1's followed by odd number of 0's}.

  4. 4.

    Let Sigma = {0, 1} and Sigma' = {a, b, c} with h(0) = ab, h(1) = ac. Find homomorphic image of L = {010, 0010, 1010}.

  5. 5.

    Write the Chomsky hierarchy of grammar.

  6. 6.

    Mention the language accepted by empty stack and final state.

  7. 7.

    What is meant by reachable symbol?

  8. 8.

    List any four closure properties of CFL.

  9. 9.

    When do you say a problem is decidable? Give example.

  10. 10.

    What is intractable problem? Give example.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)
    • (i)Prove that the statement "if n >= 5, then n can be written as a sum of 2's and 3's" by inductive principle.(7)
    • (ii)Construct a DFA that accepts the string over an alphabet {0,1}, number of 0's is multiples of 3.(6)
  2. Or
  3. (b)
    • (i)In Fig. 11(b), find the equivalent DFA for the following NFA. [Fig. 11(b): NFA with start state p and final state s; p -0,1-> p, p -0-> q, q -0,1-> r, r -0-> s, s -0,1-> s](7)
    • (ii)Prove that the language L is accepted by NFA with epsilon-transition, then there exist DFA also accept the same language L.(6)
  4. 12.
    (a)
    • (i)From Fig. 12(a), find the regular expression for the following DFA. [Fig. 12(a): DFA with start state q0 and final state q2; q0 -0-> q1, q0 -1-> q2, q1 -0-> q0, q1 -1-> q2, q2 -0-> q1, q2 -1-> q0](8)
    • (ii)Construct an NFA for the regular expression (01+10)* 10*.(5)
  5. Or
  6. (b)
    • (i)Show that the language L = {0^n 1^(2n) | n > 0} is not regular.(8)
    • (ii)Prove if L and M are regular language, then so is L-M.(5)
  7. 13.
    (a)
    • (i)Construct a PDA that accept the language L = {a^m b^n c^n d^m | n, m >= 1} by empty stack.(7)
    • (ii)Prove that if PDA P is constructed from CFG G, then L(P) = L(G).(6)
  8. Or
  9. (b)
    • (i)Construct a CFG G which accepts the language L(M) where M = ({q0, q1}, {a, b}, {z0, z}, delta, q0, z0, phi) where delta is given by delta(q0, a, z0) = (q0, zz0); delta(q0, a, z) = (q0, zz); delta(q0, b, z) = (q1, epsilon); delta(q1, b, z) = (q1, epsilon); delta(q1, epsilon, z) = (q1, epsilon); delta(q1, epsilon, z0) = (q1, epsilon)(7)
    • (ii)Grammar G : S -> S1S | 0, Is this grammar G is ambiguous? Justify.(6)
  10. 14.
    (a)
    • (i)Convert the CFG into CNF S -> AB, A -> aAA | epsilon, B -> bBB | epsilon(8)
    • (ii)Prove that L = {a^n | n is perfect square} is not context free.(5)
  11. Or
  12. (b)
    • (i)Design a Turing Machine to compute f(m, n) = m - n, if m >= n; = 0, if m < n(8)
    • (ii)Explain the programming techniques for Turing Machine.(5)
  13. 15.
    (a)
    • (i)Let Sigma = {0,1}, Let A and B be the list of string defined as [Table: i - List A (wi) - List B (xi): 1 - 1 - 10; 2 - 110 - 0; 3 - 0 - 11] Find the instance of MPCP.(7)
    • (ii)Show that 3-CNF SAT is NP complete.(6)
  14. Or
  15. (b)

    Find the following languages are recursively enumerable.

    • (i)Union of recursively enumerable languages.(7)
    • (ii)L and complement of L are recursively enumerable.(6)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Construct a minimal state DFA and find the regular expression for the DFA. [Figure: DFA with start state A and final states C, F and I; A -0-> B, A -1-> E, B -0-> C, B -1-> F, C -0-> D, C -1-> G, D -0-> E, D -1-> H, E -0-> F, E -1-> I, F -0-> G, F -1-> B, G -0-> H, G -1-> B, H -0-> I, H -1-> C, I -0-> A, I -1-> E]

  2. Or
  3. (b)

    Construct a Turing Machine to implement the multiplication operation f(m,n) = m*n, where m and n are positive numbers and simulate their action as input 5*4.

Other CS3452 papers