Material OOP Grundlagen Delphi Software-Technik Bonsai Digitaltechnik Ereignisse Grafik UML Netze Fischertechnik Tipps Werkzeuge Literatur Automaten Sprachen Datenbanken XML Prolog Berechenbarkeit
Pfad: Startseite / Fächer / Informatik / Material
Autor: mk
09.05.2004 11:09
2356
Automatentheorie

Vierertester

Aufgabe

Ein endlicher Automat sei durch folgenden Graphen (aus Gasper, Leiß, Spengler, Stimm, Technische und theoretische Informatik, S.134) beschrieben:
Gib an:
  1. Eingabealphabet E
  2. Ist der Automat ein Transduktor oder ein Akzeptor?
    Gegebenenfalls Ausgabealphabet A
  3. Zustandsmenge Z
  4. Automatentafel
  5. Start- und Endzustände
  6. Funktion des Automaten

Lösung

Am Graphen kann man ablesen:
  • Zustände = {z,z0, z1, z00, z01, z10, z11};
  • Anfangszustand = z;
  • Endzustände = {z00};
  • Eingabealphabet = {0, 1}
  • kein Ausgabealphabet, Automat ist ein Akzeptor
Automatentafel

z z0 z1 z00 z01 z10 z11
0 z0 z00 z10 z00 z10 z00 z10
1 z1 z01 z11 z01 z11 z01 z11


Der Automat befindet sich nur dann in einem akzeptierenden Zustand, wenn die beiden letzten Zeichen 00 waren. Fasst man die Zeichenkette als Dualzahl auf, so heißt das, dass die Zahl durch 4 teilbar ist.

Einen viel einfacheren Vierertester zeigt folgender Automatengraph: