1
$\begingroup$

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

  • 0
    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.2011-09-27

2 Answers 2

0

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

  • 0
    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!2011-09-27
0

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

  • 0
    @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}$.2011-09-27