zu (a)
Hallo,
wir haben diesen KA auch mit nur 2 Zuständen konstruiert.
Im Zustand s0 schreiben wir m mal ein a und n mal ein b. folgt dann ein a auf ein b kommt ein zustandswechsel in s1, wo wir dann für jedes "neue" a ein (schon geschriebenes) b löschen und für jedes "neue" b ein (schon geschriebenes) a löschen.
Und zwar folgendermaßen:
(s0,a,k0) -> (s0,ak0)
(s0,a,a) -> (s0,aa)
(s0,b,a) -> (s0,ba)
(s0,b,b) -> (s0,bb)
(s0,a,b) -> (s1,lambda)
(s1,a,b) -> (s1,lambda)
(s1,b,a) -> (s1,lambda)
(s1,lambda,k0) -> (se, k0)
Geht das so nicht auch?