Search code examples
automatadfanfa

Meaning of combined states in DFA

enter image description here

When converting and NFA to a DFA, sometimes the states have to be merged. Like in the above scenario.

But what does it really mean by 'combining the states into one' in a real scenario?

And what would the nature of the combination of above two states be?

Solution

  • The phrase combining the states into one means, that you

    1. Create a new state, which is labelled with all labels from the original states.
    2. The new state gets all output and all conflicting (ambiguous) input transitions from the original states.
    3. Each combination of the original labels may occur only in one new condition.

    Note: Creating a new state with a single label in the DFA can be seen as a special case of the above.

    The naming of the new state with the labels of the original states has the sense that you can refer unambiguously to this new state in the subsequent generation process.