A translational theorem for the class of EOL languages

Joost Engelfriet, Grzegorz Rozenberg

Research output: Contribution to journalArticleAcademic

3 Citations (Scopus)
23 Downloads (Pure)


If K is not a context-free language, then sh(K, a*) is not an EOL language (where sh(K1, K2) denotes the shuffle of the languages K1 and K2, and a is a symbol not in the alphabet of K). Hence the class of context-free languages is the largest full AFL inside the class of EOL languages.
Original languageEnglish
Pages (from-to)175-183
JournalInformation and Control
Issue number2
Publication statusPublished - 1981
Externally publishedYes


Dive into the research topics of 'A translational theorem for the class of EOL languages'. Together they form a unique fingerprint.

Cite this