Noncounting Context-Free Languages
Stefano Crespi Reghizzi, Giovanni Guida, Dino Mandrioli · Journal of the ACM · 1978
The class of noncountlng (aperiodic) context-free parenthesis languages is introduced here and is found to extend the classical theory of noncountmg regular languages It Is proved that it is possible to decide whether or not a context-free parenthesis grammar Is noncountmg The class of k-distract-homogeneous grammars (previously introduced in connection with studies on grammatical mference or language acqmsitmn) is rigorously defined and proved to be noncountlng It as argued that the noncountmg model fits the syntactic aspects of natural or araficial languages more closely than the context-free model