Akzeptierte Sprachen

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

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