Lutz Oberst wrote:
habt ihr ne Idee wie man die 1 vernünfig löst? Die 1b konnte ich nur lösen, da 1b selbst schon eine kfS ist, und sich so leicht das Komplement bilden lässt. Bei allen Anderen habe ich keine Idee wie man da mit einer kfS das Komplement beschreiben soll. Gibt es da irgendwelche Tricks die ich irgenwie kennen sollte?
ich habe auch erfolglos nach irgendwelchen Tricks gesucht. Warum die Aufgabe nur 4 Punkte bringt ist mir daher nicht ganz klar, denn ohne Tricks sind die Automaten IMHO sehr aufwendig und schwierig.
Meine Loesung der d): zuerst wird nach der Laenge des Wortes unterschieden. Wenn |w|=2n+1 gilt, dann ist w auf jeden Fall in der Sprache. Bei |w|=2n ist etwas schwieriger. Aus w = w_1w_2...w_nw_(n+1)...w_(2n) folgt das es ein i geben muss (1<=i<=n) so dass w_i != w_(i+n) gilt. Dieses muss der Automat (mit Hilfe von viel nicht-Determinismus) suchen.
HTH, -Thorsten
