Folgende Eingabe soll akzeptiert werden: , . Hierbei sollen auf viele exakt viele folgen. Im folgenden folgen DEAs die "versuchen" das Problem zu lösen. An diesen Beispielen wird deutlich, warum wir einen Zwischenspeicher (Keller) brauchen.
DEA 1:
Dieser Automat akzeptiert zwar alle geforderten Eingaben, aber er akzeptiert auch weitere, die nicht akzeptiert werden sollen. Auch wird deutlich, dass der Automat nach dem Übergang in keine Information mehr darüber hat, wie viele vorher eingegeben wurden.
DEA 2:
Dieser Automat akzeptiert auch alle geforderten Eingaben und auch nur diese. Da allerdings das unendlich groß sein könnte, müsste dieser Automat auch unendlich lang sein. In der Skizze akzeptiert der abgebildete Automat alle Eingaben bis .
Keller-Automat:
Zusätzlich zum Eingabealphabet wird auch ein Kelleraplhabet definiert. Standardmäßig ist das oberste und einzige Zeichen die im Keller, um zu kennzeichnen, dass dieser leer ist.
Um es deutlich zu machen, verwenden wir hier Großbuchstaben im Kelleralphabet:
Syntax der Übergänge: Oberstes Kellersymbol Eingabesymbol Kellerwort
Bei der Verarbeitung wird das oberste Kellersymbol (vom Stapel) und das Eingabesymbol entnommen und das Kellerwort erneut auf den Stapel gelegt
Ablauf der Eingabe :
- Start in
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
-
- Eingabe:
- Keller:
- Eingabe:
- Keller: