Skip to content
SmartFigureEdu

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

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 20870

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

    Identify NFA-epsilon to represent a*b|c.

  2. 2.

    Let L be a set accepted by a non-deterministic finite automaton. The number of states in non-deterministic finite automaton is 'N'. Find the maximum number of states in equivalent finite automaton that accepts L.

  3. 3.

    Recall the term "Regular Expression". Give a Regular Expression for any language containing symbols (0, 1) and strictly ends with '1'.

  4. 4.

    Given the following two languages: L1 = {a^n b a^n | n > 0} L2 = {a^n b a^n b^(n+1) | n > 0} Check whether the above languages are context-free or not.

  5. 5.

    Mention a few points regarding Chomsky's hierarchy with illustration.

  6. 6.

    Examine the context free Grammar representing the set of Palindrome over (0+1)*.

  7. 7.

    Tabulate the difference between Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).

  8. 8.

    Give the philosophy behind Pumping lemma for CFLs.

  9. 9.

    List down a few properties of recursively enumerable set.

  10. 10.

    Define Class P and NP problems. Give examples.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Construct a DFA for the following Language and check whether w = '01101' is a valid string or NOT. L(G) = {w | w in (0,1) and w starts with 0 and has odd length or it starts with 1 and has even length}.

  2. Or
  3. (b)

    Explain the DFA minimization algorithm with an example.

  4. 12.
    (a)

    Prove that the set of regular languages is closed under complementation. (i.e., If L a regular language then L' is also a regular language). Give an example.

  5. Or
  6. (b)

    How to determine in two Regular Expressions are equivalent or NOT? Are (a*) and (epsilon + aa*) equivalent wrt. Sigma = {a,b}?

  7. 13.
    (a)

    Construct a CFG for the language given below. L(G) = {w | w in (a,b)+ and w is an odd length palindrome}. Also check whether w = 'babab' is a valid string or not.

  8. Or
  9. (b)

    Construct an empty store PushDown Automata(PDA) for the below mentioned language: L(G) = {w | w in (a,b)} and w is of the form a^n b^n and n >= 1}. Also mention the state transitions of this PDA while parsing the string w = 'aaabbb'.

  10. 14.
    (a)

    Demonstrate the working model of a Turing machine to perform proper subtraction.

  11. Or
  12. (b)

    Construct a Turing machine to accept the following language. L(G) = {w | w in (0,1) and w is of the form 0^n 1^n where n >= 1}

  13. 15.
    (a)

    Give short notes on Recursive and Recursive Enumerable languages.

  14. Or
  15. (b)

    Explain the philosophy behind Travelling salesman problem (TSP). Analyze the computational complexity for the same. Show how the decision version of the TSP belongs to the class of NP-Complete problem.

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Construct an empty store PushDown Automata(PDA) for the below mentioned language: L(G) = {w | w in (a,b,c) and w is of the form XcX', where X' is the reversed string of X and X in (a,b)}. Also mention the state transitions of this PDA while parsing the string w = 'baacaab'.

  2. Or
  3. (b)

    Construct a PushDown Automata(PDA) for the below mentioned language: L(G) = {w | w in (a,b,c,d) and w is of the form a^n b^m c^m d^n and (m,n) >= 1}. Also mention the state transitions of this PDA while parsing the string w = 'aaabbccddd'.

Other CS3452 papers