Languages with context-free grammar having only one non-terminal symbol
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.
No comments:
Post a Comment