pith. sign in

arxiv: 1705.09695 · v2 · pith:SDNNLMMPnew · submitted 2017-05-26 · 💻 cs.FL

Regularity of languages generated by non context-free grammars over a singleton terminal alphabet

classification 💻 cs.FL
keywords context-freelanguagesalphabetsatisfysingletonterminallanguagelemma
0
0 comments X
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.