Skip to content
Show report in:

UMINF 14.12

Characterizing Non-Regularity

This paper considers a characterization of the context-free non-regular languages, conjecturing that there for all such languages exists a fixed string that can be pumped to exhibit infinitely many equivalence classes. A proof is given only for a special case, but the general statement is conjectured to hold. The conjecture is then employed to demonstrate the non-context-free nature of the shuffle of two context-free languages.


context-free, regular, shuffle, pumping lemma, pumping, formal languages


Back Edit this report
Entry responsible: Martin Berglund

Page Responsible: Frank Drewes