# Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite an ε-free non-recursive grammar into an equivalent ε-free NFA? My instinct is to put the grammar into GNF [2], translate it to an NFA, then remove ε, but it seems like there should be a more straightforward way that avoids the large blowup if we assume it to be non-recursive.

Build a directed graph, with one vertex per non-terminal, and an edge $$A \to B$$ if there is a rule in the grammar where $$A$$ is on the left-hand side and $$B$$ appears on the right-hand side. Since you assume the grammar is non-recursive, this graph is acyclic, i.e., a dag.

So, topologically sort the graph, and traverse the graph in reverse topologically sorted order. When you visit a vertex $$A$$, you will compute an $$\epsilon$$-free NFA for $$L(A)$$, using the NFAs already computed for previously visited vertices. This is easy using standard operations on NFAs.

For instance, suppose you visit the vertex for non-terminal $$A$$, and collecting all the rules with $$A$$ on the left-hand side gives something like $$A ::= B | aDb | EF | \cdots$$ (this is just an example). Then we know $$L(A) = L(B) \cup a L(D) b \cup L(E) L(F) \cup \cdots$$. Since we're traversing the graph in reverse topological order, we must already have visited $$B,D,E,F$$, so we already have $$\epsilon$$-free NFAs for $$L(B), L(D), L(E), L(F)$$. So now all we need is the ability to perform the following operations on $$\epsilon$$-free NFAs:

1. Given $$\epsilon$$-free NFAs for languages $$L_1,L_2$$, compute an $$\epsilon$$-free NFA for their concatenation $$L_1 L_2$$.

2. Given $$\epsilon$$-free NFAs for languages $$L_1,L_2$$, compute an $$\epsilon$$-free NFA for their union $$L_1 \cup L_2$$.

Both of those can be done with standard algorithms for NFAs.

• Good eye! I can tell right off the bat this will do the trick. Commented Apr 26 at 23:08