On the Intersection of Context-Free and Regular Languages

09/14/2022
by   Clemente Pasti, et al.
0

The Bar-Hillel construction is a classic result in formal language theory. It shows, by construction, that the intersection between a context-free language and a regular language is itself context-free. However, neither its original formulation (Bar-Hillel et al., 1961) nor its weighted extension (Nederhof and Satta, 2003) can handle automata with ϵ-arcs. In this short note, we generalize the Bar-Hillel construction to correctly compute the intersection even when the automaton contains ϵ-arcs. We 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset