A probabilistic pushdown automaton (PDA) maps a state and a letter on top of the pushdown stack to a probability distribution over states and stack actions (pushes and pops). Thus, it lies between a deterministic and a nondeterministic PDA. Equivalence of accepted languages is decidable if we are given two deterministic PDAs and undecidable if we are given two nondeterministic PDAs. In a probabilistic PDA (PPDA), a word is accepted with a probability obtained by summing over all runs, say accepting by empty stack. Zero probability is interpreted as rejection. The language equivalence problem for PPDA asks whether two configurations (state and stack contents) accept each word over the input alphabet with the same probability.

The PDA to context-free grammar reduction was shown by Rosenkrantz to be polynomial time [1]. The authors show that this carries over to a reduction from ppda to “multigrammars” (the tricky part is keeping the conversion of a grammar to Greibach normal form in polynomial time), and hence to context-free grammars with finite multiplicity. Deciding whether two finite-multiplicity context-free grammars are equivalent up to multiplicity is a longstanding open problem [2]. The authors also give a polynomial space upper bound when the input alphabet is unary.