Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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