Suche Home Einstellungen Anmelden Hilfe  

Minimierung 5: Beispiel

Der Beispielautomat M hat 5 Zustände .
Der DEA M akzeptiert Wörter über dem Alphabet {a,b}, die mindestens einmal die Folge 'aa' enthalten.
 
 

Der minimierte Automat M'
Minimiert enthält der Automat nur noch drei Zustände die genau den Äquivalenzklassen [epsilon], [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 {delta(q,a), delta(q',a)} markiert ist (a aus Sigma).
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: matthias • Zuletzt geändert am: