|
|
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.
|
],
[a] und [aa] entsprechen.