Reguläre Typen

Als natürliches Mittel, das dynamische Verhalten von Objekten zu beschreiben, bieten sich abstrakte Automaten an. Aus algorithmischer Sicht ist es wünschenswert, nur Automaten mit endlicher Zustandsmenge zu verwenden, die dann auch als reguläre Prozesse bezeichnet werden. Die Spezifikation eines regulären Prozesses wir als regulärer Typ bezeichnet. Ein regulärer Typ, der das Verhalten des einfachen Zwischenspeichers $Buf$ spezifiziert, könnte z. B. folgendermaßen aussehen

Zur Beschreibung eines solchen Zwischenspeichers-Objektes reichen also zwei abstrakte Zustände aus. Anders stellt sich die Situation im Falle eines Stack-Objektes dar. Hier wäre mindestens für jeden Füllstand ein eigener Zustand nötig. Da reguläre Typen aber nur endliche Zustandsmengen zulassen, muss das Verhalten eines Stacks durch nichtdeterministische Übergänge approximiert werden. Ein einfacher regulärer Typ $NDStack$ für einen Stack könnte z. B. so aussehen

Ein Stack könnte aber auch durch den regulären Typ $NDStack2$ modelliert werden