1. Pushdown Automata ( 30 points - 10 each) Give pushdown automata for the following languages. (a) L1={aibjcki,j,kZ0,i+j is odd and i+j>2k} Note that 0 is an even number, so strings in this language must have at least one a or one b. (b) L2={ww is a binary string with the same number of occurrences of 00 and 11 as substrings Note that 000 has exactly two substrings equal to 00 . Thus 1100011 is a string in L2. (c) L3={ww=wR,w is odd with 010 as the middle three characters, and w{0,1}}