patternMinor
Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)
Viewed 0 times
dfanumberthenfawhoselesserwithoutunreachablestatesthan
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#88865, answer score: 2
Revisions (0)
No revisions yet.