0
$\begingroup$

Goal: convert NFA -> DFA
Overall goal: see if the intersection of 2 of these NFAs is empty.
This will be done by converting to DFAs then DFA intersection.

input NFA: multigraph between states (each edge has 1 alphabet symbol xor epsilon)

The NFA happens to look like a linear list of states:
${S_1, S_2, ..., S_n}$
where edges only exist from $S_{i}$ to $S_{i+1}$

$S_1$ is the start state
$S_n$ is the only accepting state

Known NFA -> DFA algorithm: SC (subset construction) (exponential in worse case).

Given the constraints on the NFA, is SC provably polynomial?
Given the constraints on the NFA, is there a more efficient conversion algorithm?

Here we're measuring efficiency as runtime: a function of $n$, the number of NFA states.

$\endgroup$
5
  • $\begingroup$ Efficiency in terms of runtime asymptotic behavior - anything better than exponential worst case. I define a linear directed multigraph (I will update to say directed) as a linear directed graph, but allowing multiple edges between the nodes that a linear graph only allows one edge between, i.e. a linear multigraph would be a multigraph where the intermediate nodes have arbitrary in and out degree, but the same source or target node among all edges. I will update the question. $\endgroup$
    – ScootyPuff
    Apr 27, 2020 at 14:12
  • $\begingroup$ I suggest you try a few examples with (say) up to 5 states to get a feeling for how the transition function affects the subsets. Try to find properties of the subsets, that always stay the same, irrespective of the linear NFA you started off with. This should not be overly difficult to find such invariant properties. $\endgroup$ Apr 27, 2020 at 16:16
  • $\begingroup$ Doesn't the answer at cs.stackexchange.com/q/124815/755 provide a solution to this? Can you elaborate on in what way that doesn't meet your needs? $\endgroup$
    – D.W.
    Apr 27, 2020 at 19:41
  • $\begingroup$ See my comment to the answer there. That is for a linear graph, whereas this is for a linear multigraph. Epsilon transitions make the NFA not already a DFA. $\endgroup$
    – ScootyPuff
    Apr 28, 2020 at 22:15
  • $\begingroup$ I have an answer if anyone wants to try to formalize it better: After each set of NFA nodes is processed, at least the earliest node will not be processed again, as there are no transitions to it. This means that the number of steps is bounded by the number of nodes. Each step can be performed in at worst time linear to the size of the NFA. Therefore, the running time is at most quadratic. Furthermore, each step may produce at most one DFA node. Therefore, the number of DFA nodes is at most linear with respect to the number of NFA nodes. $\endgroup$
    – ScootyPuff
    May 6, 2020 at 17:19

0

Your Answer

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

Browse other questions tagged or ask your own question.