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

Questions asked in this paper

1. Q1 All are compulsory
2. Q2 Mixing of questions is not allowed
3. Q3 Write in clecir, legibla, writing Attempt any four: (20)
   • A) What are sets? Explain various set operations
   • B) Explain the concept of graphs and trees in brief
   • C) What are the rroofing techniques?
   • a) Proof by contradiction
   • b) Proof by Induction
   • D) What is a string? explain basic cencepts of strings
   • E) What is a language? Explain the types of operation: on th
   • F) What is automation? Attempt any four: (20)
   • A) Write in brief note on characteristics of automation
   • B) a transition system? C} Write a brief note about finite
   • D) Define DFA {deterministic finite automata)
   • E) Write in brief about NDFA {non deterministic finite
   • F) Write the steps to convert to DFA Attempt any four: (20)
   • A) What is mealy- machine?
   • B) What is More-machinc?
   • C) Conversion of mvaly into more
   • D) Conversion of more into mealy Write the steps to convert DFA te NDFA
   • F) Explain Transition States Attempt any five: A} Write components of grammar. Explain with the help of an example
   • C) Write in brief about right linear grammar and left linear grammar What are the different performed on the language
   • E) Write a primitive expression
   • F) Write the rules for regular

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