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

Wann schreibe ich bei nichtleeren Wörtern ein "+" in die Sprachdefinition und wann ein "*"?

+1 Punkt
55 Aufrufe

In Kapitel 4 Aufgabe 29 wird in Teilaufgabe b) nach der Sprache gefragt, die der Automat akzeptiert.

Die Lösung lautet: L(A) = {w element {0,1}* | |w| > 0 und |w|0 mod 2 = 0 } 
Der Automat akzeptiert nur nichtleere Wörter. Müsste ich dann in der Definition nicht ein "+" im Exponenten schreiben anstatt einem " * ", um dies zu verdeutlichen und es nicht erst extra im zweiten Teil der Definition hinter dem trennenden „|“ aufführen als "|w| > 0“ ?
 
In Kapitel 2 Aufgabe 9 wird die Sprache L(A1) so angegeben:
L(A1)= {w element {a,b,c}+ | mindestens ein v element {a,b,c}* : w = vabc}
Hier ist das + vorne, auch hier ist ein akzeptiertes Wort auf jeden Fall nichtleer, denn nur so kommt man in den Endzustand. Wieso ist es hier anders als oben?
Gefragt 28, Dez 2015 in SPR-AA von utdtz utdtz Eins-Komma-Null-Anwärter(in) (3,110 Punkte)  

Eine Antwort

+2 Punkte
Hey,

bei beiden Sprachen hast du richtig erkannt, dass durch die Form der Bedingungen das leere Wort nicht in den Sprachen enthalten ist. Ob du nun vorne bei der Definition der Zeichenmenge ein + oder * in den Exponenten schreibst, spielt für die Sprache somit keine Rolle: Das leere Wort ist durch die Bedingung in beiden Fällen nicht in der Sprache und soll das auch nicht. Du würdest in beiden Fällen die selbe Sprache definieren.

Bei der Sprache in Kapitel 4 Aufgabe 29 muss also nicht ein + im Exponenten stehen, kann es aber.

Mein persönlicher Ratschlag: Wenn die, zu beschreibende Sprache das leere Wort nicht enthalten soll, das + in den Exponenten schreiben. Damit läuft man nicht in Gefahr, dass "ausversehen" doch das leere Wort in der Sprache enthalten ist, falls man beim Aufstellen der Bedingung das leere Wort nicht ausschließt.

Viele Grüße
Ashvin (Tutor)
Beantwortet 29, Dez 2015 von uxdiu uxdiu Tutor(in) (101,710 Punkte)  
...