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.


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\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.