Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

KA1: wieso nicht mit zwei Zuständen?

–1 Punkt
42 Aufrufe

Noch einmal: Kellerautomat 1, wieso nicht mit zwei Zuständen:

ich habe P so definiert:

P = {S--> aSb|aAb

        A-->bAa|ba }

Um von S nach A zu kommen muss ich mind. einmal (=> m >= 1) 0A1 ausführen und um abzuschließen muss ich aus A mind. einmal (=> n>= 1) 10 machen.

Somit ist doch m,n >= 1 gewährleistet, wo ist da der Fehler?

 

Gefragt 21, Sep 2015 in HU-2-3 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

Deine Grammatik ist denke ich auch richtig.

Viele Grüße

Christiane (Tutorin)

 

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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?
Ich würde dir zustimmen, der KA müsste auch funktionieren.

Viele Grüße

Christiane (Tutorin)
...