l. (50%) For each of the following languages L-{a, b)", either construct directly a PDA that generates it, or prove that no such PDA exists. Hint: L is really a very simple language in disguise 2. (10+5+10%) (a) Construct directly a PDA M that recognizes the language LbcP p,q0 Define M in full detail, specifying the auxiliary alphabet, initial state, accepting states, (b) Give an accepting computation trace of your PDA for the input aaabcc, and a trace for (c) Give a CFG G that generates L, and convert it to another PDA N that recognizes L as 3. (25%) For each of the following statements, determine whether or not it is always true, and and transition rules. abc. well prove your answer. (a) If L and M are CFLs, then so is L- M. (b) If L is a CFL, and M is a regular language, then L - M is CF. (c) If L is a CFL, and M a regular language, then M - L is CF (d) If L is recognized by a PDA, then it is decidable in cubic time. (e) If L is regular, and K is recognized by a PDA, then L- K is context-free