Linear grammars with one-sided contexts and their automaton representation∗
1 Turku Centre for Computer Science, Turku 20014, Finland.
2 Department of Mathematics and Statistics, University of Turku, Turku 20014, Finland.
Received: 5 December 2014
Accepted: 11 June 2015
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 Σ02-completeness of the finiteness problem for these grammars and automata.
Mathematics Subject Classification: 68Q42 / 68Q80
Key words: Context-free grammars / conjunctive grammars / contexts / cellular automata / trellis automata / undecidability.
© EDP Sciences 2015