Flip-pushdown automata, introduced by Sarkar , are pushdown automata with an additional ability to reverse the contents of their pushdown, and with the most interesting setting arising when the number of such flips is limited by a constant. Two characterizations of flip-pushdown automata (with a limited number of flips) in terms of grammars are presented in this paper. First, the model is characterized by context-free grammars with an extra ability to generate reversals, which are called
reversal-generating context-free grammars
(RGCFG). Next, a model of parallel word production called
parallel interleaving grammar system
(PIGS) is introduced, for which the equivalence with flip-pushdown automata is proved, linking flip-pushdown automata to parallelism. The characterization in terms of PIGS is used to prove that flip-pushdown automata (with a limited number of flips) are weaker than ET0L systems, which solves an open problem of Holzer and Kutrib .