Context-free language gaps found without infinite stepping stones
Solution to Bucher's density problem for context-free languages
Formal Languages and Automata Theory
Summary
The paper answers an old question about context-free languages, which are ways to describe patterns in strings of symbols used in computer science. It was asked whether between two such languages, if one is inside the other but the difference is infinitely large, there must always be a 'middle' language with infinite differences on both sides. The authors show this is not always true by cleverly building a special language based on encoded factorial computations that regular languages can't split into infinite parts both ways. Their construction proves that some context-free language pairs have no intermediate language that fits those infinite difference requirements.
context-free languageregular languagelanguage inclusionfactorial encodingfinite automatonone-counter automatonlanguage complementinfinite differenceformal languageslanguage hierarchy
Authors
Rastko Maslic, Jeffrey Shallit
Abstract
In 1980 Bucher asked whether, given context-free languages $L\subseteq U$ with $U\setminus L$ infinite, there must be a context-free language $K$ between them for which both $K\setminus L$ and $U\setminus K$ are infinite. We give a negative answer. We first construct an infinite language $D$ with context-free complement such that, for every regular language $R$, either $D\cap R$ or $D\setminus R$ is finite. The words of $D$ encode computations of factorials; repetition of letters ensures that each finite automaton either accepts all but finitely many words of $D$ or rejects all but finitely many words of $D$, while a one-counter automaton recognizes errors in the encodings. We then construct $L$ and $U$ from the complement of $D$. A grammar argument shows that any context-free intermediate language $K$ would divide $D$ in the same way as some regular language. This proves the required impossibility. Both $L$ and $U$ can be taken over a binary alphabet.