Abstract
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.
C.R. Categories:
∗Supported by a Fulbright fellowship from CIES and US Airforce Grant AFOSR-86-0092 when the first author visited the University of Maryland.
∗Supported by a Fulbright fellowship from CIES and US Airforce Grant AFOSR-86-0092 when the first author visited the University of Maryland.
Notes
∗Supported by a Fulbright fellowship from CIES and US Airforce Grant AFOSR-86-0092 when the first author visited the University of Maryland.