B.Sc. (Computer Science) Sem 4 Theory of Computation Apr 2024 Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Attempt any four: 20 marks
   • A) Give the formal/mathematical of a DFA. Explain each term
   • B) Design a DFA for all strings in which every 00 is immediately followed by a 1
   • C) For {a, b}, construct a DFA that accepts the sets consisting of all strings with no more than two a’s
   • D) Construct a Moore: Machine to compute the number of substrings of the form bab, that occur in an arbitrary input string, over the alphabet {a,b} and output alphabet {0,1}
   • E) Design a DFA for tthe language L = { awa: w b}*}
   • F) Design a DFA for accepting strings only if its is a multiple of 4
2. Q2 Attempt any four: 20 marks
   • A) Construct a CFG to generate the set of all balanced parenthesis over the alphabet =
   • B) Construct a grammar which generates all odd integers less than four digits
   • C) Show that L = { atwhere t =i? and i>=1} is not regular
   • D) Describe the following regular expression in English: 00*11*22*. Also give five strings from the above set
   • E) Remove all the null productions and rewrite the: prodvction rules: B>bB, Cc. Show all the steps
   • F) Remove ali unit productions and rewrite the production rules: S-XY, Xa, Y>Z|b, Show all the steps
3. Q3 Attempt any four: 20 marks
   • A) Give the formal/mathematical specification of a Turing machine. Explain each term
   • B) Explain the three components of a Turing machine with the help ofa diagram
   • C) Design a TM that accepts the language of all strimgs, over the alphabet = {a, b}, whose second letter is b
   • D) Explain the variants of the Turing machine
   • E) State the Church-Turing thesis
   • F) Design a TM that erases all non-blank symbols on the tape, over the alphabet 2 = {a, b}
4. Q4 Attempt any five: 15 marks
   • A) Design an appropriate machine to add two binary numbers
   • B) Give the Chomsky classification of
   • C) What are context-free grammar and language? Give examples
   • E) Explain the halting problem
   • F) Give a grammar for a valid identifier in Java pr ogramming language

Read from the scan above, so a character or two may differ. The scan is the original.