1 } is not
context-free.
The pushdown automata were introduced by Oettinger (1961) and Schutzenberger (1963). Evey (1963) introduced the pushdown transducers. The equivalence of pushdown automata to context-free languages were observed by Chomsky (1962) and Evey (1963).
The pumping lemma for context-free languages is from Bar-Hillel , Perles , and Shamir
(1961). Scheinberg (1960) used similar arguments to show that { anbncn | n 1 } is not
context-free.
The closure of context-free languages under union , and their nonclosure under intersection and complementation, were noticed by Scheinberg (1960). The closure of the class of context-free languages under composition and under intersection with regular languages is due to Bar-Hillel , Perles , and Shamir (1961). Schutzenberger (1963) showed the closure under complementation of the class of languages that are accepted by the deterministic pushdown automata (Theorem 3.5.2). Bar-Hillel , Perles , and Shamir (1961) showed the closure of context-free languages under reversal (see Exercise 3.5.1(c)).
The decidability of the emptiness problem for context-free grammars is also due to Bar-Hillel , Perles , and Shamir (1961). The decidability of the equivalence problem for the deterministic finite-state transducers in Corollary 3.6.1 follows from Bird (1973). The proof technique used here is from Gurari (1979). This proof technique coupled with proof techniques of Valiant (1973) were used by Ibarra and Rosier (1981) to show the decidability of the equivalence problem for some subclasses of deterministic pushdown transducers.
Greibach (1981) and Hopcroft and Ullman (1979) provide additional insight into the subject.