# On the Intersection of Context-Free and Regular Languages

arXiv: https://arxiv.org/abs/2209.06809 · HTML: https://mlsanity.com/paper/2209.06809/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 21 references that are in the map.
- First posted on arXiv 14 Sep 2022.

## Built on by (most cited first, 3 of 3)

- [Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars](https://mlsanity.com/paper/2602.00612/) (2026)
- [An Exploration of Left-Corner Transformations](https://mlsanity.com/paper/2311.16258/) (2023)
- [Prefix Parsing is Just Parsing](https://mlsanity.com/paper/2604.21191/) (2026)

## Abstract (arXiv)

The Bar-Hillel construction is a classic result in formal language theory. It shows, by a simple construction, that the intersection of a context-free language and a regular language is itself context-free. In the construction, the regular language is specified by a finite-state automaton. However, neither the original construction (Bar-Hillel et al., 1961) nor its weighted extension (Nederhof and Satta, 2003) can handle finite-state automata with varepsilon-arcs. While it is possible to remove varepsilon-arcs from a finite-state automaton efficiently without modifying the language, such an operation modifies the automaton's set of paths. We give a construction that generalizes the Bar-Hillel in the case where the desired automaton has varepsilon-arcs, and further prove that our generalized construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the asymptotic size of the original construction.