N Nexsus

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

MMMUT Computer Science and Engineering previous year question paper for Theory Of Computation (BCS-213), semester 3, Major (End Semester) 2024. 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) 2024
  • Questions: 19

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

  1. Q1(a). Draw a DFA to accept the language: L = {w: w has even number of 1's followed by odd number of 0's}. [2 marks]
  2. Q1(b). Draw a NFA to accept the language: L = {w: w has arbitrary number of 0's followed by arbitrary number of 1's followed by arbitrary number of 2's}. [2 marks]
  3. Q1(c). Using pumping lemma, show that L = {ww^R : w in (a+b)*} is not regular. [2 marks]
  4. Q1(d). Explain the Myhill-Nerode theorem by taking a suitable example. [2 marks]
  5. Q1(e). Discuss in brief about the applications and limitations of finite automata. [2 marks]
  6. Q1(f). Show the equivalence of NFA and DFA by taking a suitable example. [2 marks]
  7. Q1(g). Write regular expressions for the following languages over the alphabet, Sigma = {a, b}. i. The language has all strings that do not end with ab. ii. The language has all strings that contain an even number a's. [2 marks]
  8. Q2(a). Give context free grammars that generate the following languages. (i) {w in {0,1}* | w contains at least three 1's} (ii) {w in {0,1}* | w = w^R and |w| is even. } (iii) {w in {0,1}* | the length of w is odd and the middle symbol is 0 } (iv) {a^i b^j c^k | i, j, k >= 0 and i + j = k } (v) {a^i b^j c^k | i, j, k >= 0 and i = j or i = k } [5 marks]
  9. Q2(b). Remove useless productions from the context free grammar given below. S -> AB | a, A -> BC | b, B -> aB | C, C -> aC | B [5 marks]
  10. Q2(c). Show that, acceptance by final state is equivalent to acceptance by empty stack in the context of Push Down Automata. [5 marks]
  11. Q3(a). Is the following Grammar ambiguous? Justify your claim. S -> aB | bA A -> aS | bAA | a B -> bS | aBB | b [5 marks]
  12. Q3(b). Convert the following CFG, G = (V, T, P, S), where V = {S, T, X}, Sigma = {a, b}, the start variable is S and the productions P are, S -> aTXb, T -> XTS | epsilon and X -> a | b to an equivalent PDA. [5 marks]
  13. Q3(c). Design Pushdown Automata that accept the following languages on Sigma = {0,1} , (i) L_1 = {w in {0,1}* : w contains at least three 1's} (ii) L_2 = {w : n_0(w) = n_1(w) + 1} [5 marks]
  14. Q4(a). Obtain a Turing machine to accept the language, L(M) = {0^n 1^n 2^n : n >= 1} [5 marks]
  15. Q4(b). Prove that the halting problem of Turing Machines is Undecidable. [5 marks]
  16. Q4(c). Explain Post's Correspondence Problem by taking a suitable example. [5 marks]
  17. Q5(a). Prove that, if a Language L and its complement L^C both are recursively enumerable then L is recursive. [5 marks]
  18. Q5(b). Write short notes on the following. (i) Multi-track Turing machine (ii) Nondeterministic Turing Machine (iii) Primitive Recursive Function (iv) Turing Decidable Language (v) Church-Turing Thesis [5 marks]
  19. Q5(c). Discuss about the basic primitive recursive functions and the operations defined on them [5 marks]