jaxxo hat geschrieben:Was bedeutet in Definition 6.4.18:
WHILE es existiert ein unmarkiertes Paar (q,q') es existiert ein a element Sigma (also ein Terminal), sodass (Übergangsfunktion(q, a), Übergangsfunktion(q',a)) markiert ist DO wähle ein solches Paar und markiere es.
Da stehe ich etwas auf dem schlauch. bedeutet die definition, dass wenn die einzelnen Elemente eines unmarkierten paares beide mit der selben transition auf ein markiertes paar führen, wird dieses paar auch markiert?
Richtig.
Die Idee hinter dem Markierungsalgorithmus ist: wenn es eine Zeichenkette
gibt, so dass man von q mit dieser Eingabe zu einem Endzustand kommt, aber von q' nicht (oder umgekehrt), dann muss (q,q') markiert werden.
Um das einfacher zu machen, markieren wir je nach Länge der Zeichenkette, also in der Reihenfolge n=0, n=1, ...
Für n=0 gibt es nur eine Zeichenkette: die leere. Von q kommt man mit der leeren Zeichenkette nur zu q, ebenso von q' nur zu q'. Wenn also q ein Endzustand ist, aber q' nicht, muss (q,q') markiert werden.
Dann versuchen wir es mit Zeichenketten der Länge n=1. Da gibt es für jedes
eine. Wenn es also ein a gibt, so dass man von q mit a zu einem Endzustand (z. B. r) kommt, aber von q' nicht (z. B. nur zu r'), muss man (q,q') markieren. Jetzt verwenden wir die alten Markierungen: wenn (r,r') schon markiert ist, wissen wir, dass nur einer der beiden ein Endzustand ist, und darum markieren wir auch (q,q').
Für Zeichenketten der Länge n=2 (z. B. ab) betrachten wir erst mal das erste Zeichen, also a. Wenn man mit a von q zu s kommt und von q' zu s', dann verwenden wir wieder die alten Markierungen: wenn (s,s') schon markiert ist, dann wissen wir, dass man mit irgendeiner Zeichenkette der Länge n-1=1 von s zu einem Endzustand kommt und von s' nicht (oder umgekehrt). Daraus folgt, dass man von q mit einer Zeichenkette der Länge 2 zu einem Endzustand kommt und von q' nicht (oder umgekehrt), und darum markieren wir (q,q').
Und so weiter. Hoffentlich hilft diese lange Erklärung...
aus der tabelle wird dann der minimalautomat zusammen gesetzt, in dem die unmarkierten paare zusammen gesetzt werden.
nun versteh ich aber die lösung von 8.1 nicht. denn dort ist 1,2; 1,4; 2,4 und 3,5 unmarkiert, der minimale automat in meiner lösung besteht aber nur aus 1,2; 3,5 und 4.
Welche Lösung haben Sie gefunden? Die Tabelle, die Sie nennen, ist die Tabelle, nachdem man den Fall n=0 abgeschlossen hat. Sie müssen noch n=1 behandeln. (Bei 8.1 reicht das auch schon: Bei n=2 kommen keine neuen Markierungen mehr hinzu.)
von jaxxo » 26.07.07 17:15 
