论文标题
关于无上下文和普通语言的交集
On the Intersection of Context-Free and Regular Languages
论文作者
论文摘要
酒吧 - 希利尔的结构是正式语言理论的经典结果。它通过简单的结构表明，无上下文的语言和普通语言的交集本身是无上下文的。在构造中，常规语言由有限状态自动机指定。但是，原始结构（Bar-Hillel等人，1961年）和其加权扩展（Nederhof and Satta，2003年）都无法使用$ \ varepsilon $ -arcs处理有限状态自动机。虽然可以从有限状态自动机上删除$ \ varepsilon $ -Arcs，而无需修改语言，但此类操作会修改自动机的一组路径。在所需的自动机具有$ \ varepsilon $ -Arcs的情况下，我们提供了一种概括的构造，该结构可以概括为bar-hillel，并进一步证明了我们的广义构造会导致语法，该语法编码了输入自动机和语法的结构，同时保留了原始结构的不良尺寸。
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.
