Time Varying Pushdown Automata

Time varying pushdown automata (PDA) are defined and equivalence between two modes of acceptance shown. It is seen that periodically time varying pushdown automata accept exactly the class of context-free languages. Time varying generalized PDA are defined and their equivalence to terminal weighted context free grammars in GNF shown. It is shown that TVGPDA can be simulated by TVPDA. Thus TVPDA give another machine characterization of recursively enumerable sets. © 1988, Taylor & Francis Group, LLC. All rights reserved.