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!
 

 

$\lambda \in L \Leftrightarrow s_0 \in F$?

+3 Punkte
33 Aufrufe
Hallo,
 
ich bin etwas verwirrt, aufgrund von Aufgabe 3 b) des 1 Tuts.
 
Das leere Wort liegt hier ja laut Definition in der Sprache, wenn man sich den Automaten anschaut sieht man aber doch, dass man nach Eingabe von 'nichts' noch in $s_0$ ist und somit nicht im Endzustand.
 
Ist doch sowieso etwas widersprüchlich, dass mindestens eine Eins in jedem Wort der Sprache sein muss, die Länge jedes Wortes also mindestens $1$ beträgt aber das leere Wort auch dazugehört. Oder habe ich das Konzept hinter $\lambda$ noch nicht durchschaut?
 
Danke im Voraus!
Gefragt 16, Nov 2015 in AU-1-2 von uxdui Tutor(in) (103,050 Punkte)  
Bearbeitet 17, Nov 2015 von Lukas König
Sie haben diese Frage in der falschen Kategorie gepostet. Ich werde versuchen sie in die richtige, nämlich Übungsblatt 1 => AU-1-2 zu verschieben. Bitte achten Sie in Zukunft auf die richtige Kategorie. Am besten klicken Sie einfach unter der Aufgabe auf die ID (AU-1-2).

Eine Antwort

0 Punkte
 
Beste Antwort

Wie kommen Sie darauf, dass das leere Wort Teil der Sprache sein soll? Da steht

$$|w|_1 > 0$$

was soviel bedeutet, wie dass die Anzahl der Einsen im Wort größer als 0 sein muss. Dadurch kann das Wort ja nicht leer sein.

(Ich sehe gar nicht, wo Sie ein $\lambda$ in der Aufgabenstellung entdeckt haben.)

Rein prinzipiell haben Sie aber recht: Bei endlichen Automaten gilt, dass das leere Wort genau dann Teil der Sprache des EA ist, wenn der Startzustand gleichzeitig ein Endzustand ist.

Beantwortet 17, Nov 2015 von Lukas König Dozent (10,065,090 Punkte)  
ausgewählt 17, Nov 2015 von uxdui
Ich dachte durch * und + in der Menge wird definiert, ob die leere Menge Teil der Sprache ist oder nicht?
Das stimmt auch, $\{0, 1\}^\star$ enthält das leere Wort. Aber man muss ja die gesamte Mengendefinition anschauen, und weiter hinten wird das leere Wort eben doch wieder ausgeschlossen. Die o.a. Menge enthält auch die Wörter $0, 00, 000, \ldots$, und diese sind in der Gesamtmenge ja auch nicht enthalten.
Aber das ist trotzdem eine gute Frage, die bestimmt anderen auch beim Verständnis helfen wird! Ich habe gerade einen "Upvote" vergeben.
Ah stimmt, Danke.
So weit hatte ich noch nicht gedacht^^
Um Ihren Kommilitonen bei der Übersicht zu helfen, können Sie übrigens (1) gute Antworten "upvoten" und/oder (2) auf den Stern klicken, wenn Ihre Frage beantwortet worden ist.
...