Engineering BE Computer Engineering Sem 5 December 2019 2019 Theory Of Computer Science Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 (a) Explain post correspondance problem. 5 marks
   • (b) Differentiate between FA and PDA. 5
   • (c) Define Regular Expression and obtain a regular expression such that 5 {0,1} } with at the most three zeros
   • (d) What is ambiguous grammar? Check whether following grammar is ambiguous or not 5
2. Q2 (a)Design a Finite State Machine to accept following language over the alphabet {0, 1} L(R )= { starts with 0 and has odd length or starts with 1 and has even length } 10 marks
   • (b) Give and explain formal definition of Pumping Lemma for Regular Language and 10 prove that following language is not regular
3. Q3 (a) Construct PDA accepting the language 10 marks
   • (b) Consider the following grammar 10 For the string “ibtaeibta’ find the following:
   • (i) Leftmost derivation
   • (iv), Check if above grammar is ambiguous
4. Q4 PDA to check {a,b}*} where reverse of w & c is a constant. 10 marks
   • (b) Convert following CFG to CNF 10
5. Q5 Convert (0+1) into NFA with e-moves and obtain DFA. 10 marks
   • (b) Construct Moore and Mealy Machine to convert each occurrence of 101 by 111. 10 Write short note on following (any 2) 20
   • (a) Chomsky Hierarchy
   • (b) Halting Problem
   • (c) Rice’s Theorem

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