Unambiguous conjunctive grammars over a one-letter alphabet

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 ≥ 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits {⌊k+9/4⌋,..., ⌊k+1/2⌋}, the language of all strings aⁿ with the base-k notation of the form 1 w 1, 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₀, testing whether a given unambiguous conjunctive grammar generates L₀ is undecidable.