9
$\begingroup$

As seen in this question, the class of languages that can be generated by a context-free grammar having only one non-terminal symbol (i.e. the start symbol) is a proper subclass of the class of context-free languages (in particular, it doesn't contain and is not contained in the class of regular languages).

I'd like to know if there is a commonly used name for this subclass, and more importantly, if it is decidable whether a language $L$ generated by some context-free grammar $G$ belongs to this class or not (maybe under some assumptions on $G$).

Any reference to related topics would be very appreciated. Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

Not a real answer, but a modest pointer.

In the context of so-called "descriptional complexity" of formal models, the number of nonterminals needed to specify a context-free language is called the nonterminal complexity. There is a paper by Dassow and Stiebe, Nonterminal Complexity of Some Operations on Context-Free Languages, that e.g. shows that the language $a\{a,b\}^*a\{a,b\}^*$ has complexity two, i.e., does not belong to your class. Otherwise the paper is more interested in examples of complexity $n$.

As you know context-free languages can be described by systems of language equations. So your family must be the languages that have a single equation (rather than a system). E.g., the (one sided) Dyck language is $L = aLbL \cup \{\lambda\}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .