Formal Languages and Automata Theory — DU B. Voc – Web Designing Previous Year Question Papers

(d) Parts of a question should be attempted together. Q1. (a) Explain the Chomsky Classification of language. 3 (b) Define ambiguity in grammar? Can it be removed? if yes, how? 3 (c) Differentiate between DFA and NDFA with the help of suitable examples. 3 (d) Prove L={ab n: n>=0} to be regular using pumping lemma. 3 (e) Construct TM that recognizes language over alphabet 0,1 such that string ends in 10. 3 (f) Design a FA from given regular expression 10 + (0 +11) 0 *1 3 (g) Prove that LHS RE is equivalent to RHS RE 3 (h) What are the closure properties of CFL? 3 (i) What properties of recursive enumerable seta are not decidable? 3 (i) Construct a regular expression for DFA shown below: : 3 Q2. (a) Convert the given grammar to CNF 8 (b) Demonstrate the model of Linear bound automata(LBA) with neat diagram 7 Q3. (a) Define with example 8 i. Left Recursion ii. Leftmost and Rightmost derivation ill. Ambiguous grammar iv. Parse Tree (b) Design a PDA for accepting a palindrome Loo = {WCWR I W€(a+b)*} where wR is:reverse of W and show ID for the string "aab" (b) Design DFA to Accept stings of o's and 1 's L={ starting with 01 or starting with 10} (c) Construct a DFA to accept strings ofo's and l's starting with at leasttwo o's and ending with at least two 1 's a) Construct the minimum state automata equivalent to finite automata given by (Q0 is th.e initial state and Q3;Q4 are fmal states): State a b i>-OO /initial sl:ate) 01 02 03 (Final state) 05 06 04 (Final state) 07 06 Q6. Q7. (c) Prove that the complement of a regular language is also regular. (a) Obtain the unambiguous grammar for the grarmnar shown and get the derivation for the expression (a+b)*(a-b). (b) Consider the following grammar Give LM) and RM) and Parse tree for the .string "aaabab " (c) State and prove pumping lemma Theorem (a) Explain The church-Turing machine with neat a diagram (b) .Explain Multiple TM with a neat diagram (c) Show that regular languages are closed under union,concatenation and Kleens star