Affiliations: [a] Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50–383 Wroclaw, Poland, aje@cs.uni.wroc.pl | [b] St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia, alexander.okhotin@spbu.ru
Correspondence:
[*]
Address for correspondence: Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50–383 Wrocław, Poland.
Abstract: Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.
Keywords: conjunctive grammars, ambiguity, language equations, unary languages, descriptional complexity
