Suppose, for some pushdown automaton A, there exists a constant k such that A never stores more than k elements on the stack. Show that the language L(A) is regular. (Hint: Show that the pushdown automaton A can be transformed to a finite automaton accepting the same language.)

Show that if a language L over an alphabet E is accepted by a pushdown automaton, then the language {u#vlu E L and uv E L} for some symbol # Z E is accepted by a pushdown automaton.