I must have taken a stupid pill yesterday. In the northern hemisphere Orion sets before the dogs or the rabbit, just like in the Southern hemisphere. The only thing he is chasing, is the bull.
Today was devoted to watching Futurama commentaries, preparing notes for my model checking course, and thinking about automata. So there is little to report, other than the fact that Wikipedia, which seems so complete, is curiously lacking in information about automata theory. For example, they do not seem to mention that the DFA equivalent to an NFA may be exponentially bigger, or to give an example of a case where it turns out to be so. I also made my first (very small) contribution to Wikipedia. It is such a useful resource that one ought to contribute, I suppose.
Umm, tired, so I’m going to bed. But I’ll mention one last factoid. I have this week started to use hot water bottles to heat my bed. It has not been necessary last night or tonight. Both of the last two days have been very summery, and so have the nights. It’s about 15 degrees, and during the day the temperature reached 24 degrees. But such days are becoming scarcer and scarcer. I do not believe that the coming winter will be any milder, and I really wish it would start. The sooner it starts, …
they do not seem to mention that the DFA equivalent to an NFA may be exponentially bigger, or to give an example of a case where it turns out to be so.
Is it true that for all the algorithms that construct them, there is a case where the DFA is exponentially bigger, or is it just a property of the subset-algorithm? The subset algorithm does not do minimal DFAs. Though, I do think they are also exponentially bigger.
However, a proof that the exponentiality holds for all encodings of DFAs, could, I think, be used to prove that PSPACE is not P, something I think has not yet been proven. I may be mistaken, due to sleep deprivation.
The subset construction does not always construct minimal DFA’s. (In fact, in a recent paper, my co-authors and I investigated just how often this happens. It turns out that for a 5-state 2-symbol NFA the average DFA has 2.68 extra states; this average shrinks as the number of states grows, but grows as the size of the alphabet grows!. And for special types of automata called symmetric-difference NFA, the subset construction almost always results in a minimal DFA.)
But of course there is an (infinite) family of languages for which the DFA is always exponentially bigger. For example, suppose that the alphabet is {0,1}. The minimal NFA for the regular language “{0,1}*s”, where s is some fixed k-letter word over {0,1}, has k+1 states, while the minimal DFA has 2^k states.
Small correction. The regular language should be “{0,1}*0{0,1}^(k-1)”. In other words, there the k-th last letter is “0″. If you don’t know regular languages, just close your eyes and go to your “safe” place.
I see what you mean and I do agree.