BSc CS Sem 3 BSc CS Semester 3 (2018 2019) 2019 Theory Of Computation Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate marks

1. Q3 Draw suitable diagrams and illustrations wherever necessary
2. Q4 Mixing of sub-questions is not allowed
3. Q1 Attempt All the Questions
   • A. Choose the correct alternative (SM)
   • i. An automaton in which the output depends only on the states of the machine is called a _ Machine
   • a) Mealy b) Moore
   • c) Turing Machine d) All of these
   • ii. A final state is also called state
   • c) accepting d) none of these
   • ii. 2 grammar is also grammar
   • c) Free d) natural
   • iv. (ata*)* is equivalent to
   • c) aa* d) none of these
   • v. A terminal string w L(G) is ambiguous if there exists or more derivation trees for w
   • a) one b) two
   • c) neither a nor b d) either a or b
   • B. Fillin the blanks (Choose correct one from the pool) (SM)
   • i. can be used to prove that certain sets are not regular alphabet, a finite state control, a set of final states and an initial state ili. languages can be accepted
   • iv. describe the languages accepted by finite state automata and are useful for representing certain sets of strings in an algebraic form
   • v. Context free languages (Type-2) can be accepted
   • C. the following terms in one or two lines (SM)
   • i. Nondeterministic finite state machine
   • ii. Grammar
   • v. Language generated by the grammar L(G) Paper Subject Code: 80501 Theory of Computation Attempt the following: (Any THREE) (15M)
   • A. Explain the process of construction of minimum automaton. Give suitable example to explain the concept
   • B. Construct a DFA accepting all strings over {a, b} ending in ab
   • D. If G=({S}, {0,1}, {S > 0S1,S > A}, S), find L(G)
   • E. Define Ambiguous Grammar. Find if the grammar G with the following productions is ambiguous?
   • F. Write a note on classification of Grammar
4. Q3 Attempt the following: (Any THREE) (15M)
   • A. State and prove pumping lemma for regular sets
   • B. Give a regular expression for representing the set L of strings in which every 0 is immediately followed by at least two 1’s Also prove that the regular expression also describes the same set of strings
   • C. Explain the steps for reduction of grammar to Chomsky normal form
   • D. Convert the nondeterministic systems to deterministic systems
   • E. State and prove Arden’s theorem
   • F. What is a derivation tree? Generate the derivation tree for the string aabaa using the grammar G with following set of productions
5. Q4 Attempt the following: (Any THREE) (15M) Explain the Linear Bound Automata Model Write a note on Halting problem of Turing Machine
   • D. a Turing Machine that accepts {0"1" 1 } What is Turing Machine? Design a Turing Machine to recognize all strings consisting of an even number of 1’s Explain the structure and operation of pushdown automata Paper Subject Code: 80501 Theory of Computation
6. Q5 Attempt the following: (Any THREE) (15M)
   • A. Construct a DFA with reduced states equivalent to the regular
   • B. Let G be the grammar with productions For the string 00110101, find
   • (a) the leftmost derivation
   • (b) rightmost derivation
   • C. Consider a Mealy machine represented by the figure given below Construct a Moore machine equivalent to this Mealy machine
   • D. What is regular set? Is L= | n>1} regular?
   • E. Construct the finite automaton equivalent to the regular expression
   • F. Write a note on operations on language

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