Kellerautomat Akzeptanz per leeren Keller zu per Zustand

up:: AFS

Definition

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

• Neuer Anfangszustand $q_0^{\prime }$
• Neuer Zusatnd $f$ als einziger Endzustand.
• 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_0^{\prime },\epsilon ,f)|q\in Q\}$ (Neuer Endzustand)