Linear Grammars with One-Sided Contexts and their Automaton Representation

: Barash M, Okhotin A

Publisher: EDP SCIENCES S A

: 2015

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-THEOR INF APPL

: 49

: 2

: 153

: 178

: 26

: 0988-3754

DOI: https://doi.org/10.1051/ita/2015004

The paper considers a family of formal grammars that extends linear context-free grammars with an operator for referring to the left context of a substring being defined, as well as with a conjunction operation (as in linear conjunctive grammars). These grammars are proved to be computationally equivalent to an extension of one-way real-time cellular automata with an extra data channel. The main result is the undecidability of the emptiness problem for grammars restricted to a one-symbol alphabet, which is proved by simulating a Turing machine by a cellular automaton with feedback. The same construction proves the Sigma(0)(2)-completeness of the finiteness problem for these grammars and automata.