2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Good eye! I can tell right off the bat this will do the trick. $\endgroup$
    – breandan
    Commented Apr 26 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.