PROBABILISTIC PUSHDOWN AUTOMATA
Eugene S. Santos · Journal of Cybernetics · 1976
The properties of Probabilistic Pushdown Automata (PPA) are examined. First PPA is defined, various basic properties of it are derived, and several more restrictive types are considered. Then, the families of random languages acceptable and generable by various types of PPA, as well as the families of languages acceptable and generable by various types of PPA with cut-point, are studied. The relationships among these families are also examined, and many interesting results are obtained. Among them, it is shown that the family of languages generable by PPA having uniform output length is the homomorphic closure of the family of languages acceptable by PPA.