Talk:Powerset construction

From Wikipedia, the free encyclopedia

Very nice example and description.

Small remark: I don't see the purpose of the ∅ state and the transition from state {4} in the DFA of the example:

It's rather confusing. A DFA does only accept an input if it has reached the end of the word. For example, the input '0001' would cause the sample DFA to block at {4} (having an input but no matching transition) and thus reject the word. --Code Wizard 23:45, 27 Jan 2005 (UTC)

Hi Code Wizard, thanks for your feedback. To answer your question, technically, this is not the case — this is only a convenient convention commonly used in drawings of DFAs. In the formal definition of a DFA, it is specified that there is exactly one transition out of each state on each character. If the edges are not drawn, it's assumed they lead to some inescapable non-accepting state such as the one drawn above. I chose to be more explicit about this in this instance, for clarity. Deco 07:06, 29 Jan 2005 (UTC)