2014 (English)Report (Other academic)
This paper considers a characterization of the context-free non-regular languages, conjecturing that there for all such languages exists a fixed string thatcan 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 shown to imply that the shuffle of two context-free languagesis not context-free.
Place, publisher, year, edition, pages
Umeå: Umeå universitet , 2014. , 9 p.
Report / UMINF, ISSN 0348-0542 ; 14.12
context-free languages, characterization, regular languages, pumping lemma, shuffle
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-88231OAI: oai:DiVA.org:umu-88231DiVA: diva2:714505