Theoretical Computer Science Past Paper PDF - 2022

# Paper / Subject Code: 31921 / Theoretical Computer Science T.E. SEM V COMP / R-2019 / NOV 2022/22.11.2022 ## Time: 3.00 Hrs. Marks: 80 **N.B.:** * Question No. 1 is compulsory. * Attempt any three questions out of the remaining five questions. * Assumptions made should be clearly stated. * Figur...

# Paper / Subject Code: 31921 / Theoretical Computer Science T.E. SEM V COMP / R-2019 / NOV 2022/22.11.2022 ## Time: 3.00 Hrs. Marks: 80 **N.B.:** * Question No. 1 is compulsory. * Attempt any three questions out of the remaining five questions. * Assumptions made should be clearly stated. * Figures to the right indicate full marks. * Assume suitable data whenever required but justify the same. ## 1. a) Differentiate between NFA and DFA. b) Compare and contrast Moore and Mealy machines. c) Explain variants of Turing Machine. d) Show that the following grammar is ambiguous : S --> aSbS | bSaS | ε ## 2. a) Convert the following RE into NFA with ε- moves and hence obtain the DFA : RE= (0+ ε) (10)*(ε+1). b) Consider the following grammar G = {V, T,P,S), V={S,X},T={a,b} and productions P are : S-->aSb | aX X --> Xa | Sa|a. Convert the grammar in Greibach Normal Form. ## 3. a) Construct PDA accepting the language L = { a²"b" | n >= 0 b) Construct TM to check well formedness of parenthesis. ## 4. a) Design Mealy machine to recognize r = (0+1)*( 00 + 1) and then convert it to Moore machine. b) Consider the following grammar: S-->iCtSiCtSeSa C--> b. For the string "ibtaeibta", find the following * Left most derivation * Right most derivation * Parse tree * Check if the above grammer is ambiguous or not ## 5. a) Design a Turing machine that computes a function f(m,n) = m + n, the addition of two integers. b) Give the formal definition of pumping lemma for regular language and then prove that the following language is not regular : L = { 0m1m+1 | m > 0 }. ## 6. **Write short note on following (Any two):** * Chomsky Hierarchy * Decision properties of regular languages. * Rice's theorem. * Definition and working of PDA. 12579 1 0312BDEBF29D5FE7342449F41E2E32A5