Kanns irgendwie angehen, daß ich am ende nen Automaten habe der nur einen Zustand hat der Anfangs und Endzustand ist und jedes leere Wort akzeptiert???

An Kopf schlag. Hab die Definition nicht verstanden, aber in etwa weiß ich jetzt wie ichs weitermachen muss. Nur weiß ich immer noch nicht ganz so viel mit K' Definition anzufangen.

Ich gehe mal davon aus, dass du das K' aus Theorem 3.25 meinst.

Die Definition beschreibt, wie die Kantenmenge des neuen
lambda-freien Automaten aussieht. B geht dann vom Zustand
z mit dem Wort [img]http://mokrates.de/cgi-bin/texstring?w%5Cin%5CSigma%5E%2B[/img] in z''' über, wenn im
Automaten A gilt

[img]http://mokrates.de/cgi-bin/texstring?z%5Clongrightarrow%5E*_%5Clambda%20z'%5Clongrightarrow%5E*_w%20z''%5Clongrightarrow%5E*_%5Clambda%20z'''[/img]

für irgendwelche Zustände z' und z''.

Das heißt u.a., dass man alle Kanten, außer den
lambda-Kanten, aus A wieder in B einfügt (beachte,
dass z=z' und z''=z''' erlaubt ist!). Entscheidend
ist aber hier: In B gibt es nach der Definition zwischen
zwei Zuständen z und z''' auch dann eine direkte Kante,
wenn man in A von z nur zu z''' kam, indem man
lambda-Kanten benutzt hat. Die Definition "tut" also
folgendes: sie nimmt alle lambda-Kanten weg und fügt
dafür die Übergänge explizit hinzu, die vorher nur
implizit über lambda-Kanten bestanden haben.


PS: Kann es sein, dass in der Latex-Umgebung die Befehle
\overset und \underset nicht funktionieren? Ich musste
deshalb den Notbehelf mit Sub- und Superskript an den
Pfeilen nehmen.

Wie konstruiere ich mir die neue Kanten Menge K' denn am einfachsten??
Ich denke ich habe verstanden wie es definiert ist.
Es muss doch eine Methode geben damit man nichts vergisst.
Tabelle?? Algorithmus?? Oder sonst was??

Gruß
Gosi

*EDIT*

Bei Aufgabe 4.1(ii)
wieviele neue Tripel hat K'???
ich habe 12. Man braucht meiner Meinung nach nicht alle, aber wir sollen uns ja streng an das Verfahren halten.
Kann das stimmen???

Reicht es bei den Teilaufgaben aus 4.1 wohl aus, wenn man das Zustandsübergangsdiagramm des jeweiligen Automaten zeichnet? Oder sollte man noch explizit eine Liste der Kanten oder ähnliches angeben?

Wie konstruiere ich mir die neue Kanten Menge K' denn am einfachsten??
Ich denke ich habe verstanden wie es definiert ist.
Es muss doch eine Methode geben damit man nichts vergisst.
Tabelle?? Algorithmus?? Oder sonst was??

Man kann K' so konstruieren:
Du möchtest ja eine Liste aller Tripel (z,w,z''') haben,
die die Bedingung in der Definition erfüllen. Theoretisch
könnte man also versuchen, alle Tripel aus
[img]http://mokrates.de/cgi-bin/texstring?Z%5Ctimes%20%5CSigma%5E*%5Ctimes%20Z[/img] auf die
Bedingung zu überprüfen. Das sind aber unendlich viele,
also lassen wir das. Wir wissen aber, dass es für
jedes der gesuchten Tripel (z,w,z''') eine Kante
(z',w,z'') mit den angegebenen Eigenschaften gibt.
Wir können daher alle gesuchten Tripel (z,w,z''')
finden, indem wir nacheinander die Kanten (z',w,z'')
ansehen und dazu dann alle möglichen z und z'''
suchen. Für z sind das alle Zustände,
von denen aus man über (evtl. mehrere!) lambda-Kanten
zu z' kommt sowie der Zustand z' selbst.
Und entsprechend: Für z''' sind das alle Zustände,
zu denen man über (evtl. mehrere!) lambda-Kanten von
z'' aus kommt sowie der Zustand z'' selbst.

Das kann man sich auch als Tabelle aufschreiben:
Diese besteht aus |K| Blöcken, für jede Kante aus
K ein Block. Zu je einem Block gehört eine bestimmte
Kante (z',w,z'') und er besteht aus drei Spalten, in
die linke Spalte schreibt man alle für diese Kante
möglichen z. Und in die rechte Spalte schreibt man
alle für diese Kante möglichen z'''. Aus jedem Block
entsteht dann eine Kantenmenge: für jedes z links,
jedes z''' rechts und das w von der Kante (z',w,z'')
erhält man die Kante (z,w,z''').

War das verständlich? [img]http://www.fb18.de/gfx/28.gif[/img]