Skip to content
SmartFigureEdu

CS 3452 Theory of Computation question paper, November/December 2024

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 40923

B.E./B.Tech. DEGREE EXAMINATIONS, NOVEMBER/DECEMBER 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.

    Mention any four ways of theorem proving.

  2. 2.

    Define Finite Automata and give one example.

  3. 3.

    Is it True that the language accepted by any NFA is a regular language?

  4. 4.

    Define closure properties of regular languages.

  5. 5.

    What is the relationship between PDA and CFL?

  6. 6.

    What is an ambiguous grammar?

  7. 7.

    What is the height of the parse tree to represent a string of length 'n' using Chomsky Normal Form?

  8. 8.

    Give the logic to design a Turing Machine that accept the language of odd integers written in binary.

  9. 9.

    What is meant by undecidability of problem?

  10. 10.

    Give one example of an unsolvable problem.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Prove that for every integer n >= 0, the number 4^(2n+1) + 3^(n+2) is a multiple of 13 using mathematical induction Method.

  2. Or
  3. (b)

    Construct a Deterministic Finite State Automata that accepts the set of strings over {a,b} having an even number of a's and odd number b's, even number of a's and even number of b's, odd number a's and even number b's and odd number a's and odd number of b's.

  4. 12.
    (a)

    Two Regular languages is regular under the Union operation. Is the Union of a collection of Regular Language always Regular? Justify your answer. Compare your justification with the Intersection of Regular languages.

  5. Or
  6. (b)
    • (i)Explain pumping lemma of Regular languages.(5)
    • (ii)Show that L = {a^i b^i | i, j >= 1, i and j are not equal} is Not regular using Pumping Lemma.(8)
  7. 13.
    (a)

    Give a CFG to generate A = {a^i b^j c^k | i, j, k >= 0 and either i = j or j = k}. Is the grammar ambiguous? Why or why not?

  8. Or
  9. (b)

    Given Sigma{0, 1} Design a PDA

    • (i)Which accepts string of the form 1* 0^n 1^n(7)
    • (ii)Which accepts strings that contain twice as many zeros as ones.(6)
  10. 14.
    (a)

    Convert the following to CNF (Chomski Normal Form) S -> ABA, A -> aA | epsilon, B -> bB | epsilon

  11. Or
  12. (b)

    Construct a Turing Machine which will accept the set of strings over the alphabet {a, b} of the form a^n b^(3n).

  13. 15.
    (a)
    • (i)Discuss about Universal Turing Machines.(7)
    • (ii)Write short notes on P, NP class problems.(6)
  14. Or
  15. (b)

    Let l1 and l2 be any two undecidable languages. State and prove your answer to each of the following questions.

    • (i)Is it possible that L1 - L2 n is regular?(7)
    • (ii)Is it possible that L1 union L2 is in Decidable?(6)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Minimize the given Deterministic Finite Automaton using Myhill Nerode Theorem Method (Table Filling Method) States: 1, 2, 3, 4, 5, 6, 7, 8 and alphabets are {a, b}. [Figure: DFA with start state 1 and final state 3; transitions 1 -a-> 2, 1 -b-> 6, 2 -a-> 7, 2 -b-> 3, 3 -a-> 1, 3 -b-> 3, 4 -a-> 3, 4 -b-> 7, 5 -a-> 8, 5 -b-> 6, 6 -a-> 3, 6 -b-> 7, 7 -a-> 7, 7 -b-> 5, 8 -a-> 7, 8 -b-> 3]

  2. Or
  3. (b)

    Construct a Turing Machine to carry out division operation using Unary Numbers? {Example 6 divided by 2 = 3}.

Other CS3452 papers