Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA? The only simplifications I have come up with relate to the NFA-epsilon representation, the computation of the epsilon closure, and the DFA representation. Each NFA node can be represented as a set of symbols transitioned on, if it has an epsilon transition, and a unique reference to the following node. The DFA representation can use shared references as it is acyclic.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Unless I misunderstood your question, in a NFA $N$ that is a path one vertex has in-degree $0$ and outdegree $1$, one vertex (possibly the same) has in-degree $1$ and out-degree $0$, and all the other vertices have in-degree $1$ and out-degree $1$.
Let $N'$ be the NFA obtained by identifying all the vertices in the same component of the (undirected version of the) subgraph induced by all the edges labelled $\varepsilon$ in $N$. All vertices of $N'$ have maximum out-degree $1$, moreover $N'$ contains no edge labelled $\epsilon$. This shows that $N'$ is a DFA. The process can be performed in linear time.
A note: when a set $S$ of vertices from $N$ is identified into a single vertex $v$ in $N'$, you will need to mark $v$ as a final state in $N'$ iff at least one the vertices in $S$ is a final state in $N$.
-
$\begingroup$ I now realize what I meant, but did not describe (except in the simplified representation of each NFA node) was a linear multigraph (if such a term is sensible - I mean a graph where each node is of arbitrary in and out degree other than the first and last, but all edges of a node lead to the same node) for the NFA. Marking this answer as correct, and posting a new question describing the NFA as a linear multigraph. $\endgroup$ Apr 26, 2020 at 23:39