Nie można przekonwertować z NFA na DFA

Mam prosty problem z utworzeniem DFA, który akceptuje wszystkie dane wejściowe zaczynające się od podwójnych liter (aa, bb) lub kończące się na podwójnych literach (aa, bb), biorąc pod uwagę, że jest zestawem alfabetu dany język.$\Sigma =\{a, b\}$

Próbowałem rozwiązać to w sposób okrężny:

1. Generowanie wyrażenia regularnego
2. Tworzenie odpowiedniego NFA
3. Wykorzystanie konstrukcji zestawu zasilającego do ustalenia DFA
4. Minimalizowanie liczby stanów w DFA

Krok 1: Wyrażenie regularne dla danego problemu to (wśród niezliczonych innych):

((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb))

Krok 2: NFA dla danego wyrażenia to:

_{(źródło: livefilestore.com )}

W formie tabelarycznej NFA to:

State    Input:a     Input:b
->1        2,5         3,5
  2        4           -
  3        -           4
 (4)       4           4
  5        5,7         5,6
  6        -           8
  7        8           -
 (8)       -           -

Krok 3: Przekształć w DFA za pomocą konstrukcji powerset:

Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)
   ->A, {1}         |        B, {2,5}           |        C, {3,5}
     B, {2,5}       |        D, {4,5,7}         |        E, {5,6}
     C, {3,5}       |        F, {5,7}           |        G, {4,5,6}
   (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}
     E, {5,6}       |        F, {5,7}           |        I, {5,6,8}
     F, {5,7}       |        J, {5,7,8}         |        E, {5,6}
   (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}
   (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}
   (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}
   (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}
   (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8}

Krok 4: Zminimalizuj DFA:

Najpierw zmieniłem K-> G, J-> F, I-> E. W następnej iteracji H-> D i E-> F. Tak więc stół finałowy to:

  State    +   Input:a     +   Input:b
   ->A     |      B        |      C
     B     |      D        |      E
     C     |      E        |      D
    (D)    |      D        |      D
    (E)    |      E        |      E

I schematycznie wygląda to tak:

_{(źródło: livefilestore.com )}

... co nie jest wymaganym DFA! Potrójnie sprawdziłem swój wynik. Więc gdzie popełniłem błąd?

Uwaga:

• -> = stan początkowy
• () = stan końcowy

W porządku do kroku 3 (DFA), ale minimalizacja jest nieprawidłowa.

Oczywiste jest, że zminimalizowany DFA jest niewłaściwy, ponieważ zarówno dane wejściowe, jak bai ab(które nie są w oryginalnym języku, ani nie są akceptowane przez DFA w kroku 3) prowadzą do stanu końcowego E.

Patrząc na kroki minimalizacji, wydaje się, że ujednolicono stany końcowe i nie-końcowe; na przykład J (finał) -> F (nie finał) i I (finał) -> E (nie finał). Połączenie stanu końcowego ze stanem nie-końcowym zmienia język akceptowany przez automat, co prowadzi do akceptacji niepoprawnych ciągów, jak wspomniano powyżej.