1. Construct a Pushdown automata (PDA) accepting the language L = {0'1' | i > 0} U {o1/ [ j z 0}. 2. For E = {0,1}, design DPDAS to accept the following languages: (a) 0* (b) {01'0/1' | i, j z 0} (c) (02'1' | i z 1} %3D (d) {0"1" | m= n} 3. Define the concepts of string and language acceptance for PDAS. 4. For E = {0,1}, design PDA to accept the following languages: (a) {x|xE{0, 1}"} (b) {x|xE{0, 1}* and x = x*} (c) {0"1" |ns m s 2n} (d) {0"1" |3n s ms 7n} 5. Construct a PDA accepting {a"b" |n z 1} by empty store. Obtain the PDA accepting {a"b" c" | m, n z1} by empty store. 6. 7. Obtain the PDA accepting {a"b"c" | m, n 2 1} by final state. Given L = {a"b" |m n,(x)} xE{a, b} :n, (x) 1, jz 0} Construct a PDA accepting {a' b"c" :n > 1, j> 1} by final state. 17. 18. Constuct a CFG generating {a"b" | n21} U {a"bm |m 2 1}. Using this CFG, construct a PDA accepting the given set by empty store. Using Pumping lemma show that the language L = {a'b'c' | i > 0} is not 19. context free. 20. Using Pumping lemma show that the language L = {a"b"c" |0 smsns p} Using Pumping lemma show that the language 20. L = {a"b" c" |0 s ms ns p} is not a CFL. 21. Using Pumping Lemma prove that the language L = {ww|wE{0,1}* is not a CFL. 22. Consider the set of all strings over {a, b} with no more than twice as many a's as b's: {xE{a,b}' | # a(x)s 2# b(x)} (a) Give a CFG for this set, and prove that it is correct. (b) Give a PDA for this set. Show sample runs on the input strings aabbaa, aaabbb and aaabaa. 23. Consider the set a'b'c {a"b"c" | n 2 0} - the set of all strings of a's followed by b's followed by c's such that the number of a's, b's and c's are not all equal. (a) Give a CFG for the set, and prove that your grammar is correct. (b) Give an equivalent PDA. 24. Show that {a, b} {a"b" | n2 0} is not context free