Ja, hallo zusammen.
Ich begrüße Sie zur Vorlesung Theoretische Grundlagen der Informatik.
Was machen wir heute?
Wir werden heute das Kapitel Endliche Automaten, reguläre Sprachen
abschließen und wenn es läuft wie geplant mit einem neuen Kapitel
Turing -Maschinen und Berechenbarkeit starten.
Aber erst nochmal, was bleibt uns denn noch zu tun im Zusammenhang mit
endlichen Automaten und regulären Sprachen?
Das hier.
Mein Pointer scheint nicht mehr allzu stark zu sein.
Was uns zu tun bleibt, ist zu beweisen, dass der
Äquivalenzklassenautomat tatsächlich bezüglich der Anzahl der Zustände
minimal ist.
Um der Frage nachzugehen vielleicht nochmal kurz zur Wiederholung Was
ist der Äquivalenzklassenautomat?
Wir haben anhand von einem Beispiel eines endlichen Automaten
deterministischen endlichen Automaten mit 16 Zuständen uns überlegt,
dass wohl manchmal endliche Automaten in dem Sinne zu viele Zustände
haben, als dass Zustände, die im Prinzip sich gleich verhalten, in
Bezug auf die Frage, ob ein Wort von dem Zustand aus akzeptiert wird
oder nicht zu viele sind dass man die ja vielleicht auch
zusammenfassen kann Das war ein Automat mit 16 Zuständen zu dem wir
ein Äquivalenzklassenautomat mit 4 Zuständen uns überlegt haben oder
angesehen haben Zustände zusammenfassen das beruht sozusagen auf der
Definition wann zwei Zustände äquivalent sind und informell gesprochen
sind zwei Zustände äquivalent wenn sie dasselbe Akzeptanzverhalten
haben Das heißt also, wenn von beiden Zuständen für die Frage, ob ein
Wort, das von da aus weiter abgearbeitet wird, unerheblich ist, ob das
akzeptiert wird, ob ein Wort, das von da aus weiter abgearbeitet wird,
auch akzeptiert wird, unerheblich ist, ob man von dem einen oder von
dem anderen losgeht oder abarbeitet.
Das ist die Definition hier, auf die ich irgendwie nicht so richtig
zeigen kann, weil der Pointer nicht stark genug ist.
Zwei Zustände P und Q eines deterministischen endlichen Automaten
heißen Äquivalent, denn für alle Wörter über dem Eingabe-
gilt Delta P, Wort ist in F, genau dann, wenn Delta Q, Wort in F ist.
Also P und Q sind Äquivalent, wenn für alle Wörter gilt, die Wörter
führen entweder von beiden Zuständen aus in einen Endzustand oder von
beiden Zuständen aus in einen Nicht-Endzustand.
Dass diese Relation, die wir so definiert haben, tatsächlich eine
Äquivalenzrelation ist, ist ganz offensichtlich und
Äquivalenzrelationen zerlegen die Grundmenge sozusagen in
Äquivalenzklassen, also Zustände, die Äquivalent sind, die kann man in
eine Klasse packen und dann hat man sogenannte Äquivalenzklassen und
der Äquivalenzklassenautomat ist dann so definiert, wie es hier steht,
dass eben einfach äquivalente Zustände in Klassen gepackt werden und
nur noch die Klassen als Zustände betrachtet werden.
Das heißt also, der Äquivalenzklassenautomat zu einem
deterministischen endlichen Automat ist darüber definiert, dass wir
als Zustandsmenge des Äquivalenzklassenautomats die Äquivalenzklassen
betrachten.
Und alles weitere ist im Prinzip dann kanonisch, also dass man dann
als Äquivalenz oder als Anfangszustand die Äquivalenzklasse des
Anfangszustands des Ausgangsautomaten nimmt, als Endzustände die
Äquivalenzklassen der Endzustände des Ausgangsautomaten nimmt, also
das ist irgendwie kanonisch und auch die Übergangsfunktion, wenn man
genauer draufschaut, ist auf kanonische Weise definiert.
Also man sagt, na gut, also die Übergangsfunktion, die muss ja jetzt
als Zustand eine Äquivalenzklasse haben und dann sagen, was passiert,
wenn man von dem Zustand aus ein Symbol A liest und definiert ist als
Folgezustand gerade die Äquivalenzklasse von dem Zustand, in dem A von
Q im Ausgangsautomat ausführt.
So, wir haben dann gezeigt, dass das wohl definiert ist, dass also bei
der Definition nichts Ungehöriges passiert.
So, und dann fragt sich natürlich, wie man zu einem gegebenen
deterministischen Endlichen Automaten diesen Äquivalenzklassenautomat
findet.
Und dazu haben wir uns ein Verfahren überlegt und
die Vorgehensweise war einfach die, wir betrachten alle Zustandspaare
und testen systematisch, ob die entsprechenden beiden Zustände
äquivalent sind oder vielleicht eher nicht.
Also wir gehen im Prinzip von so einer Art Hypothese aus, alle
Zustände sind äquivalent und versuchen dann systematisch
herauszufinden, für welche Paare das doch nicht der Fall ist.
Und das machen wir, indem wir eben die Wörter der Länge nach
durchgehen und für Zustandspaare dann schauen, ist ein bestimmtes Wort
einer bestimmten Länge gerade ein Zeuge dafür, dass die beiden
Zustände nicht äquivalent sind.
Wir haben uns überlegt, dass man über diese Zeugenidee tatsächlich
auch irgendwann mal abbrechen kann, also die Vorgehensweise abbrechen
kann.
Nämlich, dass man, wenn man für irgendeine Länge, Wortlänge, keinen
Zeugen für eine bisher noch nicht entdeckte Nicht-Äquivalenz zweier
Zustände findet, dann braucht man auch keine längeren Wörter mehr
betrachten, dann kann da auch nichts Neues mehr zum Vorschein kommen.
Das heißt also, betrachte alle Zustandspaare, zunächst Epsilon, dann
Elemente aus Sigma, dann alle Wörter der Länge zwei und so weiter und
dann teste nach, führen die Worte von zwei Zuständen aus zu
verschiedenem Akzeptanzverhalten.
Also gibt es da irgendein Wort darunter, das für ein Zustandspaar, von
dem wir noch nicht wissen, ob es äquivalent ist oder nicht, das Wort
von dem einen Zustand aus in einen Endzustand führt und von dem
anderen nicht.
Dann wäre das Wort Zeuge dafür, dass die zwei nicht äquivalent sind.
Also das ist ein Verfahren, das kann man systematisch anwenden, das
haben wir am Beispiel auch gemacht.
Aber warum haben wir denn die ganze Aktion Definition von Äquivalenz
von Zuständen, Definition des Äquivalenzklassenautomats angeleiert?
Wir haben das angeleiert, weil wir zu einem beliebigen
deterministischen endlichen Automaten einen äquivalenten
deterministischen endlichen Automaten konstruieren wollen, der eine
minimale Anzahl von Zuständen hat.
Und wir sagen können, es gibt keinen anderen deterministischen
endlichen Automaten, der genau dasselbe macht, dieselbe Sprache
akzeptiert, aber noch weniger Zustände.
Und unsere Vermutung ist, ein solcher Automat ist der
Äquivalenzklassenautomat.
Also ein deterministischer endlichen Automat, die zugehörige Sprache,
dazu bilden wir den Äquivalenzklassenautomat und wir werden jetzt
zeigen, dieser Äquivalenzklassenautomat hat dann tatsächlich minimale
Zustandsmenge unter allen deterministischen endlichen Automaten, die
äquivalent sind zu dem Ausgangsautomat oder in anderen Worten, die
dieselbe Sprache akzeptieren, wie dieser Ausgangsautomat.
Also die Frage ist der Äquivalenzklassenautomat zu einem
deterministischen endlichen Automaten, schon der äquivalente Automat
mit der minimalen Anzahl von Zuständen.
Der Beweis ist jetzt ein kleines bisschen indirekt und auch relativ
formal.
Also die Antwort ist ja und was wir machen ist, wir konstruieren einen
minimalen Automaten zu einer vorgegebenen regulären Sprache.
Dieser Automat heißt der Automat der Nerode-Relation.
Wir werden nämlich erst auf der Sprache oder zu der Sprache eine
Äquivalenzrelation auf den Wörtern definieren und mit Hilfe dieser
Äquivalenzrelation dann einen Automaten, Automat der Nerode-Relation.
Und dann zeigen wir anschließend, wir zeigen, dass dieser Automat
minimale Anzahl von Zuständen hat, unter allen Automaten,
deterministischen endlichen Automaten, die die vorgegebene Sprache
akzeptieren.
Und dann zeigen wir, unser Äquivalenzklassenautomat hat auch nicht
mehr Zustände als der Automat der Nerode-Relation.
Der Äquivalenzklassenautomat zu einem beliebigen Automaten,
deterministischen endlichen Automaten, der die vorgegebene Sprache
akzeptiert.
Also Äquivalenzklassenautomat bauen wir ja immer zu einem
deterministischen endlichen Automaten, aber da ist ja immer eine
Sprache sozusagen gleichwertig.
Das heißt also hier bei dem Beweis gucken wir stärker auf die Sprache,
die zu einem deterministischen endlichen Automaten gehört, für den wir
eben den Äquivalenzklassenautomat betrachten.
Äquivalenzklassenautomat, die Definition basiert auf Äquivalenzklassen
von Zuständen.
Äquivalente Zustände werden in Klassen gepackt.
Die Nerode-Relation, die gehört zu einer Sprache und ist eine
Relation, eine Äquivalenzrelation auf den Wörtern, allen Wörtern über
dem Eingabealphabet oder Grundalphabet der Sprache.
So, jetzt haben wir da also äquivalente Zustände und da äquivalente
Worte.
Die Frage ist, haben die irgendwas miteinander zu tun.
Im Prinzip ist genau dieselbe Idee dahinter.
Wenn Sie zwei Zustände betrachten, die äquivalent sind, dann heißt das
ja, egal welches Wort Sie von da aus weiter abarbeiten, in beiden
Fällen kommen Sie zum Endzustand oder zum Nicht-Endzustand.
Also in beiden Fällen wird entweder akzeptiert oder nicht akzeptiert.
Wenn Sie jetzt mal das vom Wortkonzept aus sehen, dann können Sie
sagen, naja gut, zwei Worte sind äquivalent, wenn, egal was ich da
dran hänge, in beiden Fällen ein Wort rauskommt aus der Sprache, der
zugrunde liegenden Sprache, oder eben in beiden Fällen nicht ein Wort
aus der zugrunde liegenden Sprache rauskommt.
Und wenn Sie sich sozusagen diese Worte angucken, was die bei der
Abarbeitung des zugehörigen Automaten machen, dann würden so zwei
Worte, die als äquivalent definiert werden, ja genau in äquivalente
Zustände führen.
Das heißt also, das was wir jetzt definieren werden als Relation auf
Wörtern, die eine Äquivalenzrelation ist, diese Nerurde-Relation, das
ist eigentlich dasselbe Konzept wie die Definition von äquivalenten
Zuständen.
Halten Sie das einfach mal im Hinterkopf.
Also, wir brauchen dafür jetzt noch sozusagen einen anderen Begriff,
nämlich Rechtsinvarianz.
Ich habe gesagt, wir werden zwei Wörter als äquivalent definieren,
wenn, egal was man da hinten ranhängt, in beiden Fällen entweder ein
Wort, der zugrunde liegend in der Sprache rauskommt oder in beiden
Fällen nicht.
Hinten ranhängen heißt sozusagen rechts was dranhängen.
Und deshalb macht jetzt die Definition von Rechtsinvarianz einer
Relation Sinn.
Wir betrachten jetzt mal eine beliebige Äquivalenzrelation auf Sigma
-Stern, die also Wörter aus Sigma-Stern in Äquivalenzklassen einteilt.
Und wir sagen, so eine Relation heißt Rechtsinvariant, wenn gilt für
alle xy aus Sigma-Stern, falls x in Relation zu y ist, so gilt auch
für alle z aus Sigma-Stern, dass xz in Relation zu yz ist.
Also in Relation zu sein ist invariant bezüglich was rechts anhängen.
x und y sind in Relation, sind äquivalent und folgt auch, wenn ich da
irgendwas ranhänge rechts an x und an y, kommen wieder Worte raus, die
äquivalent sind.
Und jetzt noch ein Begriff, Index.
Also so eine Äquivalenzrelation zerlegt ja eine Menge in
Äquivalenzklassen.
Wir werden jetzt eine ganze Weile lang Äquivalenzrelationen auf Sigma
-Stern betrachten.
Sigma-Stern ist unendlich.
Eine Äquivalenzrelation auf Sigma-Stern betrachten, dann könnte also
auch passieren, dass die Anzahl der Äquivalenzklassen, in die Sigma
-Stern zerfällt, unendlich ist.
Oder wird halt endlich.
Und wir nennen eben die Anzahl der Äquivalenzklassen, in die
Äquivalenzrelation so eine Grundmenge zerlegt, den Index der Relation.
Und die Tatsache, dass bei der Äquivalenzrelation, die wir jetzt
definieren, der Index endlich sein wird, der spielt eine ganz große
Rolle.
Wir werden nämlich zu dieser Äquivalenzrelation dann einen Automaten
definieren.
Die Äquivalenzklassen der Wörter zu den Zuständen des Automaten
machen.
Und dass diese Äquivalenzrelation endlich einen Index haben wird, hat
dann den Effekt, dass die Anzahl der Zustände des Automaten, den wir
dazu definieren, endlich ist.
Dass wir uns also da bei endlichen Automaten befinden.
Also das ist die Bedeutung, warum wir hier den Index, warum uns das
überhaupt interessiert.
Der Index einer Äquivalenzrelation beziehungsweise die Anzahl der
Äquivalenzklassen, in die eine Äquivalenzrelation über Sigma-Stern,
Sigma -Stern zerlegt.
Rechtsinvariant, in Relation zu sein, ist invariant gegenüber, was
rechts anhängen.
Und jetzt definieren wir also diese Nerode-Relation, die gehört zu
einer Sprache.
Nerode-Relation zu einer Sprache.
Und zwar, für eine Sprache L aus Sigma-Stern ist die Nerode-Relation
RL definiert als, für XY aus Sigma-Stern ist X in Relation zu Y genau
dann, wenn für alle Z aus Sigma-Stern XZ in L ist, genau dann, wenn YZ
in L ist.
Das heißt also, zwei Wörter nennen wir bezüglich dieser Relation
äquivalent, wenn bezüglich was rechts anhängen, in beiden Fällen
entweder ein Wort aus L rauskommt oder in beiden Fällen ein Wort
rauskommt, das nicht in L ist.
Das ist dieser Bezug zur Äquivalenz von Zuständen, den ich eben schon
angekündigt habe.
Also bezüglich, hier kann man nicht von Akzeptanzverhalten reden, aber
von, wie Wörter dazu stehen, dass was aus der Sprache rauskommt oder
nicht, wenn man rechts was dranhängt.
So ähnlich wie Äquivalenz von Automaten in Bezug auf Zustände in Bezug
auf Akzeptanzverhalten.
Also nochmal, wir starten mit einer Sprache aus Sigma-Stern.
Zu dieser Sprache definieren wir eine Relation auf der Grundgesamtheit
der Wörter über Sigma und wir sagen, zwei Wörter aus Sigma-Stern sind
in Relation genau dann, wenn in beiden Fällen, bei beiden Wörtern
gilt, egal was wir rechts ranhängen, es kommt entweder ein Wort aus L
raus in beiden Fällen oder es kommt in beiden Fällen kein Wort aus L
raus.
Also hier spielt die Sprache L, mit der wir starten, eben die
entscheidende Rolle.
Das ist ganz offensichtlich eine Äquivalenzrelation.
Also ein Wort ist zu sich selbst in Relation, wenn zwei Wörter
zueinander in Relation sind, entsprechend dieser Definition kann man
das auch umdrehen und diese Relation ist transitiv.
Also dass das eine Äquivalenzrelation ist, steht jetzt erst gar nicht
ausführlich bewiesen auf der Folie, weil es offensichtlich ist.
Aber die ist außerdem rechts invariant und das machen wir uns gerade
klar.
Also die Nerode-Relation RL zu einer Sprache L aus Sigma-Stern ist
rechts invariant, denn da starten wir einfach mal mit zwei Wörtern, X
und Y, die in Relation sind bezüglich RL.
Dann folgt er nach Definition von RL für alle W aus Sigma-Stern gilt
XW ist aus L, genau dann, wenn YW aus L ist.
Dann kann man auch sagen, naja, für alle W und Z aus Sigma-Stern gilt
dann dasselbe, nämlich XZW ist aus L, genau dann, wenn YZW aus L ist.
Und wenn dem so ist, dann heißt das also, für alle Z ist XZ in
Relation zu YZ.
Die Definition dafür ist ja gerade das, dass egal was sich an XZ und
YZ rechts ranhänge, in beiden Fällen was aus L rauskommt oder eben
nicht.
Das heißt, es ist offensichtlich, dass diese Nerode-Relation eine
rechts invariante Äquivalenzrelation ist.
Und jetzt kommt der entscheidende Satz, den man noch nicht unmittelbar
ansieht, dass er für unsere Zwecke dienlich ist.
Unsere Zwecke sind ja zu zeigen, dass der Äquivalenzklassenautomat
eine minimale Anzahl von Zuständen hat.
Und dieser Satz hier, der sagt einfach, folgende drei Aussagen sind
äquivalent.
Und die Aussagen sind erstens, ich habe eine Sprache L, die von einem
deterministischen endlichen Automaten akzeptiert wird.
Also meine Sprache ist regulär.
Die erste Aussage.
Die zweite Aussage ist, diese Sprache ist Vereinigung von
Äquivalenzklassen, einer Äquivalenzrelation auf Sigma-Stern mit
endlichem Index.
Also diese Sprache ist die Vereinigung von Äquivalenzklassen, einer
Äquivalenzrelation auf Sigma-Stern, die Sigma-Stern in eine endliche
Menge von Klassen verlegt.
Und die dritte Aussage ist, diese neurode Relation, die wir gerade
eben definiert haben, zu der Sprache L, hat endlichen Index.
Also bei der ist es auch so, dass sie Sigma-Stern in eine endliche
Anzahl von Äquivalenzklassen zerlegt.
Also die drei sind äquivalent, das zeigen wir jetzt.
Das ist jetzt so ein bisschen formal.
Aber das Konzept als Ganzes, das wird hier in dem Beweis zum Vorschein
kommen, ist eigentlich sehr elegant.
Wenn man die Äquivalenz von so drei Aussagen zeigt, dann zeigt man,
aus der einen folgt die zweite, aus der zweiten Aussage folgt die
dritte und aus der dritten Aussage folgt wieder die erste.
So machen wir es hier auch.
Und was dabei passieren wird, insbesondere ist, dass bei dem Beweis
aus drei folgt eins, ein Automat konstruiert wird.
Wir müssen zeigen, wenn die neurode Relation zu einer vorgegebenen
Sprache endlichen Index hat, dann wird die Sprache von einem
deterministischen endlichen Automaten akzeptiert.
Und das zeigen wir, indem wir diesen Automaten konstruieren zu der
neurode Relation.
Und da machen wir das, was sich jetzt schon andeutet, dass wir die
Äquivalenzklassen dieser neurode Relation zu den Zuständen des
Automaten machen.
Und von diesem Automaten, den wir im Zuge dieses Beweises
konstruieren, bei den Automaten können wir dann sehr schnell beweisen,
dass er eine minimale Anzahl von Zuständen hat, unter allen Automaten,
die diese Sprache L, von der hier immer die Rede ist, akzeptieren.
Und dann zeigen wir noch danach, so, und der Äquivalenzklassenautomat,
der hat auch nicht mehr Zustände und dann sind wir fertig.
Aber jetzt müssen wir erstmal durch diesen Beweis durch, aus eins
folgt zwei, aus zwei folgt drei, aus drei folgt eins.
Also aus eins folgt zwei.
Also wir gehen davon aus, dass wir eine Sprache haben, die von einem
deterministischen endlichen Automaten akzeptiert wird und wir zeigen,
diese Sprache ist Vereinigung von Äquivalenzklassen einer
rechtsinvarianten Äquivalenzrelation mit endlichem Index.
Hier steht so in Klammern von einigen, also unser Sigma-Stern wird
durch diese Äquivalenzrelation in Äquivalenzklassen aufgeteilt und
bestimmte von diesen Äquivalenzklassen bilden zusammen, deren
Vereinigung zusammen bildet sozusagen L.
Das müssen wir zeigen.
Also wir starten mit einer Sprache, zu der wir einen deterministischen
endlichen Automaten haben, freuen wir den mal gleich hin.
Der hieße also A, also der deterministische endliche Automat, der L
akzeptiert.
Und jetzt definieren wir zu diesem Automaten eine Relation auf der
Menge aller Wörter aus Sigma-Stern.
Nämlich wir sagen, Wörter x und y aus Sigma-Stern sind bezüglich Ra
äquivalent, genau dann, wenn sie beide von S aus in denselben Zustand
führen.
Also wir könnten ja zu jedem Wort den Zustand, in den das Wort führt,
betrachten und mal gucken, welche von denen sind äquivalent oder
welche sind nicht äquivalent.
Hier machen wir noch was strengeres.
Wir sagen, die zwei Wörter, die führen genau in denselben Zustand.
Dann sollen die als äquivalent definiert werden.
Also das ist eine Relation, die zu dem Automaten gehört.
Die ist einfach über den Automaten definiert und ist eine Relation
oder Äquivalenzrelation auf den Wörtern.
Die ist offensichtlich rechtsinvariant und eine Äquivalenzrelation.
Äquivalenzrelation, da muss man nur hier rechts gucken.
Natürlich ist Delta Sx gleich Delta Sx und wenn Delta Sx gleich Delta
Sy ist, dann ist auch Delta Sy gleich Delta Sx und Transitivität auch.
Also das ist offensichtlich.
Ich werde ab jetzt nicht mehr genauer mit Ihnen diskutieren, ob eine
Relation eine Äquivalenzrelation ist.
Und rechtsinvariant, das ist ja auch offensichtlich.
Wenn wir jetzt hier an X und Y was dranhängen, egal was das ist, wenn
X und Y von S aus in den selben Zustand führen, dann führt danach,
dann passiert danach genau dasselbe.
Was ist gerade der Index dieser
Relation?
Naja gut, wie viele verschiedene Klassen können da rauskommen, wenn
gerade die Wörter in dieselbe Klasse gesteckt, die von S aus in den
selben Zustand führen.
Das heißt, für jeden Zustand haben wir eine andere Klasse.
Für jeden Zustand natürlich, den wir von S aus erreichen.
Zustände, die von S aus überhaupt nicht erreichbar sind, spielen bei
der ganzen Angelegenheit überhaupt keine Rolle.
Das heißt also, der Index dieser Äquivalenzrelation ist gerade die
Anzahl der nicht überflüssigen Zustände unseres Automaten.
Und die Sprache zu dem Automaten, das ist ja die Menge der Wörter, die
in N-Zustände führen.
Das ist gerade die Vereinigung der Äquivalenzklassen von A nach A, die
zu den N-Zuständen von A gehören.
Das werden Wörter als Äquivalenz definiert, wenn sie in den selben
Zustand führen.
Und gerade die Wörter aus L führen in N-Zustände.
Und zu den verschiedenen N-Zuständen haben wir jetzt nach der
Definition verschiedene Klassen von Wörtern, deren Vereinigung gerade
L bildet.
Okay, damit haben wir eins nach zwei bewiesen.
Also wenn wir von so einer Sprache starten, zu der wir einen
deterministischen endlichen Automaten haben, dann können wir eine
Äquivalenzrelation definieren, die so geartet ist, dass sie
rechtsinvariant ist, dass sie einen endlichen Index hat, also Sigma
-Sterne in eine Menge von Klassen zerlegt und dass gerade einige der
Klassen dieser Äquivalenzrelation bezüglich dieser Äquivalenzrelation
L bilden.
Gut, jetzt von zwei nach drei.
Also wir starten jetzt mit einer Sprache, die Vereinigung von
Äquivalenzklassen einer rechtsinvarianten Äquivalenzrelation mit
endlichem Index ist und zeigen, dass die Nerode-Relation zu dieser
Sprache L endlich einen Index hat.
Also unsere Ausgangsrelation, die heißt R, die Nerode-Relation heißt
RL, die gehört ja zu L nach Definition.
Was wir zeigen ist, wenn zwei Wörter x und y bezüglich R in Relation
sind, dann auch bezüglich RL.
Denn damit haben wir, dass RL gröber ist als R.
R ist dann feiner als RL, das heißt also R hat dann höchstens mehr
Äquivalenzklassen.
Also daraus, wenn x RY impliziert x RL Y, dann folgt Index RL ist
kleiner als Index R.
Und da nach Voraussetzung R endlich einen Index hat, haben wir damit
auch, dass Index RL endlich ist.
Also betrachten wir mal zwei Wörter x und y, die bezüglich R in
Relation oder Äquivalenz sind.
Erstmal steht hier oben, dass R ist rechtsinvariant, also weil R
rechtsinvariant ist, gilt dann nach Definition von rechtsinvariant für
alle Z aus Sigma Stern.
xz ist auch in Relation zu yz.
Und dann gilt ja nach der Voraussetzung, dass das L Vereinigung von
Äquivalenzklassen von R ist.
Das heißt also, eine Äquivalenzklasse von R ist immer entweder ganz in
L oder ganz nicht in L.
Wenn L Vereinigung von Äquivalenzklassen ist, dann finden wir keine
Äquivalenzklasse, von denen einige in L sind, einige Wörter, die da
drin sind, einige nicht.
Also nach Voraussetzung gilt, jede Äquivalenzklasse von R gehört
entweder ganz zu L oder gar nicht zu L.
Das heißt also, xz und yz sind beide in L oder beide nicht in L, wenn
x und y in R, also bezüglich R, äquivalent sind.
Aber dann sind sie auch bezüglich RL äquivalent.
Das ist ja gerade die Definition von RL, dass das hier gilt.
Okay, das war jetzt auch leicht.
Und jetzt kommt das dritte und das ist ein ganz klein bisschen
aufwendiger.
Jetzt starten wir also mit einer Sprache und der Neurode-Relation zu
dieser Sprache und sagen, die soll endlich einen Index haben.
Also diese Relation zerlegt uns Sigma-Sterne in eine endliche Menge
von Äquivalenzklassen.
Und daraus folgern wir, dass wir dann zu dieser Sprache L auch einen
deterministischen endlichen Automaten konstruieren können.
Und den konstruieren wir jetzt tatsächlich zu dieser Neurode-Relation.
Also wir haben unsere Neurode-Relation RL zu L und dazu konstruieren
wir einen deterministischen endlichen Automaten, der L akzeptiert.
Der heißt dann auch der Automat zur Neurode-Relation und den, den ich
eben schon angekündigt habe, den werden wir auch dann über den Satz
hinaus verwenden.
Also das sei jetzt unser Automat A.
Den definieren wir folgendermaßen.
Der Schlüssel ist wieder, was wir als Zustandsmenge definieren.
Nämlich wir nehmen gerade die Äquivalenzklassen der Wörter aus Sigma
-Stern bezüglich der Neurode-Relation und sagen, die sollen die
Zustände dieses Automaten bilden.
Nochmal, zwei Wörter sind äquivalent, wenn, egal was wir hinten
dranhängen, entweder in beiden Fällen ein Wort der Ausgangssprache
rauskommt oder eben in beiden Fällen nicht.
Diese Äquivalenzrelation, die zerlegt uns Sigma-Stern in
Äquivalenzklassen und wir sagen, diese Äquivalenzklassen, die sollen
gerade die Zustände des Automaten sein und da wir gerade davon
ausgehen, dass die Neurode-Relation zu der bestimmten Sprache, die wir
hier betrachten, endlich einen Index hat, haben wir hier also
tatsächlich auch dann eine Zustandsmenge, die endlich ist.
Alles Weitere ist ziemlich kanonisch.
Als Anfangszustand nehmen wir gerade die Äquivalenzklasse des leeren
Wortes, die Äquivalenzklasse von Y.
Als die Endzustände nehmen wir gerade die Äquivalenzklassen der Wörter
aus unserer Sprache.
Das ist wohl definiert.
Hier kann nicht irgendwas Komisches passieren, dass also hier dann
plötzlich Wörter aus L und nicht Wörter aus L drin sind.
Und dann müssen wir uns nur hier unten das angucken.
Als Übergangsfunktion nehmen wir folgendes.
In dem Automat soll bei Lesen von A von dem Zustand, der zur
Äquivalenzklasse des Wortes X gehört,
übergegangen werden in die Äquivalenzklasse, die zum Wort XA gehört.
Und die Frage ist, ob das okay ist, also wohl definiert, oder ob da
irgendwas Komisches passieren kann, dass wir hier zwei Wörter
betrachten, die hier zwar zum selben Zustand gehören, also in
derselben Äquivalenzklasse sind, wo aber durch das Strandhängen von A
hier zwei verschiedene Äquivalenzklassen rauskommen.
Offensichtlich, dass das nicht passieren kann.
Denn wenn W und W' in derselben Äquivalenzklasse sind, also
Äquivalenzklasse von W gleich Äquivalenzklasse von W' bezüglich der
Nerode -Relation, dann gilt W und W' sind bezüglich Nerode-Relation
äquivalent und wegen Rechtsinvarianz gilt dann auch WA äquivalent zu W
'A und das ist das, was wir brauchen, um sicherzustellen, dass dieser
Zustand, in dem übergegangen wird von W beziehungsweise W' aus,
derselbe ist.
Dann ist auch die Äquivalenzklasse von WA gleich der Äquivalenzklasse
von W'A.
Was jetzt zu zeigen bleibt, ist, dass dieser Automat genau unsere
Sprache akzeptiert.
Das ist aber offensichtlich nach Konstruktion.
Nach Konstruktion ist Delta SW gleich Delta Äquivalenzklasse von Y, W
und das führt uns nach dieser Definition von Delta in die
Äquivalenzklasse, in der YW liegt.
Das ist ja gerade die Äquivalenzklasse von W.
Und W wird genau dann akzeptiert, wenn das hier ein Endzustand ist.
Und das ist nach Definition genau dann der Fall, wenn W aus L ist.
Der Automat ist so definiert, dass er genau die Sprache akzeptiert,
von der wir hier gestartet sind.
Was wir also haben, ist die Äquivalenz dieser drei Aussagen und bei
diesem letzten Schritt von hier nach hier haben wir eben zu einer
Nerode -Relation einer Sprache einen Automaten definiert, der auch
tatsächlich endlicher Automat ist, weil diese Nerode-Relation nach
Voraussetzung hier einen endlichen Index haben soll.
Und dieser Automat, den wir da gerade definiert haben, der hat eine
minimale Zustandsmenge unter allen Automaten, die eben zu dieser
Sprache L gehören.
Dafür betrachten wir einfach irgendeinen anderen endlichen,
deterministischen endlichen Automaten, der dieselbe Sprache akzeptiert
und zeigen, wie auch immer der aussieht, der kann nicht weniger
Zustände haben als dieser Automat der Nerode-Relation.
Und da können wir den Satz, den wir gerade bewiesen haben und alles,
was wir im Beweis gebaut haben, natürlich verwenden.
Und was wir erstmal verwenden, ist, dass bei dem Beweis von 1 nach 2
folgt, dass eine rechtsinvariante Äquivalenzrelation zu dem Automaten
gehört, die einen endlichen Index hat und sogar einen Index, der
kleiner gleich der Anzahl der Zustände des Automaten ist.
Es war diese Äquivalenzrelation, wo wir gesagt haben, zwei Wörter sind
äquivalent, wenn sie genau in denselben Zustand führen.
Da können nicht mehr Klassen rauskommen, als der Automat Zustände hat.
Und dann wegen dieser Verfolgerung von 2 auf 3 gilt, dass der Index
der Nerode-Relation kleiner gleich dem Index von r' ist.
Und jetzt von 3 nach 1 folgt dann, dass die Anzahl der Zustände
unseres Nerode-Automaten, den wir eben bei diesem Beweis definiert
haben, die ja gerade gleich Index der Nerode-Relation ist, kleiner
gleich Anzahl der Zustände von diesem Ausgangsautomaten.
Also wir fangen mit irgendeinem beliebigen Automaten an, der L
akzeptiert und zeigen, der kann auch nicht weniger Zustände haben als
der Nerode-Automat oder Automat zur Nerode-Relation.
Und das folgt eben aus den einzelnen Beweisschritten.
Okay.
Das heißt also, wir haben jetzt sozusagen im Prinzip eine
Konstruktion, um zu einer regulären Sprache einen deterministischen
endlichen Automaten anzugeben, der minimale Zustandsmenge hat.
Nämlich dieser Automat zur Nerode-Relation.
Was wir bei unserer Zustandsminimierung ursprünglich aber gemacht
haben, ist, wir sind von einem Automaten ausgegangen, haben dazu den
Äquivalenzklassenautomat gebildet und wollen jetzt eben noch
nachweisen, dass der eine minimale Anzahl von Zuständen hat.
Der hier, der Nerode-Automat, von dem wir wissen, der hat eine
minimale Anzahl von Zuständen, der gehört zu einer Sprache, der wird
sozusagen zur Sprache über die Nerode-Relation definiert.
Und jetzt müssen wir eigentlich nur zeigen, dass der
Äquivalenzklassenautomat auch nicht mehr Zustände hat, als der Nerode
-Automat, alles ausgehend von derselben Sprache.
Also Minimalität des Äquivalenzklassenautomats.
Der Äquivalenzklassenautomat zu einem beliebigen deterministischen
endlichen Automaten, ohne überflüssige Zustände, ist minimal.
Und dazu gucken wir uns an, die Sprache zu diesem deterministischen
endlichen Automaten A, dazu die Nerode-Relation, dazu im Prinzip den
Index und zeigen, der ist größer gleich Anzahl der Zustände unseres
Äquivalenzklassenautomats.
Zu zeigen, dass sie größer gleich ist, müssen wir nichts anderes
zeigen, als dass, wenn zwei Wörter bezüglich der Nerode-Relation
äquivalent sind, dann folgt daraus, die Zustände, in die diese beiden
Wörter von S ausführen, in unserem Automat A sind äquivalent.
Und das haben, kann die Anzahl der Zustände des
Äquivalenzklassenautomats nicht größer sein, als der Index der Nerode
-Relation.
Okay, also schauen wir mal zwei Wörter an.
Nehmen an, die sind bezüglich der Nerode-Relation äquivalent.
Dann folgt nach Definition der Nerode-Relation, egal was wir da rechts
ranhängen, in beiden Fällen landen wir entweder bei einem Wort in L
oder bei einem Wort, das nicht in L ist.
Das heißt, für alle Z aus Sigma Stern gilt dann, xz ist in L, genau
dann, wenn yz in L ist.
Wenn wir jetzt xz und yz in unseren Automaten einfüttern von S aus,
was passiert dann?
Na gut, dann passiert in beiden Fällen, wir enden in einem Endzustand
oder wir enden nicht in einem Endzustand.
Also hieraus folgt, für alle Z aus Sigma Stern gilt, delta s, xz ist
in F, genau dann, wenn delta s, yz in F ist.
Und das kann man natürlich auseinanderziehen, indem man erstmal guckt,
wo führt uns x von S aus hin und dann der nächste Schritt und wo führt
dann z hin.
Das heißt also, daraus folgt für alle Z aus Sigma Stern, delta von
delta von s, x, z ist in F, genau dann, wenn delta von delta von s, y,
z in F ist.
Das ist das hier nur anders hingeschrieben, aber wenn wir hier genau
hingucken, dann steht da die Eigenschaft, die erfüllt sein muss, damit
delta s, x, der Zustand, in dem wir von x von s aus bei Lesung von x
kommen, äquivalent ist zu delta s, y.
Das heißt also, hieraus folgt delta s, x, äquivalent delta s, y.
Das heißt, wenn zwei Wörter bezüglich der Neurode-Relation äquivalent
sind, dann sind auch die entsprechenden Zustände, in die die beiden
Wörter von s ausführen, äquivalent.
Damit ist die Anzahl der Zustände des Äquivalenzklassenautomats
kleiner gleich steht im Index der Neurode-Relation und weil der ja im
Prinzip minimal ist, gilt hier also Gleichheit.
Zusammenfassung.
Wie weit sind wir jetzt insgesamt gekommen?
Das ist ja sozusagen die Zusammenfassung unseres Kapitels reguläre
Sprachenendliche Automaten.
Wir haben den deterministischen Endlichen Automaten eingeführt als ein
Berechnungsmodell.
Und wir haben festgestellt, die Sprachen, die von deterministischen
Endlichen Automaten akzeptiert werden, das sind gerade die regulären
Sprachen.
Und wir haben festgestellt, dass die deterministischen Endlichen
Automaten und die nicht-deterministischen Endlichen Automaten
gleichmächtig sind.
Das heißt also, die regulären Sprachen sind auch gerade genau die
Sprachen, die von einem nicht-deterministischen Endlichen Automaten.
Und dann haben wir uns gefragt, können wir von einem nicht
-deterministischen Endlichen Automaten eigentlich zu einem
äquivalenten nicht-deterministischen Endlichen Automaten kommen?
Die Antwort ist ja, mit Potenzmengenkonstruktion.
Wir haben uns gefragt, haben wir ein Hilfsmittel, um für eine Sprache,
die wohl nicht regulär ist, auch zu beweisen, dass sie nicht regulär
ist?
Wir haben ein Hilfsmittel, aber es funktioniert nicht immer.
Das Hilfsmittel ist das Pumping Lemma und in verschärfter Form das
verallgemeinerte Pumping Lemma.
Also wir haben das Pumping Lemma für reguläre Sprachen und das
verallgemeinerte Pumping Lemma für reguläre Sprachen.
Und die können wir benutzen, um für Sprachen zu zeigen, dass sie nicht
regulär sind, aber das funktioniert nicht immer.
Bei manchen nicht-regulären Sprachen kann man das tatsächlich mit dem
Pumping Lemma oder verallgemeinerten Pumping Lemma machen.
Wir haben uns gefragt, können wir zu einem deterministischen Endlichen
Automaten einen äquivalenten deterministischen Endlichen Automaten
konstruieren, der eine minimale Anzahl von Zuständen hat?
Die Antwort ist ja, das geht, indem wir zu dem Endlichen Automaten den
Äquivalenzklassenautomat bilden.
Bei diesem Äquivalenzklassenautomat haben wir aber jetzt heute erst
dann tatsächlich bewiesen, dass er eine minimale Anzahl von Zuständen
hat und das haben wir, indem wir gezeigt haben, der hat die gleiche
Anzahl von Zuständen wie der Automat zur Nerode-Relation, von dem wir
eben vorher gezeigt haben, der hat eine minimale Anzahl von Zuständen.
Das heißt, Sie können die Konstruktion Automat zur Nerode-Relation
auch benutzen im Prinzip und zu einer Sprache einen Automaten zu
konstruieren, der eine minimale Anzahl von Zuständen hat.
Das ist nicht so ganz glatt.
Da müssen Sie erst diese Relation auf den Wörtern sozusagen ausführen,
also herausfinden, welche Wörter gehören in dieselbe Äquivalenzklasse.
Aber wenn Sie sich die Konzepte genauer angucken, dann stellen Sie
fest, das Konzept Äquivalenz von Wörtern mit der Nerode-Relation und
Äquivalenz von Zuständen, wie beim Äquivalenzklassenautomat
betrachtet, das sind dieselben Konzepte.
Bei Zuständen sagt man von den beiden Zuständen aus, liest dafür, ob
man in einem Endzustand ist oder nicht.
Das ist im Prinzip dieselbe Vorgehensweise oder das selbe Konzept, um
von zwei Wörtern aus zu sagen, es ist unerheblich, was ich rechts dran
hänge für die Frage, ob ich bei einem Wort aus der Sprache lande.
Damit wären wir mit dem Endlichen Automaten und den regulären Sprachen
durch und kommen zu einem neuen Kapitel.
Wir haben ja insbesondere festgestellt, dass das Konzept Endlicher
Automat und da ist es egal, ob wir einen deterministischen oder nicht
deterministischen Endlichen Automaten haben, bezüglich seiner
Berechnungsmächtigkeit beschränkt ist.
Endliche Automaten können genau die regulären Sprachen erkennen, aber
es gibt, das ist ganz offensichtlich, noch andere Sprachen, die nicht
regulär sind.
Auch andere Sprachen, die etwas wirklich Sinnvolles sind, wie zum
Beispiel die Sprache der korrekten Klammerausdrücke.
Wir haben nur die Buchstaben Klammerauf und Klammerzu und nehmen nur
Worte in die Sprache, die wirklich einen korrekten Klammerausdruck, zu
jeder Klammerauf dann noch eine Klammerzu kommt,
darstellen.
Und die Sprache, die kann nicht erkannt werden von einem Endlichen
Automaten, das heißt also nach mächtigeren Berechnungsmodellen zu
schauen, ist definitiv sinnvoll.
Wir gehen jetzt ziemlich weit in dem Kapitel.
Wir betrachten Turing-Maschinen.
Zwischen Endlichen Automaten und Turing-Maschinen sind noch andere
Modelle, die weniger können als Turing-Maschinen und mehr als Endliche
Automaten.
Da kommen wir später drauf zurück.
Wir betrachten Turing-Maschinen, weil wir jetzt eine sehr umfassende
Frage stellen, die sich natürlich anschließt, wenn man eben
feststellt, ja Deterministische Endliche Automaten oder Nicht
-Deterministische ebenso, die sind beschränkt in ihrer Mächtigkeit.
Nämlich, wo sind denn überhaupt Schranken der Berechenbarkeit?
Gibt es irgendwelche Sprachen, die überhaupt nicht von einem
sinnvollen Berechnungsmodell akzeptiert werden können?
Gar kein Modell angeben können, das die Sprache entscheiden kann.
Also für beliebige Worte entscheiden kann, ist das Wort in der Sprache
oder nicht.
Also sozusagen die Frage der Berechenbarkeit, gibt es nicht
berechenbare oder nicht entscheidbare Sprachen?
Das ist jetzt das Kapitel und dafür brauchen wir die Turing-Maschine
als Modell.
Und ich hole jetzt ein bisschen weiter aus, also Endliche Automaten
sind als Berechnungsmodell nicht mächtig genug.
Die Frage, gibt es ein mächtigeres realistisches Rechnermodell, das
man als Grundlage für solche ganz grundsätzlichen Fragen, wie die
Frage nach der Berechenbarkeit oder danach, ob es nicht berechenbare
oder nicht entscheidbare Sprachen sind, man dafür zugrunde legen kann.
Und die Hauptfrage ist dann, welche Probleme sind denn berechenbar und
wo sind die Schränken?
Gibt es welche, die nicht berechenbar sind?
Und ich hole jetzt weit aus, weil ich Sie daran erinnere, dass Sie im
Prinzip so ein Berechnungsmodell, das hier benutzt werden könnte, auch
schon kennen.
Das Modell der Registermaschine.
Da gehe ich jetzt ziemlich schnell durch.
Ich will Ihnen nur klarmachen, das Modell, das wir dann danach
intensiv nutzen, die Turing-Maschine, ist ein bisschen weiter weg von
unserer Vorstellung, wie Algorithmen abgearbeitet werden.
Das Modell, das sozusagen näher an den Algorithmen ist, das ist die
Registermaschine.
Aber man könnte auch jetzt mit der Maschine, also mit der RAM, diese
Überlegungen anstellen, die wir anstellen.
Nur die Turing-Maschine eignet sich gewisserweise besser, insbesondere
auch für das, was wir dann im darauffolgenden Kapitel machen, nämlich
Probleme nach ihrer Komplexität einzuordnen.
Also dies ist jetzt nur kurz als Erinnerung.
RAM, wie die aussieht, da gehe ich jetzt gar nicht so genau ein.
Also Sie haben sozusagen ein Programm, das steuert, was die Maschine
macht.
Und ein Programm besteht aus einer Folge von Befehlen.
Die Programmzeilen sind durchnummeriert und der Befehlszähler zählt
sozusagen mit und sagt dann, was folgt auf den nächsten Befehl.
Wie es am Beginn aussieht, kann ich darauf angehen.
Interessant ist eben, dann gibt es Befehle, die im Prinzip diesen
Grundoperationen entsprechen, auf die man alle Algorithmen
runterbricht.
So etwas wie addieren, subtrahieren, multiplizieren, von einer
Programmzeile zu einer anderen springen und so weiter.
Und Variationen.
Und dieses Modell ist, wie ich eben sagte, nah an Algorithmen.
Das benutzt man, um dann Aufwand, Laufzeit von Algorithmen
abzuschätzen.
Üblicherweise mit dem uniformen Kostenmodell, wo jeder Befehl
sozusagen eins zählt.
Zumindest wenn man keine großen Zahlen hat.
Wenn man sehr große Zahlen hat, dann muss man irgendwie auch die Länge
der Zahlen mit reinnehmen ins Kostenmodell.
Dann nimmt man sozusagen das logarithmische Kostenmodell.
Also wie gesagt, RAM ist sozusagen die Grundlage, die man im
Hinterkopf hat, zumindest wenn man Algorithmen sich anschaut.
Und deren Aufwand zum Beispiel.
Und dazu äquivalent ist die Turing-Maschine, die eben nicht so nah an
dem Algorithmusbegriff ist.
Und die Turing-Maschine, das ist jetzt für Sie auch nicht völlig neu.
Soviel ich weiß, war in den Grundbegriffen der Informatik die Turing
-Maschine auch mal kurz drin.
Ich gehe jetzt aber trotzdem sozusagen ausführlich die Grundlagen
durch, weil wir mit der Turing-Maschine jetzt eine ganze Weile
arbeiten.
So, so eine Turing-Maschine, die besteht aus einem beidseitig
unendlichen Band und es gibt Varianten von Turing-Maschinen, auch mit
mehreren Bändern und so.
Da gehen wir auch mal bei Gelegenheit kurz drauf ein.
Aber so das Grundmodell ist, ich habe ein Band, das ist nach beiden
Seiten unendlich lang und das ist sozusagen das Band, auf dem die
Eingabe steht und auf dem irgendwas gemacht wird.
Und gemacht wird heißt, also da gibt es so einen lese-schreib-Kopf,
der auf dem Band hin und her geht, liest, was an bestimmten Stellen
des Bandes ist und da auch möglicherweise überschreibt er auch was.
Also ein lese-schreib-Kopf, der kann nach rechts, nach links gehen,
liest, was an der Stelle auf dem Band steht, möglicherweise
überschreibt er die Stelle auch und gesteuert wird das Ganze durch die
sogenannte endliche Kontrolle.
Und zwar ist diese endliche Kontrolle immer in einem von der endlichen
Menge vorgegebenen Zustände.
Das entspricht so dem Befehlszähler bei der RAM.
Und bei dem Eingabe- und Rechenband ist es so, das enthält sozusagen
eine Folge von Symbolen.
Mal eins pro Zelle, beziehungsweise können auch auf Zellen nichts
stehen, sozusagen Plenk, und das entspricht sozusagen dem, was bei der
RAM die Register sind.
Und das Verhalten der Turing-Maschine kann man folgendermaßen
beschreiben.
Der lese-schreib-Kopf ist gerade auf einer Position, er liest das
Symbol auf der aktuellen Position und geht dann in den Folgezustand
über, je nachdem, was die endliche Kontrolle für die Situation
vorsieht.
Und dazu gehört auch, dass er eventuell das Symbol, das er gerade
gelesen hat, überschreibt.
Und dazu gehört auch, dass er möglicherweise eine Position nach rechts
oder nach links geht.
Also lese sozusagen ausgehend vom aktuellen Zustand, macht die Turing
-Maschine Folgendes, lese das Symbol, an dem gerade der lese-schreib
-Kopf steht, gehe in einen Folgezustand über, überschreibe eventuell
das Symbol, bewege eventuell den Schreibkopf nach rechts oder nach
links.
Und dann kann man folgendermaßen eine deterministische Turing-Maschine
definieren.
Q ist eine endliche Zustandsmenge.
Diese Zustandsmenge gehört zu dieser endlichen Kontrolle.
Da bezieht sich das Endlich bei der endlichen Kontrolle.
Wir haben ein Eingabealphabet, Sigma nennen wir das wieder.
Wir haben ein Symbol für gar nichts, nämlich das Plank-Symbol, das ist
nicht in Sigma.
Wir haben ein Endliches-Band-Alphabet, also noch zusätzliche Symbole.
Das Band-Alphabet enthält Sigma und enthält das Plank-Symbol, aber
möglicherweise noch weitere Symbole.
Wir haben einen Startzustand, an dem startet sozusagen die ganze
Angelegenheit.
Wir haben eine Übergangsfunktion, da müssen wir mal genauer hingucken.
Die Übergangsfunktion nimmt einen Zustand und ein Symbol.
Die Übergangsfunktion sagt uns, was gemacht wird, wenn die endliche
Kontrolle in einem ganz bestimmten Zustand ist und der Lese
-Schreibkopf ein ganz bestimmtes Symbol liest.
Und was wird gemacht?
Wir gehen in einen Folgezustand über, schreiben möglicherweise ein
neues Symbol an die Stelle, wo der Lese-Schreibkopf gerade ist und
gehen mit dem Lese-Schreibkopf entweder nach links oder nach rechts
oder bleiben damit da.
Das heißt also, so ein Paar, bestehend aus einem Zustand und einem
Symbol aus dem Band-Alphabet, wird durch die Übergangsfunktion
überführt in so ein Trippel, bestehend aus einem Zustand, einem Symbol
und einer Vorgabe links-rechts-gar-nix.
Also L bedeutet gehen nach links, R bedeutet gehen nach rechts und N
bedeutet stehenbleiben für den Lese-Schreibkopf.
Und dann gibt es noch möglicherweise eine Menge F von ausgezeichneten
Endzuständen.
Da werden wir je nachdem, wie es uns gerade passt,
tatsächlich eine Vorgabe machen, das sind die Endzustände, wenn wir in
denen landen, dann wird akzeptiert.
Entsprechend, ohne dass wir jetzt akzeptieren von Turing-Maschinen
schon definiert haben, einfach entsprechend unserer Vorstellung, die
wir durch die Automaten mitbringen.
Wir haben genau zwei Zustände, bei denen eine Turing-Maschine enden
kann.
Der eine steht genau für Wortwört akzeptiert und der andere steht für
Wortwört nicht akzeptiert.
Oder wir werden auch sagen, wir haben jetzt gar keine nach Definition
der Turing-Maschine ausgezeichneten Endzustände, sondern wir sagen,
das endet, wenn die Turing-Maschine nichts mehr macht.
Bemerkung dazu.
Die Übergangsfunktion Delta gehört ja, wie wir eben gesehen haben, zu
so einem Paar, bestehend aus einem Zustand und einem Symbol und
überführt dieses Paar in einen Zustand, ein Symbol und so ein gehe
links oder gehe rechts oder mache gar nichts.
Und das kann man auch symbolisch oder grafisch darstellen, so ähnlich
wie bei endlichen Automaten, dass man eben Zustände in so Boppel
reinschreibt und dann so ein Pfeil macht zwischen zwei Zuständen oder
von einem Zustand über einen anderen, der genau das hier ausdrückt,
nämlich wenn ich im Zustand Q bin und A lese, dann wird die Stelle mit
B überschrieben, der Leseschreibkopf geht nach links und ich bin im
Folgezustand P.
Das heißt, zu der grafischen Darstellung gehört etwas, was zu der
grafischen Darstellung gehört, was sagt, ich bin erst in dem Zustand Q
und hier lese ich A und was danach passiert ist, ich bin danach in dem
Zustand P, hier an der Stelle steht danach B und der Leseschreibkopf
geht eins nach links.
Und jetzt so einfach Konventionen, wie man sagt, wie das Ganze
losgeht, das legen wir jetzt mal so fest, aber je nachdem, wenn es
passt, kann man auch, ich sag mal, äquivalente andere Konventionen
zugrunde legen.
Also was wir jetzt zugrunde legen ist, dass die Turing-Maschine immer
im Zustand S, in diesem ausgezeichneten Startzustand, startet, dass
der Lese- und Schreibkopf an der linken Stelle des Bandes, in dem ein
Eingabesymbol steht, also das ist dann sozusagen diese Stelle 0 und
sie stoppt, wenn sie zum ersten Mal in einen Endzustand kommt, wenn
wir so ausgezeichnete Endzustände haben, oder zu einem Zustand Q, wo
egal, was da jetzt gelesen wird, wenn wir im Zustand Q sind, nichts
mehr passiert.
Das heißt also, das Symbol wird nicht überschrieben und der Lese- und
Schreibkopf bewegt sich nicht.
Das ist irgendwie klar, wenn wir im Zustand Q sind und die
Übergangsfunktion sagt, wenn wir im Zustand Q A lesen, dann bleiben
wir in Q, lassen das A da stehen und machen gar nichts, passiert also
wirklich nichts mehr, wenn wir A lesen.
Das heißt also, irgendwelche Übergänge, die aus Endzuständen
herausführen, sind überflüssig.
In dem Sinne überflüssig wie überflüssige Zustände bei endlichen
Automaten.
Wir gucken uns jetzt einfach mal ein Beispiel an.
Beispiel einer Touring-Maschine.
Also so können wir die grafisch darstellen, nachdem was wir uns eben
überlegt haben.
Wir haben da den Start-Zustand, hier haben wir noch zwei andere
Zustände und die Übergangsfunktion wird also an so ein Pfeil von einem
Zustand zum anderen herangeschrieben, in dem Sinne, dass man sagt,
wenn in dem Ausgangszustand das Symbol gelesen wird, dann wird an die
Stelle das Symbol hinter dem senkrechten Strich geschrieben und der
Lese -Schreib-Kopf macht das, was hier noch rechts daneben steht.
Also in dem Fall heißt es nach rechts gehen.
Also hier, wenn wir die Touring-Maschine genauer angucken, sehen wir
folgendes.
Wenn die Touring-Maschine im Start-Zustand S ist und ein Plank-Symbol
liest, lässt sie das Plank-Symbol da stehen und geht mit dem Lese
-Schreib -Kopf um eine Position nach rechts und die Endliche Kontrolle
bleibt im selben Zustand.
Und wenn in dem Start-Zustand oder im Zustand S eine 0 gelesen wird,
dann bleibt die 0 da stehen und der Lese-Schreib-Kopf geht eine
Position nach rechts und die Endliche Kontrolle wechselt von dem
Zustand S in den Zustand Q1.
Während wenn in dem Zustand S eine 1 gelesen wird, wird die 1
weggewischt, Plank stattdessen dahingeschrieben, der Lese-Schreib-Kopf
geht nach 1 nach links und die Endliche Kontrolle geht in den Zustand
Q2.
So weit, so gut.
Jetzt was in Q1 und Q2 passiert, das ist jetzt spannend.
Spannend für das, was diese Touring-Maschine eigentlich treibt.
Wenn sie in Q1 ist und liest eine 0, lässt sie die 0 da stehen und
geht 1 nach rechts.
Wenn sie in Q1 ist und liest nur 1, lässt sie die 1 da stehen und geht
1 nach rechts.
Wenn sie in Q1 ist und Plank liest, lässt sie Plank da stehen und geht
1 nach rechts.
Ohne dass ich es dazu gesagt habe oder ohne dass es auf der Folie
steht, gehen wir davon aus, dass unser Alphabet nur aus 0 in 1
besteht.
Wir haben auch in dem Band-Alphabet keine zusätzlichen Symbole außer
dem Plank-Symbol.
Das heißt also, von Q1 aus ist gerade egal, was die Touring-Maschine
liest, sie lässt das unverändert und geht immer weiter.
Auch wenn sie nichts liest, geht immer weiter nach rechts.
Die Touring-Maschine hat ein rechts und links unendliches Band.
Das heißt also, wenn wir in den Zustand kommen, geht es immer weiter.
Die Touring-Maschine endet nicht, wenn sie jemals in den Zustand Q1
kommt.
Wenn sie in den Zustand Q2 kommt, macht sie folgendes.
Wenn sie da eine 0 liest, lässt sie die 0 stehen und der Lese
-Schreibkopf bewegt sich nicht mehr.
Und die endliche Kontrolle bleibt im selben Zustand.
Im Prinzip ist es genauso, wenn eine 1 gelesen wird oder wenn ein
Plank gelesen wird.
Also die drei Möglichkeiten, was gelesen werden kann, führen bei Q2
dazu, dass die Eingabe da stehen bleibt oder das Symbol, was da gerade
gelesen wird, da stehen bleibt und der Lese-Schreibkopf sich nicht
bewegt.
Das heißt also, wenn wir jemals nach Q2 kommen, passiert nichts mehr.
Wenn wir jemals nach Q1 kommen, geht es immer weiter, unendlich lange.
Wenn wir jemals nach Q2 kommen, passiert nichts mehr.
Hier habe ich so einen Doppelkreis drum gezeichnet, um Q2, um zu
sagen, das ist unser ausgezeichneter Endzustand.
Aber selbst wenn wir das nicht so definieren, ist das ein Endzustand,
weil aus Q2 heraus passiert ja nichts mehr.
Das heißt also, was macht diese Touring-Maschine?
Nur wenn sie irgendwann mal eine 1 liest, geht sie nach Q2 über.
Nachdem sie möglicherweise eine ganze Menge Planks gelesen hat, eine 1
liest, geht sie nach Q2 über und hält da.
Während wenn sie, nachdem sie möglicherweise eine ganze Menge Planks
gelesen hat, eine 0 liest, geht sie nach Q1 und macht dann diese
Story, ich gehe immer weiter nach rechts.
Das heißt also, diese Touring-Maschine akzeptiert die Wörter, die mit
einer 1 beginnen.
Nach unserer Konvention steht der Lese-Schreibkopf am Anfang ja
sowieso 1 links von dem Beginn der Eingabe.
Das heißt also, dass da hier jetzt erstmal so Planks gelesen werden,
wäre nach der Konvention sowieso nicht der Fall, es sei denn, die
Eingabe wäre leer.
Das heißt genau dann, wenn die Eingabe mit einer 1 startet, geht die
Touring -Maschine, akzeptiert die Touring-Maschine die Eingabe.
So kann man das hier interpretieren.
Also Touring-Maschine kennt alle Wörter aus 0,1 Stern, die mit einer 1
beginnen.
Und dann macht sie aber noch mehr.
Sie löscht die führende 1, falls vorhanden.
Und alles andere bleibt auf dem Band unverändert.
Also dann geht sie ja nicht mehr weiter, das heißt, das bleibt da
stehen, beziehungsweise wenn am Anfang eine 0 war, macht sie ja das
hier.
Einfach immer weitergehen.
Wenn sie stoppt, dann steht der Lese-Schreibkopf nach diesem Stopp
links neben der Stelle, an der die führende 1 gelesen wurde.
Hier E1 nach links.
Und das Q1 ist für akzeptieren unwesentlich.
Also da wird nie gestoppt und in dem Sinne ist das unwesentlich.
Wir haben hier festgestellt, es gibt also Eingaben, bei denen die
Touring -Maschine möglicherweise nie stoppt.
Da müssen wir uns dann nochmal mit beschäftigen, wenn wir formal
definieren, was heißt denn, eine Touring-Maschine akzeptiert eine
Sprache?
In dem Beispiel ist auch klar, welche das sind.
Welche Eingaben das sind, bei denen die Touring-Maschine nie stoppt.
Nämlich alle, die nicht mit einer 1 beginnen.
Was eben bei Eingaben über 0, 1 die sind, die mit einer 0 beginnen.
Aber was hier auffällig ist, auch im Vergleich zu endlichen Automaten,
ist, dass so eine Touring-Maschine nicht nur einfach so eine Eingabe
abarbeitet und dann sagt, ja ist okay, oder vielleicht irgendwie sagt,
ist nicht okay, oder immer irgendwie weiter sprudelt, sondern sie
verändert ja auch was auf dem Band.
Und das, was da, nachdem die Touring-Maschine stoppt, auf dem Band
steht, was irgendwie eine Modifikation oder Veränderung der Eingabe
ist, das kann man als Ausgabe interpretieren.
Das heißt also, im Gegensatz zum endlichen Automaten, der nur liest
und dann akzeptiert oder nicht akzeptiert, produziert eine Touring
-Maschine auch eine Ausgabe.
Ausgabe gleich Inhalt des Bandes nach Stoppen oder nach Bearbeiten.
Das heißt also, die Touring-Maschine realisiert so eine partielle
Funktion, die von Menge der Wörter über dem Eingabealphabet in die
Menge der Wörter über dem Bandalphabet führt.
Also wenn die Eingabe modifiziert wird oder irgendwas überschrieben
wird, dann kann die Touring-Maschine da ja auch irgendwas aus Gamma
hinschreiben, was nicht in Sigma ist, also irgendwas aus dem
Bandalphabet.
Das heißt also, die Eingabe ist aus Sigma Stern und die Ausgabe, das
was auf dem Band steht, nachdem die Touring-Maschine stoppt, ist
irgendwas aus Gamma Stern.
Partielle Funktion, weil für bestimmte Eingaben aus Sigma Stern die
Touring -Maschine gar nicht stoppt.
Das haben wir ja eben festgestellt.
Bei dem kleinen Beispiel ist es schon so, dass Eingaben, die mit einer
Null anfangen, dazu führen, dass die Touring-Maschine immer weiter
macht.
Das heißt, denen wird gar nichts zugeordnet mittels dieser partiellen
Funktion.
Das heißt also, eine Touring-Maschine realisiert eine partielle
Funktion, f von Sigma Stern nach Gamma Stern.
Und dem Beispiel hier ist das, Eingabe w wird zugeordnet einem v.
Falls w ein Wort ist, das mit 1 beginnt und nach der 1 das Wort v
folgt.
Nämlich dann macht sie das, die 1 wird mit blank überschrieben und die
Touring -Maschine lässt den Rest unverändert unendet.
Das heißt also, für so ein w, dass die Form hat 1v, steht nach Lesen
von w,
v auf dem Band.
Das heißt also, die Ausgabe für die Eingabe w ist v.
Und für alle anderen Wörter, die mit einer Null beginnen, endet die
Touring -Maschine nicht.
Also könnte man auch nicht von einer Ausgabe sprechen.
Gar nicht wissen, zu welchem Zeitpunkt soll man denn gucken.
Auch das wieder eher eine Konvention.
Wenn die Touring-Maschine irgendwelche Übergänge hat, die gar nicht
wesentlich sind für das, was sie macht, also für die Frage, welche
Wörter führen zum Enden und was steht dann auf dem Band, kann man das
auch in der grafischen Darstellung der Touring-Maschine weglassen.
Das heißt also, Touring-Maschinen werden wir oft nur unvollständig
angeben.
Die Übergangsfunktionen nur für die Übergänge, die wirklich eine Rolle
spielen für das, was die Touring-Maschine macht.
Also hier in unserem Fall hätte man auch dann sagen können, also
wesentlich ist ja nur das, was sie macht, wenn sie dann nachher
stoppt, also was sie macht bei Wörtern, die mit einer Eins beginnen
und das ist eben so darstellbar.
Wir haben einfach nur diese zwei Zustände und diese Übergänge.
Das kann man sozusagen künstlich vervollständigen, indem man sagt, was
passiert denn hier, wenn eine Null gelesen wird.
Also hier hat der Wort nie gestoppt.
Und dann macht man folgendes, dass man sagt, wenn für eine bestimmte
Kombination Zustand Q, Symbol A, kein Übergang definiert ist, dann
stoppt die Touring-Maschine in diesem Zustand.
So und jetzt sozusagen letzte Folie für heute, eine sehr volle Folie,
die aber sehr wichtig ist, da fangen wir dann auch das nächste Mal
wieder mit an.
Also sehr wichtig, deshalb werden wir jetzt noch ein paar Minuten
brauchen, um da durchzugehen.
Also Definition einer Touring-Maschine und was heißt denn akzeptieren
bei einer Touring-Maschine?
Eine Touring-Maschine akzeptiert eine Eingabe, wenn sie nach Lesen
dieser Eingabe in einem Zustand aus der Menge der Endzustände stoppt.
Wir gehen jetzt mal davon aus, wir haben Endzustände vorgegeben.
Und sie akzeptiert eine Sprache L, wenn sie genau die Wörter aus L als
Eingabe akzeptiert.
Das ist im Prinzip so wie bei endlichen Automaten, nur müssen wir
hierbei im Hinterkopf halten, es kann auch Wörter geben, die dazu
führen, dass die Touring-Maschine nie stoppt.
So, eine Sprache L heißt rekursiv oder entscheidbar, wenn es eine
Touring -Maschine gibt, die auf allen Eingaben stoppt und eine Eingabe
W genau dann akzeptiert, wenn W in L ist.
Das ist jetzt ganz wichtig.
Jetzt konzentrieren wir uns darauf, dass Touring-Maschinen
möglicherweise bei bestimmten Eingaben stoppen, bei bestimmten aber
nicht.
Wann sagt man jetzt, eine Sprache ist entscheidbar?
Es kann für ein Wort entschieden werden, ob es in der Sprache ist oder
nicht.
Wir sagen, eine Sprache ist entscheidbar, wenn es eine Touring
-Maschine gibt, die auf allen Eingaben stoppt und genau die Eingaben
aus der Sprache akzeptiert.
Und wenn das so ist, dann können wir wirklich sagen, okay, Sigma
-Stern, das ist sozusagen die Menge aller Wörter, wir interessieren
uns für L, Teilmenge aus Sigma-Stern.
Okay, da haben wir unsere Touring-Maschine, die stoppt auf allen
Eingaben von Sigma-Stern und akzeptiert genau die aus L.
Das heißt, wir haben eine Touring-Maschine, die auch für jede Eingabe
entscheidet, ja, die gehört zu L oder nein, die gehört nicht zu L.
Und das für L sagen können, es gibt so eine Touring-Maschine, dann
sagen wir, L ist entscheidbar.
So, jetzt wissen wir aber, es gibt Touring-Maschinen, die bei
bestimmten Eingaben nicht stoppen, möglicherweise aber bei allen
Eingaben unserer vorgegebenen Sprache stoppen.
Da können wir also, wenn es für unsere vorgegebene Sprache nur so eine
Touring -Maschine gibt, dann können wir nicht unbedingt so richtig von
entscheiden reden, weil bei irgendwelchen Eingaben passiert das ja,
dass die Touring-Maschine nie stoppt.
Da wissen wir ja gar nicht jetzt, ist die Eingabe in L oder ist sie
nicht in L.
Und solche nennen wir semi-entscheidbar, also eine Sprache L aus Sigma
-Stern heißt semi-entscheidbar oder rekursiv aufzählbar.
Wenn es eine Touring-Maschine gibt, die genau die Eingaben W
akzeptiert, die aus L sind.
Da sagen wir also nichts darüber, was passiert bei Eingaben, die nicht
aus L sind.
Kann sein, dass sie bei Eingaben, die nicht aus L sind, auch manchmal
stoppt, aber manchmal vielleicht auch nicht.
Und das ist eben kein verlässlicher Entscheidbarkeitsvorgang.
Deshalb sprechen wir bei so einer Sprache, für die es nur so eine
Touring -Maschine gibt, davon, dass sie semi-entscheidbar ist.
Also Verhalten der Touring-Maschine bei Eingabe W, nicht in L, ist in
dem Fall nicht definiert.
So können wir das interpretieren.
Touring-Maschine stoppt entweder oder stoppt nicht und was das ist,
wenn die nicht stoppt, das interpretieren wir als undefiniert.
Okay, da würde ich jetzt mal für heute enden.