Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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