Theoretische Info - Sprachen, DFA/NFA [Archiv]

Archiv verlassen und diese Seite im Standarddesign anzeigen : Theoretische Info - Sprachen, DFA/NFA

HeavensRevenge

14.05.2003, 19:12

Ich habe ein paar Probleme bei der Bearbeitung folgender Aufgabe:

Für eine Sprache L 'echte Teilmenge von' Σ*
werden die Sprachen MAX(L) und CYCLE(L) definiert.

MAX(L)
:= {u e Σ* | 'existiert kein' v e Σ+, uv e L}

CYCLE(L)
:= {vu e Σ* | uv e L}

Zeigen Sie:
Falls L e C(Σ, DFA), so gilt auch

a) MAX(L) e C(Σ, DFA)
b) CYCLE(L) e C(Σ, DFA) = C(Σ, NFA)

Das C steht hierbei für ein "Schnörkel-L", das e steht für 'ist enthalten in' bzw 'ist Element von'. Sonderzeichen, für die ich keinen Ersatz fand, habe ich benannt...

Nun meine Fragen...

1.: CYCLE kann ich, denke ich nachvollziehen, was das heißt... Die gebildeten Worte werden durch den Automaten einfach umgedreht, bzw revertiert. Aber was bedeutet die Angabe in MAX? Wenn kein v in Σ+ existiert, das konkateniert mit einem u ein Wort der Sprache L ergibt, dann kann es doch höchstens das ε, also das leere Wort sein, oder?

2.: Wie soll ich die Beweise von a) und b) angehen? Ich habe irgendwie keine Idee, wie ich da anfangen soll...

...Wäre echt super, wenn mir da jemand weiterhelfen könnte!

Danke im Voraus!

<img src="http://home.t-online.de/home/Heavens.Revenge/bilder/other/heav.gif">

Lim_Dul

15.05.2003, 01:24

Schöne Aufgaben, muss ich sagen :)
MAX(L) sind die Wörter maximaler Länge aus L, wenn du an ein Wort aus MAX(L) ein einziges zeichen (oder mehr) dranhängst, ist es nicht mehr in L drin.

Der Beweis zu MAX(L) ist recht einfach, gegeben sei ein DFA M der L akzeptiert, mit der Menge der Endzustände F, die sollen mal die Zustände F1 bis Fn enthalten.

Nun wird ein DFA M' konstruiert, der bis auf die Endzustände alles gleich hat.
Die Endzustände F' von M' sind genau die Endzustände, von den man keinen andern Endzustand (und auch nicht dennselben) erreichen kann.

Zu CYCLE ist der Beweis etwas schwieriger, denn bekomme ich jetzt so auf die schnelle nicht hin, da müsst ich mal was basteln und der müsste etwas aufwendiger sein.

HeavensRevenge

15.05.2003, 12:44

Originalnachricht erstellt von Lim_Dul
Schöne Aufgaben, muss ich sagen :)
MAX(L) sind die Wörter maximaler Länge aus L, wenn du an ein Wort aus MAX(L) ein einziges zeichen (oder mehr) dranhängst, ist es nicht mehr in L drin.
OK, das ist soweit verstanden!

Der Beweis zu MAX(L) ist recht einfach, gegeben sei ein DFA M der L akzeptiert, mit der Menge der Endzustände F, die sollen mal die Zustände F1 bis Fn enthalten.

Nun wird ein DFA M' konstruiert, der bis auf die Endzustände alles gleich hat.
Die Endzustände F' von M' sind genau die Endzustände, von den man keinen andern Endzustand (und auch nicht dennselben) erreichen kann.
Heißt das, ich muss den Beweis per "Bildchen" machen und irgendwie "erklären", dass M und M' die gleichen Worte erkennen?

Zu CYCLE ist der Beweis etwas schwieriger, denn bekomme ich jetzt so auf die schnelle nicht hin, da müsst ich mal was basteln und der müsste etwas aufwendiger sein.
Wäre super, wenn Du was finden würdest, irgendeinen Ansatz ... Ich habe noch immer ziemliche Probleme mit dieser formalen Beweiserei, hoffe das gibt sich irgendwann noch...

<img src="http://home.t-online.de/home/Heavens.Revenge/bilder/other/heav.gif">