Item

Abstract

It is demonstrated that unambiguous conjunctive grammars over a unary alphabet Σ=a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base k ≥qslant 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits \big{\lfloor\frac{k+9}{4}\rfloor, \ldots, \lfloor\frac{k+1}{2}\rfloor\big, the language of all strings a^n with the base-k notation of the form \D1w\D1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L_0, testing whether a given unambiguous conjunctive grammar generates L_0 is undecidable.