Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Formale Sprachen Übungsaufgabe
Hey Leute,
Könnt ihr mir vllt bei folgender Aufgabe weiterhelfen.
Sei Sigma = {a,b}, sei L die kleinste Menge, die das Wort a enthält und die für jedes w Element von L auch waa enthält.
a) Beweisen Sie: aaaaaaa Element von L
b) Beweisen Sie: L ist unendlich
c) Beweisen Sie: b nicht Element von L
Ich brauche unbedingt die Lösungen dazu und weiß nicht wie ich anfangen soll. Wäre toll wenn ihr mir helfen könntet.
Grüße, Tobi
als erstes würde ich mal versuchen das ganze als Grammatik hinzuschreiben
Und wenn du a) hast hast du auch b):
ersetze a = bb; aaaaaaa => bbbbbbbbbbbbbb
usw. => unendlich
alle Angaben ohne Gewähr, ich bin froh, dass ich’s bestanden hab 
Jetzt dacht ich schon BFS waere schon fertig korrigiert … aber dann will nur jemand Hilfe bei den Hausaufgaben … hat den die Vorlesungszeit ueberhaupt schon angefangen?
Naja … L = a(aa)* und der Rest sollte somit offensichtlich sein.