Let L be the language over the alphabet {x, y} consisting of those strings in which there are exactly as many ys as xs. The empty word is in L, as are xy and yxyx, but xxy and yyyx are not.

a) Give a diagram of a pushdown automaton that accepts L. Use only basic transitions, that is, do not use transitions that push or pop multi-symbol sequences in one arc.

b) Give a brief (sentence or two) explanation of the idea of how the machine works.

c) Give a full formal specification of the machine. To enhance readability, leave blank any entries in the transition table that consist of the empty set of pairs.

d) Construct a context-free grammar for L.

e) Give a leftmost derivation of the word xxyxyxyy in this grammar.