One-Way Tape Determinsitic PDA
Abstract
An automata with a tape is known as a pushdown automata (PDA). A pushdown automation has an
advantage of scanning the alphabets of its tape without deleting its content. A one-way tape deterministic pushdown
automata (DPDA) is considered in this paper. In this paper, it is presented that L(R) ={w| x ∈ R,wx ∈ L} where R is a
set of symbols and a language L accepted by a PDA. On the basis of a corollary, the terminal symbols are not required
on the alphabet set of DPDA. In this paper it is also presented that Max(L) = {w| x ∈ R,wx ∈ L} is accepted by a DPDA
only and only if L is accepted by a DPDA.
References
Aho, A. Computational thinking in programming language and compiler design (keynote). STOC ’21: 53rd Annual ACM SIGACT Symposium On Theory Of Computing, Virtual Event, Italy, June 21-25, 2021. pp. 1 (2021), https://doi.org/10.1145/3406325.3465350
Aho, A. & Ullman, J. Abstractions, their algorithms, and their compilers. Commun. ACM. 65, 76-91 (2022), https://doi.org/10.1145/3490685
Aho, A. Computation and Computational Thinking. Comput. J.. 55, 832-835 (2012), https://doi.org/10.1093/comjnl/bxs074
Okhotin, A. & Salomaa, K. Descriptional complexity of unambiguous input- driven pushdown automata. Theoretical Computer Science. 566 pp. 1-11 (2015), https://www.sciencedirect.com/science/article/pii/S0304397514008585
Ullman, J. The Battle for Data Science. IEEE Data Eng. Bull.. 43, 8-14 (2020), http://sites.computer.org/debull/A20june/p8.pdf
Polách, R., Trávníček, J., Janoušek, J. & Melichar, B. Efficient determinization of visibly and height-deterministic pushdown automata. Computer Languages, Systems & Structures. 46 pp. 91-105 (2016), https://www.sciencedirect.com/science/article/pii/S1477842416300136
Grigorian, H. & Shoukourian, S. The equivalence problem of multidimensional multitape au- tomata. J. Comput. Syst. Sci.. 74, 1131-1138 (2008), https://doi.org/10.1016/j.jcss.2008.02.006
Kutrib, M. & Malcher, A. Context-dependent nondeterminism for push- down automata. Theoretical Computer Science. 376, 101-111 (2007), https://www.sciencedirect.com/science/article/pii/S0304397507000321, Developments in Language Theory
Ullman, J. On the Nature of Data Science. KDD ’21: The 27th ACM SIGKDD Conference On Knowledge Discovery And Data Mining, Virtual Event, Singapore, August 14-18, 2021. pp. 4 (2021), https://doi.org/10.1145/3447548.3469651
