3
$\begingroup$

I have recently learned about using powerset construction for conversion of NFA to DFA - however this only seems to be feasible when the number of states we are working with are 3 or less, as $2^k$ seems to grow unmanageable very quickly.

I have a problem with 6 states, meaning that if I were to use powerset construction, I would have 64 states. What is a more efficient way?

$\endgroup$
  • 3
    $\begingroup$ Please ask only one question per question. $\endgroup$ – adrianN Sep 29 '16 at 13:46
  • $\begingroup$ Editing out question 2). You may ask it separately, but note that we don't do homework solving. What have you tried and where did you get stuck? $\endgroup$ – Raphael Sep 29 '16 at 19:29
6
$\begingroup$

Let me mention a variant of the powerset construction. In this variant, we are going to construct only states reachable from the initial state. The way it works is as follows:

  1. Create a list of states to-be-processed, and populate it initially with $\{q_0\}$, where $q_0$ is the initial state of the NFA.

  2. While the to-be-processed list is non-empty, remove a state $S$, and compute all states reachable from $S$ by reading one character. Put any of these which hasn't been encountered yet in the to-be-processed list.

This variant (which I haven't quite specified in full) constructs the powerset automaton restricted to states reachable from the (new) initial state, and runs in time proportional to the resulting number of states (and the alphabet size).

The same construction, and indeed the vanilla powerset construction, also works for NFAs with several initial states. The only difference is that we start with the set $Q_0$ of initial states (which is also going to be the initial state of the resulting DFA) rather than with $\{q_0\}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In addition to the strategies pointed out in other answers , You can also adopt the method of directly constructing a DFA by determining the number of equivalence classes for your problem which is equal to the number of states in your minimized automaton. However this approach is suitable for problems having few partitions for the strings but produces the results quicker relative to other methods.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please edit your answer to (only) answer the remaining question. $\endgroup$ – Raphael Sep 29 '16 at 19:31

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.