N Nexsus

Theory Of Computation — Major (End Semester) 2023 question paper

MMMUT Computer Science and Engineering previous year question paper for Theory Of Computation (BCS-213), semester 3, Major (End Semester) 2023. All 19 questions are listed below, each with a written answer on Nexsus.

Paper details

  • Subject: Theory Of Computation (BCS-213)
  • Branch: Computer Science and Engineering
  • Semester: 3
  • Exam: Major (End Semester) 2023
  • Questions: 19

Questions asked in Theory Of Computation Major (End Semester) 2023

  1. Q1(a). Explain the Myhill-Nerode theorem by taking a suitable example. [2 marks]
  2. Q1(b). Draw a DFA to accept the language: L = {w:w has odd number of 1's followed by even number of 0's}. [2 marks]
  3. Q1(c). What is halting problem of Turing machines? Explain in brief. [2 marks]
  4. Q1(d). Discuss in brief about Church-Turing thesis. [2 marks]
  5. Q1(e). Obtain context free grammar to generate the language described below as, L = {w: number of a's in w is more than number of b's in w.} [2 marks]
  6. Q1(f). Discuss in brief about the following. (i) Chomsky Normal Form (ii) Greibach Normal Form (iii) Inherently ambiguous languages (iv) Unit Production [2 marks]
  7. Q1(g). Discuss in brief about the applications and limitations of finite automata. [2 marks]
  8. Q2(a). Obtain a DFA that accepts the set of all strings over the alphabet {a,b}, such that the number of a's is divisible by 2 and the number of b's is divisible by 3. [5 marks]
  9. Q2(b). Draw a NFA to accept the language: L = {w: w has arbitrary number of a's followed by arbitrary number of b's followed by arbitrary number of c's followed by arbitrary number of d's} [5 marks]
  10. Q2(c). Prove the equivalence of NFA and DFA by taking a suitable example. [5 marks]
  11. Q3(a). Using pumping lemma, show that the language L= {ww': we (a+b); is not regular. [5 marks]
  12. Q3(b). Write regular expressions for the following languages over the alphabet, ∑ = {a,b} i. All strings that do not end with ab. ii. All strings that contain an even number a's. iii. All strings which do not contain the substring ba iv. All strings which start and end with the same symbol V. All strings which start and end with different symbol [5 marks]
  13. Q3(c). Compare and contrast between Moore and Mealy machines by taking suitable examples. [5 marks]
  14. Q4(a). Is the following Grammar ambiguous? Justify your claim. SaBbA, AaS | BAA | a, BbS | aBB | b [5 marks]
  15. Q4(b). Eliminate unit productions from the grammar given below. S→AB, A→a, B→C|b, C→D, D→ E | bC and E→ d Ab [5 marks]
  16. Q4(c). Obtain a PDA to accept the language L = {w: we (a+b)* and na(w) < no(w) } [5 marks]
  17. Q5(a). Prove that, if a Language L and its complement both are recursively enumerable then L is recursive as well. [5 marks]
  18. Q5(b). Write short notes on the following. (i) Multitape Turing machine (ii) Church Thesis (iii) Recursive language [5 marks]
  19. Q5(c). Obtain a Turing machine to accept the language L(M) = { 0^n1^n2^n: n ≥1} [5 marks]