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.

Police may soon have a new way to catch pedophiles who distribute child abuse photos anonymously online. The technology could also help law enforcement agencies in other ways, such as identifying smartphone thieves who take pictures with the stolen gadgets and then post their snapshots on the Internet. Riccardo Satta, scientific project officer of the European Commission Joint Research Center's Institute for the Protection and Security of the Citizen, described the work he did with fellow researcher Pasquale Stirparo at the Computers, Privacy and Data Protection Conference in Brussels held in January.* The key is the ability to spot a unique, unremovable pattern--or signature--that each digital camera imprints on photographs. By comparing the signature from a specific camera with those found in images posted to social media, a forensic investigator would be able to establish that all the images had been taken by the same camera.