Konvertierung von NFA nach DFA nicht möglich

11

Ich habe ein einfaches Problem damit, einen DFA zu erstellen, der alle Eingaben akzeptiert, die mit Doppelbuchstaben (aa, bb) beginnen oder mit Doppelbuchstaben (aa, bb) enden, vorausgesetzt, Σ={ein,b}} ist die Alphabetmenge der angegebenen Sprache.

Ich habe versucht, es auf Umwegen zu lösen, indem ich:

  1. Generieren eines regulären Ausdrucks
  2. Herstellung der entsprechenden NFA
  3. Verwenden der Powerset-Konstruktion zum Ableiten eines DFA
  4. Minimierung der Anzahl der Zustände in DFA

Schritt 1: Regulärer Ausdruck für ein gegebenes Problem ist (unter unzähligen anderen):

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

Schritt 2: NFA für den gegebenen Ausdruck ist:

NFA
(Quelle: livefilestore.com )

In tabellarischer Form lautet NFA:

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)       -           -

Schritt 3: Konvertieren Sie mithilfe der Powerset-Konstruktion in einen DFA:

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}

Schritt 4: Minimieren Sie den DFA:

Ich habe zuerst K-> G, J-> F, I-> E geändert. In der nächsten Iteration H-> D und E-> F. Somit ist der Final Table:

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

Und schematisch sieht es so aus:

Endgültiger DFA
(Quelle: livefilestore.com )

... was nicht der erforderliche DFA ist! Ich habe mein Ergebnis dreifach überprüft. Also, wo bin ich falsch gelaufen?

Hinweis:

  • -> = Ausgangszustand
  • () = Endzustand
Anurag Kalia
quelle
3
Dies ist ein großartiges Beispiel für eine grundlegende Frage, die gut gestellt wurde, weil Sie Ihren gesamten Gedankengang einbeziehen.
Raphael
Fühlt sich toll an, geschätzt zu werden, danke! ^^
Anurag Kalia

Antworten:

5

Sie sind bis zu Schritt 3 (dem DFA) in Ordnung, aber Ihre Minimierung ist falsch.

Es ist klar, dass der minimierte DFA nicht richtig ist, da sowohl die Eingaben baals auch ab(die nicht in der Originalsprache sind oder vom DFA in Schritt 3 akzeptiert werden) zum endgültigen Zustand führen E.

Wenn Sie sich Ihre Minimierungsschritte ansehen, scheinen Sie einheitliche End- und Nichtendzustände zu haben. Zum Beispiel J (endgültig) -> F (nicht endgültig) und I (endgültig) -> E (nicht endgültig). Durch das Zusammenführen eines Endzustands mit einem Nicht-Endzustand wird die vom Automaten akzeptierte Sprache geändert, was zur Annahme falscher Zeichenfolgen führt, wie oben angegeben.

Rici
quelle
1
Oh. Das ist es also, was hier zu Problemen führt. Nun, da ich mich erinnere, gab es beim letzten Mal, als ich diese Methode verwendete, überhaupt keine besonderen Akzeptanzzustände in der Tabelle!
Anurag Kalia