# Path NFA-eplison to DFA conversion

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.

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$$.