|
Verarbeitung der Eingabe von links nach rechts in einem Zug
Verarbeitung der Eingabe von rechts nach links in einem Zug
Verarbeitung der Eingabe mit Sprüngen von "Insel" zu "Insel"
|
Mehrere Möglichkeiten sind denkbar.
Automaten verarbeiten den Input Zeichen für Zeichen.
Endliche Automaten und Kellerautomate können das Eingabewort genau einmal von links nach rechts durchlaufen.
Sie sind also einerseits in der Verarbeitungsrichtung beschränkt (von links nach rechts)
und andererseits in der Anzahl der Durchläufe (einmaliges Lesen).
TM und LBA können auf beliebige Weise den Input lesen.
Der Lese-/Schreibkopf kann vor und zurück laufen.
Sie sind damit weder auf das einmalige Durchlaufen der Eingabe noch auf eine bestimmte Verarbeitungsrichtung beschränkt.
Aber auch Variationen der Verarbeitungsrichtung sind denkbar:
von rechts nach links; oder mit Sprüngen durch die Eingabe - das sogenannte Islandparsing.
| Verarbeitungsrichtung | | Anzahl der Durchläufe |
|---|
| von links nach rechts (left-to-right) |
|
einmaliges Durchlaufen (one-pass) |
| von rechts nach links (right-to-left) |
|
mehrmaliges Durchlaufen |
| mit Sprüngen (island) |
|
|
|
1
2
3
4
5
6
7
Alternativen