Im Keller befinden sich nie 2 $a$.
$$(s_0,a,a) \rightarrow (s_1,a)$$
überschreibt das im Keller vorhandene $a$ durch ein $a$. Der Keller bleibt also unverändert. Mit
$$(s_0,a,a) \rightarrow (s_1,aa)$$
könnte man 2 $a$ in den Keller schreiben. Ich vermute das war dein Probem.
Sven (Tutor)