A Reduction of Finitely Expandable Deep Pushdown Automata

Lucie Dvořáková,

Alexander Meduna


For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the present paper demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols - $ and #, where # always appears solely as the pushdown bottom. The paper demonstrates an infinite hierarchy of language families that follows from this main result. The paper also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages. In its conclusion, the paper suggests open problems and topics for the future investigation.

Słowa kluczowe: Finite Expandability, Reduction, Non- Input Pushdown Symbols, Deep Pushown Automata

[1] Kalra N., Kumar A., Fuzzy state grammar and fuzzy deep pushdown automaton, Journal of Intelligent and Fuzzy Systems, 2016, 31 (1), pp. 249–258.

[2] Kalra N., Kumar A., State grammar and deep pushdown automata for biological  sequences of nucleic acids, Current Bioinformatics, 2016, 11 (4), pp. 470–479.

[3] Arratia A., Stewart I. A., Program schemes with deep pushdown storage, in: Proc. of Logic and Theory of Algorithms, CiE 2008, Vol. 5028 of Lecture Notes in Computer Science, Springer, 2008, pp. 11–21.

[4] Meduna A., Deep pushdown automata, Acta Inf., 2006, 42 (8-9), pp. 541–552.

[5] Harrison M. A., Introduction to Formal Language Theory, Addison-Wesley, 1978.

[6] Meduna A., Automata and Languages: Theory and Applications, Springer, 2000.

[7] Meduna A., Zemek P., Regulated Grammars and Automata, Springer, 2014.

[8] Leupold P., Meduna A., Finately expandable deep PDAs, in: Proc. of Automata, Formal Languages and Algebraic Systems, World Scientific, 2010, pp. 113–123.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.

Wersja papierowa czasopisma dostępna na www.wuj.pl