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.)

alternativlösung

+2 Punkte
118 Aufrufe

A = ({0,1, &) , (s1, s2 ,s0 , se) , (a, k0), δ, s0, k0, {se} )

δ :  {(s0, 1, ko) -> (s1, ak0) ;

(s0, 0, ko) -> (s1, ak0) ;

(s0, &, ko) -> (s2, k0) ;

(s1, 0, a) -> (s1, aa) ;

(s1, 1, a) -> (s1, aa) ;

(s1, &, a) -> (s2, a) ;

(s2, 0, a) -> (s2, a) ;

(s2, 1, a) -> (s2, lambda) ;

(s2, lambda, ko) -> (se, k0) ;

(s2, 0 , k0 ) -> (s2, k0) }

 

 

Gefragt 11, Jan 2016 in 2015-B-02 von ugemt ugemt Eins-Komma-Null-Anwärter(in) (1,960 Punkte)  

2 Antworten

+3 Punkte

Hallo ugemt,

deine Lösung ist wegen des Lambda-Übergangs (s2, Lambda, k0) -> (se, k0) eine nichtdeteministische Lösung, da für das Kellerzeichen k0 und den Zustand s2 auch der Übergang (s2, 0, k0) -> (s2, k0) definiert ist. In dieser Aufgabe ist aber eine deterministische Lösung gefragt. In der Musterlösung ist nur zusätzlich noch eine nichtdeteministische Variante angegeben. Ansonsten ist deine Lösung in Ordnung, du schreibst ein a statt einer 0 in den Keller und verwendest einen zusätzlichen Zustand, das passt aber soweit.

Viele Grüße

Gregor (Tutor)

Beantwortet 11, Jan 2016 von uhdzw uhdzw Tutor(in) (102,490 Punkte)  
+1 Punkt

Noch ein weiterer Hinweis zu Alternativlösungen: Sie können auch den XWizard nutzen, um Ihre Lösungen zu überprüfen.

Das Skript zu Ihrer Lösung wäre:

pda:

(s0, 1, k) => (s1, ak);
(s0, 0, k) => (s1, ak);
(s0, U, k) => (s2, k);
(s1, 0, a) => (s1, aa);
(s1, 1, a) => (s1, aa);
(s1, U, a) => (s2, a);
(s2, 0, a) => (s2, a);
(s2, 1, a) => (s2, lambda);
(s2, lambda, k) => (se, k);
(s2, 0 , k) => (s2, k);
--declarations--
s0=s0;
F=se;
kSymb=k;
inputs=01U110
--declarations-end--
Sie können auch einfach über diesen Link darauf zugreifen:
 
 
Dort sehen Sie auch, wie sich die Berechnung bei dem Lambda-Übergang aufspaltet in zwei separate Pfade, also nichtdeterministisch wird.
 
(PS. Ich hab das &-Symbol durch U ersetzt, weil sonst die Darstellung nicht in Ordnung war.)
Beantwortet 11, Jan 2016 von Lukas König Dozent (10,065,100 Punkte)  
Alternativer Übergang
...