BSc CS Sem 3 BSc CS Semester 3 (2019 2020) Oct 2020 THEORY OF COMPUTATION Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate marks

1. Q3 in-depth answers and diagrams will be appreciated
2. Q4 Mixing of sub-questions is not allowed
3. Q1 Attempt All(Each of 5Marks) (15M)
   • (a) Multiple Choice Questions
4. Q1 Language of finite automata is
5. Q2 Regular expression for all strings starts with ab then any number of a or b and ends with bba All of the above
6. Q3 Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular
   • a) true b) false
7. Q4 machine, the O/P depends upon?
   • a) State b) Previous State State and Input d) Only Input
8. Q5 Language if and only If the set of classes of L
   • (b) Fill in the blanks
9. Q1 The major difference between Mealy and Moore machine is about
10. Q2 Concatenation of R with outputs
11. Q3 The difference between number of states with regular expression (a + b)
12. Q4 The entity which generates Language is
13. Q5 The Grammar can be defined as: G=(V, >, p, S). In the given definition,
    • (c) Short Answers
14. Q1 Define Moore Machine
15. Q2 Define Parse tree
16. Q3 Define reverse substitution
17. Q4 Define -transition
18. Q5 What are different techniques to represent Turing machine?
19. Q2 Attempt the following (Any THREE)(Each of 5Marks) (15M)
    • (a) Write short note on transition system with its notations
    • (b) Prove that for any transition function 6 & for any two input string x&y,
    • (c) Consider following Grammar G where P consists of
    • a] the Test whether girl with a flower likes the boy” is in L(G)
    • (d) Construct a Moore machine which is equivalent to the Mealy machine
    • (e) Construct DFA equivalent to the NDFA whose transition diagram is given
    • (f) Define Grammar. Consider G =({ S. /a, b}, P, S), where ? consists of S->
20. Q3 Attempt the following (Any THREE) (Each of 5Marks)
    • (a) What is formal definition of Regular Expression? Explain its order of
    • (b) State Andren’s Theorm. Prove equivalence of
    • (c) Consider following to generate NFA
    • (d) Construct a DFA with reduced state equivalent to following Regular Expression
    • (e) What is derivation? What are different types of derivation? Draw a parse tree for input string
    • (f) Write a short note on Greibach Normal form
21. Q4 Attempt the following (Any THREE) (Each of 5Marks) (15M)
    • (a) Explain Turing Machine representation by instantaneous descriptions using
    • (b) Explain model of Linear Bounded Automata
    • (c) Write short note on variant of Turing machine
    • (d) What is Halting problem of Turing Machine?
    • (e) What are Unsolvable problems?
    • (f) How to design Turing Machines? Design a TM to recognize all strings consisting of an even number of 1’s the following (Any THREE) (Each of 5Marks) (15M)
    • (a) Consider the finite machine whose transition function 6 is given by following transition table. Here, O= q3}, L= {0, 1},F= {q0} Give the entire sequence of states for the input string 110001
    • (b) Describe following set by Regular Expression L1=set of all strings of 0’s & 1’s ending in 00 L2=set of all strings of 0’s &1’s which begins with 0 and ends with i, L4=set of all stings whose length is exactly 4,
    • (c) Explain Turing Machine Model
    • (d) State the process of minimization of automata Consider following automata & minimize the states and draw DFA,
    • (e) Explain Pumping lemma and its various applications,

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