The complexity of the reachability-coreachability analysis of a finite state machine

Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is coreachable if there exists a string $s$ such that $\delta(q,s) \in Q_{m}$.

I'm wondering what is the computational complexity of the reachability-coreachability analysis of a FSM, as a function of $|Q|=n$. In particular, the input is a FSM $A$, and I'd like the algorithm to output a list of all states that are reachable, and a list of all states that are coreachable. What is the worst-case asymptotic complexity of this function, as a function of $n$?

Let $m\ge1$ be the size of the alphabet $\Sigma$.

Let us restrict our attention to the two most common models of finite state machines (FSM), deterministic finite automatons (DFA) and non-deterministic finite automatons (NFA). We know that FSM corresponds naturally to the directed multi-graph as explained by Wikipedia entry on state diagram.

A $n$-state $DFA$ $D=(Q,\Sigma,\delta,q_0,F)$ corresponds a directed multi-graph $G$, whose nodes are also $Q$ and all of whose nodes have outdegree $m$. Whenever we mention some $q\in Q$, it will be clear whether we mean the state $q$ in $D$ or the node $q$ in $G$. It takes $O(mn)$ time to convert $D$ to $G$.

-
The problem of determining all reachable states from state $q_0$ in $D$ corresponds to the problem of determining all reachable nodes from node $q_0$ in $G$. If we use the classic breadth first traversal starting from node $q_0$ to solve the later problem, the worst case happens when we have to go through all arcs in $G$, which is $\Theta(mn)$ time-complexity. In fact, for any algorithm to determine the set of all reachable nodes, all edges must be checked.

-
The problem of determining all co-reachable states in $D$ corresponds to the problem of determining all reachable nodes from $q'$ in graph $G'$, where $G'$ is $G$ with all edges reversed and with one extra node $q'$ that is connected to all node $q_i\in F$. The conversion from $G$ to $G'$ takes $O(mn+n) = O(mn)$ time. If we use the classic breadth first traversal starting from node $q'$ to solve the later problem of all reachable nodes, the worst case happens when we have to go through all arcs in $G'$, which is $\Theta(m(n+1)=\Theta(mn)$ time-complexity. In fact, it is easy to see that asymptotically, solving the problem of co-reachability has the same worst-case time-complexity as solving the problem of reachability.

To summarize, the worse case to determine the reachability or co-reachability of a $n$-state DFA takes $\Theta(mn)$ time.

In this section, we will explain the exact meaning of the statement "all edges must be checked" for the case of reachable states.

(All edges by adversary) Let $G$ be a multi-graph $G$ of $n$ nodes and a start node $q_0$. Each node $q$ has exactly $m$ outgoing edges $\{q_\sigma\mid \sigma\in\Sigma \}$. The only way for us to know the other endpoint of $q_\sigma$ is to inquire from a truthful smart adversary $A$, who can config the other endpoint on the fly. Each inquiry must be "which node is the endpoint of $q_\sigma$ other than $q$?" for some $v$ and $\sigma$. The minimal number of inquiries needed to determine the set of reachable nodes from $q_0$ is $mn$.

Proof. Let $Q=\{q_0, q_1, \cdots, q_{n-1}\}$.

Here is $A$'s strategy to reply to the inquiry. Initialize $n$ empty set $S_q$, $q\in Q$. For an inquiry about $q_\sigma$ with $q=q_i$, there are five cases.

• if $i\lt n-2$ and $\#S_q\lt m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.

• if $i\lt n-2$ and $\#S_q= m-1$, reply that $q_\sigma= (q,q_{i+1})$. Add $\sigma$ to $S_q$.

• if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}\lt 2m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.

• if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}= 2m-1$, reply $q_\sigma=(q_{n-2}, q_{n-1})$ when $q=q_{n-2}$ and reply $q_\sigma=(q_{n-1}, q_0)$ when $q=q_{n-1}$. Add $\sigma$ to $S_q$.

• if $\#S_\sigma= m$, the inquiry must have been done before and, hence, reply the same as before.

I will leave the rest of the proof as an exercise.

Exercise 1. Finish the proof of "all edges by adversary". Show that $A$'s strategy is consistent in the sense that there is one such $G$ that all replies of $A$ are true. Furthermore, after $mn-1$ inquires, we cannot determine whether $q_{n-1}$ is reachable from $q_0$ or not.

Interested readers can do the following exercise that deals with NFA.

Exercise 2. the worse case to determine the reachability or co-reachability of a $n$-state NFA takes $\Theta(mn^2)$ time.

StackExchange Computer Science Q#102393, answer score: 2