Partielle Zustandsübergangsgraphen und Fehlerzustände

Der Zustandsübergangsgraph zum Passwortschutz ist partiell. Das heißt, dass einige Zustandsübergänge nicht abgebildet sind. Beispielsweise kann im Startzustand kein Sonderzeichen oder Zahlzeichen gemäß des Übergangsgraphen verarbeitet werden. Da es aber für jedes Eingabezeichen in jedem Zustand einen Folgezustand geben muss, müssen auch die fehlenden Zustandsübergänge definiert sein.

Eine gängige Konvention in der theoretischen Informatik ist es, dass der Automat beim Lesen eines Eingabezeichens, für das kein Zustandsübergang angegeben ist, in einen Fehlerzustand gelangt. In diesem Fehlerzustand bleibt der Automat beim Lesen jedes weiteren Eingabezeichens des Eingabewortes. Nach Lesen des letzten Eingabezeichens wird das Eingabewort abgelehnt. 

Dieser Fehlerzustand wird bei der Vervollständigung eines DEA ergänzt und fehlende Zustandsübergänge werden notiert, indem jeweils ein Zustandsübergang zum Fehlerzustand notiert wird. 

Falls kein vollständiger Übergangsgraph gefordert ist, können beim Erstellen eines Übergangsgraphen - mit der oben genannten Konvention - Zustandsübergänge zu einem Fehlerzustand weggelassen werden.

  1. Überführen Sie den Zustandsübergangsgraphen zum Passwortschutz in eine Zustandsübergangstabelle. Da der Übergangsgraph partiell ist, bleiben einige Einträge leer. Markieren Sie diese mit einem ‘-‘.

  1. Vervollständige Sie den partiellen Zustandsübergangsgraphen zum Passwortschutz.