1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\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$
    – ScootyPuff
    Apr 26, 2020 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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