TY - JOUR

T1 - On the number of nonterminal symbols in unambiguous conjunctive grammars

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Ambiguity

KW - Conjunctive grammars

KW - Descriptional complexity

KW - Language equations

KW - Unary languages

UR - http://www.scopus.com/inward/record.url?scp=85051991792&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/number-nonterminal-symbols-unambiguous-conjunctive-grammars

U2 - 10.3233/FI-2018-1713

DO - 10.3233/FI-2018-1713

M3 - Article

AN - SCOPUS:85051991792

VL - 162

SP - 43

EP - 72

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1

ER -