Suche Home Einstellungen Anmelden Hilfe  

3.2.2 Deterministische Kellerautomaten

KA ohne Konflikte zwischen:
epsilon/nicht-epsilon- Übergang
Das oberste Kellersymbol ist A und der Automat kann unabhängig von der Eingabe in den Zustand p1 wechseln
oder er kann in den Zustand p2 wechseln, wenn die aktuelle Eingabe ein a ist,
nicht-epsilon-/nicht-epsilon- Übergang
Liest der Automat ein a in der Eingabe und ist das oberste Kellersymbol A, so hat er die Möglichkeit sowohl nach p1 als auch nach p2 zu wechseln

Deterministische Kellerautomaten sind ähnlich wie nicht-deterministische aufgebaut. Ein KA ist deterministisch, wenn die folgenden zwei Bedingungen erfüllt sind:

  1. Es tritt kein Konflikt zwischen einem epsilon-move und einem nicht-epsilon-move auf.
    Forderung: delta(q,a,Z) muss leer sein, wenn delta(q,epsilon,Z) nicht leer ist
  2. Es tritt kein Konflikt zwischen verschiedenen nicht-epsilon-moves auf.
    Forderung: delta(q,a,Z) darf maximal 1 Element enthalten.
Dies muss für alle q aus Q, alle a aus sigma und alle Z aus gamma erfüllt sein.

Nicht für jede Sprache, die mit einem Nicht-Deterministischen KA beschrieben werden kann, lässt sich ein Deterministischer KA finden. Ein Beispiel für eine Sprache, die nicht von einem deterministischen Kellerautomaten beschrieben werden kann, ist die Spiegelsprache. In dieser Sprache besteht jedes Wort aus zwei Teilwörtern über einem 2-Elementigen Alphabet, z.B. {a,b}, wobei das zweite Teilwort eine exakte Spiegelung des ersten Teilwortes ist. Der Automat kann nicht wissen, wann der gespiegelte Teil des Wortes anfängt, bevor er nicht das gesamte Wort gelesen hat.

Auch Palindrome haben diese Spiegeleigenschaft. Palindrome können sowohl von vorn als auch von hinten gelesen werden. Beispiele sind 'otto', 'nennen'. Aber auch ganze Sätze kann man konstruieren, wie z.B. 'Einsen essen es nie' (wobei die Leerzeichen nicht beachtet werden).

Sprache 1   2   3   4   5   6   Übersicht: Sprachklassen

Benutzer: Gast • Besitzer: senn • Zuletzt gešndert am: