Suche Home Einstellungen Anmelden Hilfe

Minimierung 5: Beispiel

Der DEA M akzeptiert Wörter über dem Alphabet {a,b}, die mindestens einmal die Folge 'aa' enthalten.     Minimiert enthält der Automat nur noch drei Zustände die genau den Äquivalenzklassen [], [a] und [aa] entsprechen.

Anwendung des Verfahrens an einem Beispiel-EA. Gegeben sei der EA M in Graphendarstellung. So ergibt sich die folgende Tabelle von Zustandspaaren.  Im ersten Schritt wird jedes Paar bestehend aus Endzustand und Nichtendzustand mit '*' markiert. Im Beispiel alle Paare, in denen q4 vorkommt. Jetzt werden alle Paare {q,q'} markiert, wenn das Paar {(q,a), (q',a)} markiert ist (a aus ). Der Vorgang wird so lange wiederholt, bis keine Änderungen auftreten. Folgende Paare entstehen bei der Anwendung des Algorithmus: {q0,q1}   a  {q1,q4}   *   b  {q2}   {q0,q2}   a  {q1,q3}     b  {q2}   {q0,q3}   a  {q1,q4}   *   b  {q0,q2}   {q1,q2}   a  {q3,q4}   *   b  {q2}   {q1,q3}   a  {q4}     b  {q0,q2}   {q2,q3}   a  {q3,q4}   *   b  {q0,q2}   q1   q2     q3       q4 * * * * q0 q1 q2 q3 q1 * q2   * q3 *   * q4 * * * * q0 q1 q2 q3 Die Paare {q0,q2} und {q1,q3} bleiben unmarkiert und können verschmolzen werden. Warum müssen die Paare {q,q} = {q} (mit q aus Q) nicht berücksichtigt werden?  Arbeiten Sie Schritt für Schritt an einer Beispielaufgabe.

Verfahren 1   2   3   4   5   6 Übersicht: Sprachklassen

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: