3
$\begingroup$

I'm stuck with another homework question - "Design an NFA with $n$ states such that the corresponding equivalent DFA constructed using the subset-construction method has less than $n$ states."

What I have learnt is that using subset (or powerset) construction, you can convert a given NFA with $n$ states to it's equivalent DFA with atmost $2^n$ states. I've tried constructing NFA's and tried converting them to check their equivalent DFA's number of states, with multiple attempts, but in vain.

DFA with less states than NFA

The above question tackles the possibility of a DFA having less than equivalent states to it's corresponding NFA. The question, as mentioned in some comments, doesn't take into account the fact that a DFA can have multiple equivalent NFAs, and also suggests the solution of having unreachable states to solve the problem.

Now, this does offer a solution to my homework problem, as the given problem doesn't specify that I shouldn't use unreachable states. Regarding epsilon moves, I believe my professor mentioned not to use them, if not said in the question, or indicated as an option to use, in the given question. Regardless, I can solve my problem by adding unreachable states. But that is not my question, here.

My question is, given an arbitrary NFA with $n$ states, to begin with. (without $\epsilon$ moves or unreachable states). Is there any specific case, where the NFA (please provide an example) under said conditions is such that I can use subset construction and get a DFA with less than $n$ states?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider an automaton with $n$ states, all final, and a transition between every pair of states for every symbol.

There are two variants of the subset construction. A "formal" one where always $2^n$ subsets are considered, and a "practical" one, where you consider only states that are reachable. Of course only the latter interpretation of subset construction will work.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This approach works, although only for $n > 3$, right? The latter "practical" method for subset construction, is the convenient one, but, why do you say that only the latter interpretation will work? The former also does in all cases, right? What's wrong with the generic formal method? $\endgroup$
    – Vishhvak Srinivasan
    Mar 4, 2018 at 13:48
  • $\begingroup$ Also, could you explain the intuition behind the idea as well? $\endgroup$
    – Vishhvak Srinivasan
    Mar 4, 2018 at 13:49
  • $\begingroup$ @VishhvakSrinivasan The "formal" construction starts with state set $Q$ of $n$ elements and (by construction) gives a new automaton with state set $2^Q$ (the powerset of $Q$ which has exactly $2^n$ elements. This construction of course is valid, but does not answer your question, too much states. $\endgroup$
    – Hendrik Jan
    Mar 5, 2018 at 2:13
  • $\begingroup$ Yes, that part I understand. It is valid, is what I wanted to confirm. Could you also explain the intuition behind how you arrived at "Consider an automaton with n states, all final, and a transition between every pair of states for every symbol." ? $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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