Pushdown Automata and Context-Free Grammars in Bisimulation Semantics

The Turing machine models an old-fashioned computer, that does not interactwith the user or with other computers, and only does batch processing.Therefore, we came up with a Reactive Turing Machine that does not have theseshortcomings. In the Reactive Turing Machine, transitions have labels to give anotion of interactivity. In the resulting process graph, we use bisimilarityinstead of language equivalence. Subsequently, we considered other classical theorems and notions fromautomata theory and formal languages theory. In this paper, we consider theclassical theorem of the correspondence between pushdown automata andcontext-free grammars. By changing the process operator of sequentialcomposition to a sequencing operator with intermediate acceptance, we get abetter correspondence in our setting. We find that the missing ingredient torecover the full correspondence is the addition of a notion of state awareness