On the Intersection of Context-Free and Regular Languages (2023)

Abstract: 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 ε-arcs. While it is possible to remove ε-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 the desired automaton has ε-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.

## languages, automata, and grammars as background, we now give formal definitions of semirings, weighted formal languages, finite-state automata, and context-free grammars. ## conclusion we generalized the weighted bar-hillel intersection construction so that the given wfsa may contain ε-arcs. our construction is strongly equivalent to the product of the original wcfg and wfsa, i.e., every derivation tree in the resulting grammar represents a pairing of a derivation tree in the input wcfg and a path in the wfsa with the same yield. we gave a full proof of correctness for our construction. by adding output strings to the wfsa arcs and having rule (5f) rewrite to the arc's output string, our method can also be used to compose a wcfg with a weighted finite-state transducer (wfst) that could usefully model morphological post-processing or speaker errors. michael sipser. 2006. introduction to the theory of computation, 2 edition. thomson course technology. hisao tamaki and taisuke sato. 1984. unfold/fold transformation of logic programs. in proceedings of the second international logic programming conference, pages 127-138, uppsala, sweden. uppsala university.