Regularity of languages generated by non context-free grammars over a singleton terminal alphabet
classification
💻 cs.FL
keywords
context-freelanguagesalphabetsatisfysingletonterminallanguagelemma
read the original abstract
It is well-known that: (i) every context-free language over a singleton terminal alphabet is regular, and (ii) the class of languages that satisfy the Pumping Lemma is a proper super-class of the context-free languages. We show that any language in this superclass over a singleton terminal alphabet is regular. Our proof is based on a transformational approach and does not rely on Parikh's Theorem. Our result extends previously known results because there are languages that are not context-free, do satisfy the Pumping Lemma, and do not satisfy the hypotheses of Parikh's Theorem.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.