Problem 1: Properties and Relations of Regular Languages [10] In each of the following statements, A and B denote languages. For each statement, identify a counter-example to prove that it is false. a. If A is non-regular and B is non-regular, then AB is non-regular. [2] b. If AB is regular and A is regular, then B is regular. [2] c. If AB is non-regular, then both A and B are non-regular. [2] d. If A is non-regular and B is non-regular and A=B then AB is non-regular. e. If A is regular, then A si regular. [2] Problem 2: Non-regular languages [20] Prove that the following languages over the alphabet, ={0,1,#}, are not regular. a. A={u#v#wu,v,w{0,1},uRisasubstringofeithervorw} (uRR denotes the reverse of string u ) [10] b. For any x{0,1}, let c0(x) represent the number of zeroes in x, and c1(x) the number of ones. B={1n#xn1,x{0,1}andc0(x)>norc1(x)>n} c. [Bonus: (Optional)] Let C={1m#1nm,n0,m=n} Prove, using the pumping lemma, that C is not regular. [10] Problem 3: Context Free languages [20] a. Show that the language A, defined in Problem 2(a), is context-free by designing a CFG to generate it. You should explain the role of each non-terminal in your grammar, and why it generates the strings that you say it does. [10] b. Design a PDA to recognise the language B, defined in Problem 2(b). Provide an explanation of how your PDA works by describing the roles of specific states (or groups of states), and explaining how those roles ensure that only the appropriate strings are accepted. [10]