Automaten Sprache ändern -> Neuer Automat |
07.11.2017, 21:18 | Auf diesen Beitrag antworten » |
666Malte | Automaten Sprache ändern -> Neuer Automat Hallöle, ich habe in der Uni eine Zusatzübungsaufgabe erhalten, die nicht bewertet wird, die ich aber gerne zu meiner Zufriedenheit lösen möchte. 5 von 8 Teilaufgaben habe ich gelöst, aber drei fehlen noch. Also es geht um folgendes: Ihr habt einen DFA oder NFA, der die Sprache L akzeptiert, die Teilmenge aus Sigma * ist. Nun sollen wir sagen, wie man den Automaten ändern sollen, damit er die veränderte Sprache akzeptiert. a) L+ b) alle a aus Sigma Stern für die gilt, dass es ein b gibt mit ab aus L und Länge(a) = Länge(b) c) wheel(L) = xy aus Sigma Stern für yx aus L (also vertauscht) Meine Ansätze sind die folgenden: Ein L+ muss Pfeile haben, die von den akzeptierten Zuständen in die Zustände geht, die die Folgezustände der Startzustände sind. Wenn er also beispielsweise ein d einliest, muss er in den Zustand zu dem man kommt wenn man von einem Startzustand aus d einliest. Oder beschreibt das L* und nicht L+? b) er mus auf jeden Fall alle Worte ungerader Ursprungslänge herauslassen. Vielleicht muss man auch den gesamten Automaten so stark erweitern, dass jeder Zustandspfeil auch einen internen "Zähler"Zustand anvisiert, der die Länge zählt. Aber das ist viel zu größenwahnsinnig und unlogisch. c) Man muss offensichtlich wahllos Worte in der Mitte brechen können und dann vertauschen. Hat jemand Ideen? Wäre sehr froh, wenn jemand coole Ansätze hätte! Danke |
|
|
08.11.2017, 15:55 | Auf diesen Beitrag antworten » |
Karlito | Hallo 666Malte. hier ein paar Hinweise/Ansätze:
Besten Gruß, Karlito |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|