# NFA to DFA conversion, half the power set

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 is the languages of the form "set of all strings over {a,b} where the n-th letter from the end is an a" (fixed n). I don't know of a general theory, but usually, if the language is defined by some behavior at the end of the string, the NFA to DFA conversion will blow up exponentially. – Ted Sep 27 '11 at 3:45

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).

-
Hmm, interesting. Ill look into this. Basically you are saying for example something like (aUb)*a(aUb)(aUb) if n = 3, since a would be 2 letters from the end? – Matt Sep 27 '11 at 5:21
Yes, that's right. (I assume you mean "$a$ would be 3 letters from the end" rather than 2.) – Ted Sep 27 '11 at 5:28
sorry yes, i just made me some caffeinated tea :). Although i did construct a NFA in JFLAP, did a quick conversion, but I'm not getting what it should be. Is there a more succinct way to create this NFA and I'm just not doing it correctly? – Matt Sep 27 '11 at 5:31
I don't know what JFLAP is; is it some automated tool to convert regular expressions to NFAs? I'm guessing that such tools usually give more complicated than necessary constructions. In this case, the NFA is simple enough that you should be able to construct it by hand. – Ted Sep 27 '11 at 5:49
Yea you can create DFAs and NFAs as if you were writing it on paper and it will reduce NFAs to DFAs. But anyway, i was just being stupid and adding more states than i needed. But yes, this should work. Thanks! – Matt Sep 27 '11 at 6:04

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

-
But some states of the resulting DFA will be useless, or can be merged with other states. There is a unique minimum state DFA for a regular language: en.wikipedia.org/wiki/DFA_minimization – Ted Sep 27 '11 at 3:48
@com yea what ted said. There will be states that are useless or even if you don't minimize it and merge and combine, there will be states that you can't even get to. While yes, you will create a power set, you really don't need to. You can just see what you do need as you go along and convert it from an NFA to DFA. – Matt Sep 27 '11 at 3:50
Of course we should consider only reachable states from initial state (but in general it's $2^k$) – com Sep 27 '11 at 3:52
@com: Well, the empty set is never reachable so it's surely no more than $2^k - 1$ :) More seriously, do you know of an example where a $k$-state NFA actually requires $2^k - 1$ states when converted to a DFA? The best examples I know are only $2^{k-1}$. – Ted Sep 27 '11 at 4:09