Kellerautomat Akzeptanz per Zustand zu per leeren Keller

Definition

$A=(Q,\Sigma ,\Gamma ,q_0,Z_0,△,F)$
zu
$B=(Q\cup \{q_0^{\prime },q_1^{\prime },\Sigma ,\Gamma \cup \{Z_0^{\prime }\},q_0^{\prime },Z_0^{\prime },{△}^{\prime }\})$

• Neuer Anfangszustand $q_0^{\prime }$
• Neuer Zusatnd $q_1^{\prime }$ zum Leeren des Kellers.
• Ein neues Kellerstartsymbol $Z_0^{\prime }$
• ${△}^{\prime }=△$
  $\cup \{(q_0^{\prime },\epsilon ,Z_0^{\prime },Z_0{Z}_0^{\prime },q_0)\}$ (Neuer Startzustand)
  $\cup \{(q,\epsilon ,Z,\epsilon ,q_1^{\prime })|q\in F,Z\in \Gamma \cup \{Z_0^{\prime }\}\}$ (Neuer Endzustand)
  $\cup \{(q_1,\epsilon ,Z,\epsilon ,q_1^{\prime })|Z\in \Gamma \cup \{Z_0^{\prime }\}\}$ (Leeren des Kellers)

⇒ Endzustand wird erreicht genau dann, wenn Keller von B leer wird.