出版社：Information and Media Technologies Editorial Board
摘要：This paper refines the alternate stacking technique used in Greibach-Friedman's proof of the language inclusion problem L ( A ) ⊆ L ( B ), where A is a pushdown automaton (PDA) and B is a superdeterministic pushdown automaton (SPDA). In particular, we propose a product construction of a simulating PDA M , whereas the one given by the original proof encoded everything as a stack symbol. This construction avoids the need for the “liveness” condition in the alternate stacking technique, and the correctness proof becomes simpler.
