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.
Page Responsible: Frank Drewes 2024-11-21