Back to Search
Start Over
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.
- Source :
-
Fundamenta Informaticae . 2018, Vol. 162 Issue 1, p43-72. 30p. - Publication Year :
- 2018
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 162
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 131747161
- Full Text :
- https://doi.org/10.3233/FI-2018-1713