|
|
Bestandteile
Vieles erinnert an Automaten:
Speicher für die Eingabe und ein Lesewerkzeug zum Erkennen der Eingabezeichen.
Eine Art Kontrolle, in der das Wissen um die Sprache kodiert ist.
Zusätzlicher Speicher für Zwischenergebnisse.
Außerdem Handlungsvorschriften darüber, welche Schritte in Abhängigkeit von Eingabe und Zwischenergebnis ausgeführt werden können.
|
|
Steigen Sie in einen deterministischen Kellerautomaten und erfahren Sie, welche Informationen ihm zur Verfügung stehen.
Eine Rechnerumsetzung eines nicht-deterministischen Kellerautomaten bräuchte zusätzliche Informationen zum Wort oder zusätzlichen Speicher, um die Alternativen zu verwalten.
Ein Javaapplet gibt Ihnen einen Einblick in die Innenwelt eines deterministischen KA.
|
Umgang mit Nichtdeterminismus
Die abstrakten Maschinenmodelle wie Kellerautomat, Endlicher Automat oder Turingmaschine sind bei Nichtdeterminismus auf übernatürliche Art auf den richtigen Pfad geleitet worden.
Im Gegensatz dazu benötigen konkrete Umsetzungen einen Mechanismus, der den Nichtdeterminismus verwaltet.
Dies ist notwendig, da die geläufigen Rechner determinsitisch arbeiten und sie nicht die geringste Intuition darüber haben, welche Analyse die richtige sein könnte.
|
1
2
3
4
5
Beispiel