Frage:
Aufgabe 1: Akzeptanz durch Endzust¨ande 
Text erkannt:
Aufgabe 1: Akzeptanz durch Endzustände (schriftlich)
\( [20] \)
In der Vorlesung wurden PDA's als 6-Tupel \( \left(Z, \Sigma, \Gamma, \delta, z_{0}, \#\right) \) eingeführt, mit der Akzeptierung durch leeren Keller. Wir können ein solches 6-Tupel nun auch als 7Tupel betrachten, bei welchem die letzte Komponente die leere Menge ist. Diese letzte Komponente bezeichnen wir im Folgenden als die Menge der Endzustände und definieren einen PDA, welcher durch Erreichen eines Endzustandes akzeptiert, wie folgt:
Wir setzen nun \( \tilde{M}=\left(Z, \Sigma, \Gamma, \delta, z_{0}, \#, F\right) \), wobei mit \( F \subseteq Z \) die Menge der Endzustände bezeichnet wird. Der Automat \( M \) arbeitet auf \( Z \times \Sigma^{*} \times \Gamma^{*} \) genau gleich wie \( M \). Die von \( \tilde{M} \) durch Erreichen eines Endzustandes akzeptierte Sprache ist nun wie folgt definiert:
\( T(\tilde{M})=\left\{w \in \Sigma^{*} \mid \exists z \in F, V \in \Gamma^{*} \operatorname{mit}\left(z_{0}, w, \#\right) \vdash_{\tilde{M}}^{*}(z, \varepsilon, V)\right\} \)
Wir zeigen in dieser Aufgabe, dass die Menge der durch einen PDA mittels leerem Keller akzeptierten Sprachen genau gleich der Menge der durch einen PDA mittels Erreichen eines Endzustandes akzeptierten Sprachen ist.
(a) Sei \( M_{1}=\left(Z, \Sigma, \Gamma, \delta, z_{0}, \#, F\right) \) ein PDA mit \( F \neq \emptyset \), welcher durch Erreichen eines Endzustandes akzeptiert. Betrachten Sie den folgenden PDA
\( M_{2}=\left(Z \cup\left\{z_{0}^{\prime}, z_{e}\right\}, \Sigma, \Gamma \cup\{\Delta\}, \delta^{\prime}, z_{0}^{\prime}, \Delta, \emptyset\right) \)
mit \( \Delta \notin \Gamma \) und
(1) \( \delta^{\prime}\left(z_{0}^{\prime}, \varepsilon, \Delta\right)=\left\{\left(z_{0}, \# \Delta\right)\right\} \)
(2) \( \forall z \in Z, a \in \Sigma \cup\{\varepsilon\}, \forall A \in \Gamma: \delta(z, a, A)=\delta^{\prime}(z, a, A) \)
(3) \( \forall z \in F, A \in \Gamma \cup\{\Delta\}:\left(z_{e}, \varepsilon\right) \in \delta^{\prime}(z, \varepsilon, A) \)
(4) \( \forall A \in \Gamma \cup\{\Delta\}:\left(z_{e}, \varepsilon\right) \in \delta^{\prime}\left(z_{e}, \varepsilon, A\right) \)
Der Automat \( M_{2} \) akzeptiere bei leerem Keller. Zeigen Sie: \( T\left(M_{1}\right)=T\left(M_{2}\right) \).
(b) Sei \( M_{1}=\left(Z, \Sigma, \Gamma, \delta, z_{0}, \#, \emptyset\right) \) ein PDA mit Akzeptierung durch leeren Keller. Betrachten Sie den PDA
\( M_{2}=\left(Z \cup\left\{z_{0}^{\prime}, z_{f}\right\}, \Sigma, \Gamma \cup\{\Delta\}, \delta^{\prime}, z_{0}^{\prime}, \Delta,\left\{z_{f}\right\}\right) \)
mit \( \Delta \notin \Gamma \) und
In der Vorlesung wurden PDA’s als 6-Tupel (Z, Σ, Γ, δ, z0, #) eingefuhrt, mit der ¨
Akzeptierung durch leeren Keller. Wir k¨onnen ein solches 6-Tupel nun auch als 7-
Tupel betrachten, bei welchem die letzte Komponente die leere Menge ist. Diese
letzte Komponente bezeichnen wir im Folgenden als die Menge der Endzust¨ande und
definieren einen PDA, welcher durch Erreichen eines Endzustandes akzeptiert, wie
folgt:
Wir setzen nun M˜ = (Z, Σ, Γ, δ, z0, #, F), wobei mit F ⊆ Z die Menge der Endzust¨ande bezeichnet wird. Der Automat M˜ arbeitet auf Z ×Σ
∗ ×Γ
∗ genau gleich wie
M. Die von M˜ durch Erreichen eines Endzustandes akzeptierte Sprache ist nun wie
folgt definiert:
T(M˜ ) = {w ∈ Σ
∗
| ∃z ∈ F, V ∈ Γ
∗ mit (z0, w, #) `
∗
M˜
(z, ε, V )}
Wir zeigen in dieser Aufgabe, dass die Menge der durch einen PDA mittels leerem
Keller akzeptierten Sprachen genau gleich der Menge der durch einen PDA mittels
Erreichen eines Endzustandes akzeptierten Sprachen ist.
(a) Sei M1 = (Z, Σ, Γ, δ, z0, #, F) ein PDA mit F 6= ∅, welcher durch Erreichen eines
Endzustandes akzeptiert. Betrachten Sie den folgenden PDA
M2 = (Z ∪ {z
0
0
, ze}, Σ, Γ ∪ {∆}, δ0
, z0
0
, ∆, ∅)
mit ∆ ∈/ Γ und
(1) δ
0
(z
0
0
, ε, ∆) = {(z0, #∆)}
(2) ∀z ∈ Z, a ∈ Σ ∪ {ε}, ∀A ∈ Γ: δ(z, a, A) = δ
0
(z, a, A)
(3) ∀ z ∈ F, A ∈ Γ ∪ {∆}: (ze, ε) ∈ δ
0
(z, ε, A)
(4) ∀A ∈ Γ ∪ {∆}: (ze, ε) ∈ δ
0
(ze, ε, A)
Der Automat M2 akzeptiere bei leerem Keller. Zeigen Sie: T(M1) = T(M2).
(b) Sei M1 = (Z, Σ, Γ, δ, z0, #, ∅) ein PDA mit Akzeptierung durch leeren Keller.
Betrachten Sie den PDA
M2 = (Z ∪ {z
0
0
, zf }, Σ, Γ ∪ {∆}, δ0
, z0
0
, ∆, {zf })
mit ∆ ∈/ Γ und
1/3
TI1 WS2022/23 Ubungsblatt 6 ¨
(1) δ
0
(z
0
0
, ε, ∆) = {(z0, #∆)}
(2) ∀z ∈ Z, a ∈ Σ ∪ {ε}, ∀A ∈ Γ: δ
0
(z, a, A) = δ(z, a, A).
(3) ∀z ∈ Z: (zf , ε) ∈ δ
0
(z, ε, ∆).
Dieser PDA akzeptiert durch Erreichen eines Endzustandes. Zeigen Sie: T(M1) =
T(M2).
(c) Sei die folgende Sprache L uber dem Alphabet Σ = ¨ {a, b, c} gegeben:
L = {wcn
| w ∈ {a, b}
∗
, 2 · |w|a + |w|b = n, |w| ≥ 1}
Geben Sie einen DPDA M an mit T(M) = L.
Code:
