Skip to content
SmartFigureEdu

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

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 30123

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

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.

    Differentiate NFA and DFA.

  2. 2.

    Convert the given NFA to an DFA. [Figure: NFA with states 1 and 2; state 1 is the start state and the final state; 1 -a-> 1, 1 -a,b-> 2, 2 -b-> 1]

  3. 3.

    Prove that reversal of any regular language is also regular.

  4. 4.

    Write a regular expression that recognizes the set of all strings (0+1)* that do not contain the substrings 00 and 11 over the alphabet Sigma = {0, 1}.

  5. 5.

    State the Pumping Lemma for Context Free Languages.

  6. 6.

    What is a Deterministic Push Down Automata?

  7. 7.

    Give the instantaneous description of a TM.

  8. 8.

    What do you mean by useless symbol? Explain with an example.

  9. 9.

    When is a language L recursively enumerable?

  10. 10.

    What are tractable problems?

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Construct NFA accepting the set of strings Sigma = {0, 1} such that two 0's are separated by a string whose length is 4i, for some i>=0.

  2. Or
  3. (b)

    Prove that for every L recognized by an NFA, there exists an equivalent DFA accepting the same language L.

  4. 12.
    (a)

    Prove that regular expressions are closed under union, concatenation, Kleene closure, complement.

  5. Or
  6. (b)

    Prove that any language accepted by a DFA can be represented by a regular expression and also construct a finite automata for the regular expression 10+(0+11)0*1.

  7. 13.
    (a)

    Let G = (V, E, R, S) be the CFG, where V = {A, B, S}, E = {a, b}, S is the start variable and R consists of the rules S -> aB | bA, A -> a | aS | BAA, B -> b | bS | ABB

    • (i)Prove that ababba in L(G)(7)
    • (ii)Prove that L(G) is the set of all non-empty strings w over the alphabet {a, b} such that the number a's in w is equal to the number of b's in w.(6)
  8. Or
  9. (b)
    • (i)Design a PDA that will accepts strings (a+b)* in which the number of a's is greater than the number of b's given the alphabet Sigma = {a, b}.(7)
    • (ii)Convert the above PDA to its equivalent CFG.(6)
  10. 14.
    (a)
    • (i)Convert the following grammar to CNF S -> ASB | epsilon, A -> aAS | a, B -> SbS | A | bb(7)
    • (ii)Design a Turing machine to compute proper subtraction.(6)
  11. Or
  12. (b)
    • (i)Convert the following grammar to GNF A1 -> A3A2 | A2A3, A2 -> A3A3 | A2A2 | a, A3 -> A2A2 | b(7)
    • (ii)Design a Turing machine that takes a binary number as input and increments the number by 1.(6)
  13. 15.
    (a)
    • (i)Prove that Post Correspondence Problem is undecidable.(7)
    • (ii)Write short notes on P and NP completeness.(6)
  14. Or
  15. (b)
    • (i)Explain about Universal Turing Machine.(7)
    • (ii)Discuss Travelling Salesman Problem in terms of P and NP completeness.(6)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Consider the NFA N = (Q, Sigma, delta, q, F), where Q = {1, 2, 3}, Sigma = {a, b}, q = 1, F = {2}, and delta is given by the following table: [Table: state - a - b - c: 1 - {3} - phi - {2}; 2 - {1} - phi - phi; 3 - {2} - {2, 3} - phi] Convert the NFA (N) into DFA (M) that accepts the same language.

  2. Or
  3. (b)
    • (i)Write the regular expression for the set of all strings of 0's and 1's not containing 101 as substring.(5)
    • (ii)Design a Turing machine to recognize the language {0^n 1^n 0^n | n >= 0}.(10)

Other CS3452 papers