Journalartikel

Jahr der Veröffentlichung: 2023

Seiten: 225-251

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 34

Heftnummer: 02N03

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S012905412244004X

Verlag: World Scientific Publishing

Abstract: 
Top-down syntax analysis can be based on LL(k) grammars. The canonical acceptors for LL(k) languages are deterministic stateless pushdown automata with input lookahead of size k. We investigate the computational capacity of reversible computations of such automata. A pushdown automaton with lookahead k is said to be reversible if its predecessor configurations can uniquely be computed by a pushdown automaton with backward input lookahead (lookback) of size k. It is shown that we cannot trade a lookahead for states or vice versa. The impact of having states or a lookahead depends on the language. While reversible pushdown automata with states accept all regular languages, we are going to prove that there are regular languages that cannot be accepted reversibly without states, even in case of an arbitrarily large lookahead. This completes the comparison of reversible with ordinary pushdown automata in our setting. Moreover, it turns out that there are problems which can be solved by reversible deterministic stateless pushdown automata with lookahead of size k + 1, but not by any reversible deterministic stateless pushdown automaton with lookahead of size k. So, an infinite and tight hierarchy of language families dependent on the size of the lookahead is shown. Finally, we prove that the language families accepted by reversible deterministic stateless pushdown automata with lookahead of size k are not closed under standard operations. For example, we show that the families are anti-AFLs which are not closed under intersection.

Harvard-Zitierstil: Kutrib, M. and Meyer, U. (2023) Reversible Top-Down Syntax Analysis, International Journal of Foundations of Computer Science, 34(02N03), pp. 225-251. https://doi.org/10.1142/S012905412244004X

APA-Zitierstil: Kutrib, M., & Meyer, U. (2023). Reversible Top-Down Syntax Analysis. International Journal of Foundations of Computer Science. 34(02N03), 225-251. https://doi.org/10.1142/S012905412244004X