Automaten-Simulator

Binärzahl modulo 3

Eingabewort

Schrittlimit

Wort aus den Symbolen 0, 1. Ein leeres Feld ist das leere Wort ε.

Idee

Akzeptiert genau die Binärwörter, deren Wert durch 3 teilbar ist. Der Zustand merkt sich den Rest der bisher gelesenen Zahl: Ein angehängtes Bit b macht aus dem Wert x den Wert 2x + b.

Ein deterministischer endlicher Automat (DFA) hat in jedem Zustand für jedes Symbol genau einen Pfeil. Er liest das Wort Symbol für Symbol und folgt dabei den Pfeilen. Steht er nach dem letzten Symbol in einem akzeptierenden Zustand (Doppelkreis), ist das Wort akzeptiert.

Protokoll

Start.

Ergebnis für dieses Wort

Eingabewort: 110; 3 Symbole
Ergebnis: Akzeptiert
Gelesen: 3 von 3
Zustand am Ende: q0

Eingabe vollständig gelesen, der Automat steht im akzeptierenden Zustand q0.

Mehr zum deterministischen endlichen Automaten (DFA)