Jos C. M. Baeten ; Cesare Carissimo ; Bas Luttik - Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

lmcs:9178 - Logical Methods in Computer Science, March 2, 2023, Volume 19, Issue 1 - https://doi.org/10.46298/lmcs-19(1:15)2023
Pushdown Automata and Context-Free Grammars in Bisimulation SemanticsArticle

Authors: Jos C. M. Baeten ; Cesare Carissimo ; Bas Luttik

    The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reactive Turing Machine, transitions have labels to give a notion of interactivity. In the resulting process graph, we use bisimilarity instead of language equivalence. Subsequently, we considered other classical theorems and notions from automata theory and formal languages theory. In this paper, we consider the classical theorem of the correspondence between pushdown automata and context-free grammars. By changing the process operator of sequential composition to a sequencing operator with intermediate acceptance, we get a better correspondence in our setting. We find that the missing ingredient to recover the full correspondence is the addition of a notion of state awareness.


    Volume: Volume 19, Issue 1
    Published on: March 2, 2023
    Accepted on: January 28, 2023
    Submitted on: March 7, 2022
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory

    1 Document citing this article

    Consultation statistics

    This page has been seen 1831 times.
    This article's PDF has been downloaded 323 times.