BSc CS Sem 4 Theory of Computation Question Paper PDF - Mumbai University | munotes

Questions asked in this paper

1. Q2 All questions carry equal marks Attempt the following (Any FOUR) (20M)
   • (a) Write a short note on Deterministic Finite Automaton
   • (b) Consider a Mealy Machine described by the transition table given below Construct a Moore Machine equivalent to Mealy Machine Present Next State
   • (c) For the Finite State Machine M, find the acceptibility of the strings
   • ii) 11001100
   • iii) 10100101
   • iv) 11100011 a (d) If G=({S}, {0,1},P,S) where P consists of S->0S1 | 0 | 1B | 1, 0, Let | m>=0 and n>0} Find grammar for it.
   • (f) Write a note on —
   • i) Type 0 Grammar
2. Q2 Attempt the following (Any FOUR) (20M)
   • (a) Find a reduced grammar equivalent to the grammar G, having production
   • (b) a PDA that accepts L={0"1" | n>=0} VCD- of Computation-75 MKS- 2'? HRS
   • (c) Find out below Automaton M1 and M2 are equivalent to each other or not
   • (d) Explain the Identities for Regular Expressions
   • (e) What is ambiguity in Context Free Grammar? If G is the Grammar whose production rule is S->SbS | a. Show that G is ambiguous
   • (f) Construct a Regular Expression corresponding to the state diagram described in figure below
3. Q3 Attempt the following (Any FOUR) (20M)
   • (a) Write a note on Linear Bound Automata model
   • (b) Consider the Turing Machine M described by the transition table given below. Describe the processing of string 0011
   • (c) Explain Mutlitape and Multitrack variant of Turing Machine
   • (d) Write a note on Language Decidability
   • (f) What is halting problem of Turing Machine? VCD- of Computation-75 MKS- 2'” HRS
4. Q4 Attempt the following (Any FIVE) (15M)
   • (a) Construct a deterministic finite automaton equivalent to, Where is given by,
   • (b) Write note on Phase Structure Grammar
   • (c) Describe following sets by regular expression
   • i) Set of all strings of 0’s and 1’s ending in 00
   • ii) Set of all strings of 0’s and 1’s beginning with 0 and ending with 1
   • iii) Set of all strings of 0’s and 1’s whose length is odd
   • (d) What is derivation tree? Define Leftmost Derivation Tree and Rightmost
   • (e) Explain transition table representation method of Turing machine
   • (f) Write note on Turing Machine

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