<p>We all know that arbitrary CFG and FSA can be intersected using the Bar-Hillel Construction, whose time complexity is unfortunately too expensive. On the other hand, there are efficient algorithms that intersects intersect CFGs with lattices (i.e. acyclic FSAs). If an FSA is much like a lattice, except that all circles it can possibly have are self loops, is there any efficient algorithm for intersecting such an FSA with a CFG?</p>

CC BY-SA 3.0
2012-03-30T21:42:15.240Z
Wouldn't an acyclic FSA accept a finite language? In fact, in [this](http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf) paper, an acyclic FSA is called a _dictionary_. In any case, it would be helpful to give a reference for the intersection algorithm of CFLs/CFGs with acyclic FSAs.
David Lewis
CC BY-SA 3.0
2012-03-30T22:08:48.123Z
Just a remark on the way the question is stated: the Bar-Hillel algorithm is in $O(|Q|^3)$ for unweighted automata with state space $Q$.
Sylvain
<fl.formal-languages><automata-theory>
Fast weighted intersection algorithm for CFG and FSA with self loops but no other circles?
Wu Ke
# Fast weighted intersection algorithm for CFG and FSA with self loops but no other circles?

(Asked by: username_0 on 2012-03-30)

We all know that arbitrary CFG and FSA can be intersected using the Bar-Hillel Construction, whose time complexity is unfortunately too expensive. On the other hand, there are efficient algorithms that intersects intersect CFGs with lattices (i.e. acyclic FSAs). If an FSA is much like a lattice, except that all circles it can possibly have are self loops, is there any efficient algorithm for intersecting such an FSA with a CFG?

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: Wouldn't an acyclic FSA accept a finite language? In fact, in [this](http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf) paper, an acyclic FSA is called a _dictionary_. In any case, it would be helpful to give a reference for the intersection algorithm of CFLs/CFGs with acyclic FSAs.  
> **username_2**: Just a remark on the way the question is stated: the Bar-Hillel algorithm is in $O(|Q|^3)$ for unweighted automata with state space $Q$.  

---

## 0 answers

