Bucher’s density problem for context-free languages

For every finite alphabet $\Sigma$ and all context-free languages $L,U\subseteq\Sigma^*$ , if $L\subseteq U$ and $U\setminus L$ is infinite, then there exists a context-free language $K\subseteq\Sigma^*$ such that $L\subseteq K\subseteq U$ and both $K\setminus L$ and $U\setminus K$ are infinite.

References

Primary source

arXiv

Additional references

Solution to Bucher's density problem for context-free languages — arXiv

automata-theory formal-languages

Posted 4 weeks ago

Progress summary

Refreshed 4 weeks ago

Claimed solved

An unrefereed preprint claims to refute Bucher’s 1980 conjecture about density in context-free languages.

Bucher’s 1980 question asks whether the proposed density property holds for context-free languages. The latest report claims a negative answer.

September 2026 claimed counterexample

On September 8, 2026, a report linked to an unrefereed preprint describing a binary-language construction based on factorial encodings that refutes the proposed property. This would settle the problem negatively, but the result has not been independently verified.

Current status (as of September 2026): A negative answer is claimed via a factorial-encoding construction, but the claim remains unverified.

Sources

No solutions have been posted yet.