On the Intersection of Context-Free and Regular Languages

Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 737–749 May 2-6, 2023 ©2023 Association for Computational Linguistics On the Intersection of Context-Free and Regular Languages Clemente PastiN,Q Andreas OpedalQ Tiago PimentelD Tim Vieira6 Jason Eisner6 Ryan CotterellQ NUniversità della Svizzera Italiana QETH Zürich DUniversity of Cambridge 6Johns Hopkins University clemente.pasti@usi.ch andreas.opedal@inf.ethz.ch tp472@cam.ac.uk tim.f.vieira@gmail.com jason@cs.jhu.edu ryan.cotterell@inf.ethz.ch 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 with- out 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 ε-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. https://github.com/rycolab/ bar-hillel 1 Introduction Bar-Hillel et al.’s (1961) construction—together with its weighted generalization (Nederhof and Satta, 2003)—is a fundamental result in formal language theory. Given a weighted context-free grammar (WCFG) G and a weighted finite-state automaton (WSFA) A, the Bar-Hillel construction yields another WCFG G∩ whose language L(G∩) is equal to the intersection of L(G) with L(A). Impor- tantly, the Bar-Hillel construction directly proves that weighted context-free languages are closed un- der intersection with weighted regular languages. The construction was later extended to other for- malisms, e.g., tree automata (Maletti and Satta, 2009), synchronous tree substitution grammars (Maletti, 2010) and linear context-free re-writing systems (Seki et al., 1991; Nederhof and Satta, 2011b). Furthermore, the Bar-Hillel construction has seen applications in the computation of infix probabilities (Nederhof and Satta, 2011a) and hu- man sentence comprehension (Levy, 2008, 2011). Unfortunately, Bar-Hillel et al.’s construction, as well as its weighted generalization by Nederhof and Satta, requires the input automaton to be ε-free.1 Although any WFSA can be converted to a weakly equivalent2 ε-free WFSA using well- known techniques (Mohri, 2001, 2002; Hanneforth and de la Higuera, 2010), such an approach adds an additional step of computation, typically increases the size of the output grammar G∩, and does not, in general, maintain a bijection between derivations in G∩ and the Cartesian product of the derivations in G and paths in A. In other words, G∩ is not strongly equivalent to the product of G and A.3 In this note, we generalize the classical Bar- Hillel construction to the case where the automaton we seek to intersect with the grammar has ε-arcs. Our new construction produces a WCFG G∩ that is strongly equivalent to the product of G and A. We further generalize the Bar-Hillel construction to work with arbitrary commutative …

Content truncated to 500 words