finite-automatadfacomputation

Is this DFA has already been minimized?


I tried to minimize this DFA through table-filling method:
enter image description here

So this is the table that I made for this figure:

enter image description here

We can conclude from this table that the figure is already minimized and we dont need to continue.
Is that correct?


Solution

  • We can use Myhill-Nerode to check whether the states of this DFA correspond to unique equivalence classes under the indistinguishability relation.

    Strings leading to State 1 can be followed by any string in the language and is the first we've looked at, so we must have such a state in a minimal DFA.

    Strings leading to State 2 cannot be followed by a to get an accepted string, so State 2 corresponds to a class distinct from State 1's.

    State 3 is not accepting and so must correspond to a class distinct from State 1 and State 2.

    State 4 is not accepting, so it's class cannot be the same as State 1's or State 2's. Strings leading to State 4 cannot be followed by b to get a string in the language, so State 4 is also distinct from State 3.

    State 5 is not accepting either, so it is distinct from State 1 and State 2. Strings leading to State 5 can be followed by a to get a string in the language, so State 5 is also distinct from State 3 and State 4.

    State 6 is not accepting, so it is also distinct from State 1 and State 2. It can be followed by either a or b to get a string in the language, so it is distinct from States 3, 4 and 5.

    State 7 is accepting, so it is distinct from States 3, 4, 5 and 6. Strings leading to State 7 can befollowed by either a or aa to get a string in the language, so State 7 is distinct from States 2 and 1, respectively.

    Because all of the states are distinguishable, the DFA is minimal for whatever language it accepts.