Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use at least half of it's power set.
Thanks,
Matt
Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use at least half of it's power set.
Thanks,
Matt
One class of examples are the languages $L_n$ over $\{a,b\}$ defined by "the $n$th letter from the end of the string is $a$." It's easy to construct an $n+1$ state NFA for this, but any DFA requires $2^n$ states. Intuitively, the reason for this is because, as you're reading the string from left to right in your DFA, you never know when the end of the string is coming. So you always have to keep track of the last $n$ symbols because you never know if any of them might become the $a$ that you're looking for. There are $2^n$ possible sequences of last-$n$-symbols to keep track of, so the DFA requires $2^n$ states. I'll leave it as an exercise for you to formalize this argument (it's a good exercise if you haven't done it before).
What do you mean by "NFA will use at least half of it's power set."
According definition every NFA has equivalent DFA. DFA simulation of NFA (with $k$ states) will have $2^{k}$ states every state of DFA will be set of states of NFA