 Automaten Sprache ändern -> Neuer Automat |
666Malte
unregistriert
 |
|
| 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
|
|
07.11.2017 21:18 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo 666Malte.
hier ein paar Hinweise/Ansätze:
- Warum die Folgezustände der Startzustände? Außerdem:
![[latex]L^+=L^*\backslash\{\varepsilon\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L^+=L^*\backslash\{\varepsilon\})
- Die Formulierung lautet doch: es gibt ein Wort. Nicht die Sprache besteht aus ab mit Länge(a) = Länge(b). Deswegen würde ich es nicht kompliziert machen.
- Reicht es hier nicht einfach, die Startzustände zu Finalzuständen zu machen und die Richtung aller Kanten umzukehren? Das müsste man noch einmal genau durchdenken.
Besten Gruß,
Karlito
|
|
|
08.11.2017 15:55 |
|
|
|
