next up previous
Next: deterministische und nichtdet. Kellerautomaten Up: Arbeitsweise Previous: Zustandsbeschreibungen (Konfigurationen)

Akzeptierte Sprachen

Der Kellerautomat \( KA=(Z,X,Y,\delta ,z_{0},y_{0},F) \) kann auf 2 verschiedene Arten eine Sprache akzeptieren:

1.
Menge aller Sprachen, die zu leerem Keller führen: \( L_{\epsilon }(KA)=\{p\vert p\in X^{*} \)und \( \exists z\in Z:(z_{0},p,y_{0})\vdash ^{*}(z,\epsilon \, \epsilon )\} \).
2.
Vom Kellerautomaten mit Endzustand akzeptierte Sprache: \( L_{f}(KA)=\{p\vert p\in X^{*}\wedge (z_{0},p,y_{0})\vdash ^{*}(z_{f},\epsilon \, q) \) mit \( z_{f}\in F \) und \( q\in Y^{*}\} \).
Bem: Zu jedem durch Endzustand akzeptierenden Kellerautomaten K existiert ein K' der die Sprache durch leeren Keller akzeptiert und andersherum.



Thomas Rabe
1999-09-23