So, jetzt begrüße ich Sie zu einer weiteren Fortsetzung der Vorlesung
Grundlagen der Informatik.
Letztes Mal hatten wir schon einiges gemeinsam getan.
Wie gesagt, nochmal für die Aufzeichnung.
Da ich einen Haken nicht gemacht hatte oder ein Feld nicht bedient
hatte, war der Ton nicht aufgezeichnet worden und die ganze
Aufzeichnung hatte nicht funktioniert.
Und ich wollte jetzt nur noch einmal kurz wiederholen, was wir letztes
Mal gemacht hatten.
Wir hatten uns letztes Mal einige Dinge angeschaut innerhalb dieses
Kapitels 1.
Ich hatte Ihnen etwas erzählt über die Chomsky-Grammatiken, überhaupt
über Grammatiken, mit denen man Sprachen beschreiben kann.
Wir hatten uns darüber ausgetauscht, wie das funktioniert.
Ich hatte Ihnen ein Beispiel gegeben von einer Bakus-Naur-Form, das
war nochmal hier zurück.
Das war die Bakus-Naur-Form für eine einfache Programmiersprache und
hier nur dafür, wie Namen aussehen.
Wir hatten dann das nochmal als Chomsky-Grammatik formuliert und dann
gesehen, wie man mit einer Grammatik Wörter ableiten kann.
Ich hatte Ihnen dann erzählt, wie eine Sprache einer Chomsky-Grammatik
aussieht.
Also alles gerade die Wörter über dem Terminalalphabet, die man aus
dem Startsymbol ableiten kann.
Das war hier die wesentliche Definition dafür, die durch eine
Grammatik erzeugte Sprache.
Wir hatten uns dann nochmal angeschaut, was man da alles ableiten
kann.
Wir hatten ein paar Vereinbarungen getroffen, Notationen, die wir
immer verwenden.
Und wir hatten nochmal gesehen, was wir eigentlich untersuchen wollen.
Das eine ist nämlich das Wortproblem.
Wie aufwendig ist es, zu überprüfen, ob ein Wort tatsächlich zur
Sprache gehört oder nicht.
Oder anders ausgedrückt, wie aufwendig ist es, von einem Programm zu
überprüfen, ob es richtig formuliert ist oder ob es die Regeln der
Grammatik verletzt.
Und das zweite ist, können wir alles das, was wir ausdrücken müssen,
tatsächlich auch ausdrücken.
Das sind die beiden wesentlichen Fragen, die uns im Weiteren
verfolgen.
Und jetzt machen wir mal weiter.
Da hatten wir die Chomsky-Grammatik-Hierarchie gesehen.
Von den einfachsten allgemeinen oder von den allgemeinsten
Grammatiken, die wir zunächst angeschaut haben, bis runter zu den
einfachsten, also über die kontextsensitiven, die kontextfreien und
runter zu den rechtslinearen, die dann uns die einfachste Sprachklasse
liefern.
Wir hatten dann entsprechend von den Grammatiktypen auf die
Sprachtypen geschlossen und gesehen, dass die eine echte Hierarchie
bilden.
Jede Sprache vom Typ 3 ist auch eine Sprache vom Typ 2, vom Typ 1, vom
Typ 0.
Und damit waren wir da durch und kamen zum nächsten Kapitel, nämlich
zum Kapitel 2, endliche Automaten.
Und auch da habe ich Ihnen einiges vorgeschrieben.
Ich muss das hier einmal kurz wegnehmen, damit ich hier rankomme, um
Ihnen das richtig zeigen zu können.
Ups, da ist es.
Und dann schieben wir das wieder hier runter.
Also, ich hatte Ihnen einiges erzählt über endliche Automaten.
Und auch da hatten wir dann gesehen, wie man solche Automaten
definieren kann.
Wir hatten also hier gesehen, wir haben interne Zustände, wir haben
ein Eingabeband, ein Ausgabeband, wir können lesen, was auf dem Band
steht, wir können was schreiben.
Und das ist genau das, was ein Automat macht.
Der bekommt Eingaben, der kann was damit tun und kann seinen internen
Zustand ändern und kann etwas ausgeben.
Und dann hatten wir gesehen, wie so ein Mili-Automat definiert ist,
der nämlich abhängig von Eingabe und Zustand ein Ausgabesymbol
produziert.
Hatten dazu auch ein paar Beispiele angeschaut, hatten uns angesehen,
dass man die Zustandstafel hat, ein Zustandsdiagramm.
Ich habe Ihnen das Tiefgaragentor als Beispiel erläutert.
Und dann hatten wir gesehen, wie man die Abbildung, die
Zustandsübergangsfunktion auf Wörter erweitern kann.
Das ist eine kanonische Definition, natürliche Fortsetzung.
Im Prinzip ist das eine Fortsetzung, algebraisch ausgedrückt, einer
Abbildung auf ein freies Monoid, das ein einfaches erzeugendes System
hat, nämlich das Alphabet, das E-Stern, das ist ein freies Monoid über
dem Alphabet.
Das war die algebraische Formulierung, die brauchen wir aber nicht.
Die kann man für andere Sachen einsetzen, kann man viele interessante
Sachen machen, über die Strukturen von Sprachen, die wir hier aber
nicht brauchen.
Und das ist die erste neue Folie für heute.
Da kommen wir auf das zweite Beispiel, nämlich den Einwagenautomaten.
Also ich habe hier so eine Folge von immer komplizierteren Automaten,
die ich Ihnen vorstellen wollte.
Und das hier ist also jetzt der Automat, der ein bisschen mehr kann.
Letztes Mal fragte jemand, wofür brauchen wir das eigentlich?
Und es sind halt viele Geräte oder viele Objekte in der realen Welt,
die man tatsächlich als endliche Automaten beschreibt.
Nun muss man wissen, wie macht man das so, dass tatsächlich jemand,
der spezifiziert, wie ein Automat oder was der tun soll, dass man das
überführen kann, tatsächlich in ein geeignetes Programm oder geeignete
Realisierung, sodass genau das passiert, was vorher als Wunsch
geäußert worden war.
Und dazu braucht man eben einfach Kenntnis von Automaten, wie man die
tatsächlich aufschreibt.
Und da kann man auch Aussagen darüber machen, welche Fähigkeiten die
eigentlich haben.
Gut, das hier ist also ein Warenautomat, der also denjenigen, die
daran gehen, hier in dem Fall nur ein einziges Produkt liefern,
nämlich Schokoriegel.
Man hätte auch verschiedene Sachen auswählen können, dann wird es doch
komplizierter.
Wir haben also hier vorne irgendwo die Waren, die sind da sichtbar.
Wir haben einen Münzeingabeknopf, das ist der hier, oder einen
Schlitz.
Dann haben wir einen Rücksetzknopf und da haben wir eine Wähltaste.
Um auszuwählen, was man haben möchte, kann man also verschiedene
Sachen eventuell auswählen, das wird hier aber nicht tatsächlich
modelliert.
Und was eingegeben wird, das ist entweder eine 1-Euro-Münze, 2-Euro
-Münze oder eine falsche Münze.
Wir können auf den Wählknopf drücken und wir können auf den
Rückgabeknopf drücken.
Das sind die möglichen Eingaben.
Dann gibt es Ausgaben, das Geld kann zurückgegeben werden.
Wenn man eine falsche Münze hat, wird das Geld sofort zurückgegeben
und mit der Meldung falsche Münze.
Es wird eine Warenausgabe erfolgen, wenn man genügend Geld eingeworfen
hat und eine Warenausgabe und Restgeldrückgabe, wenn man mehr
eingeworfen hat, als das Objekt kostet.
Und ansonsten kann es auch sein, dass gar nichts ausgegeben wird.
Auch das haben wir als Ausgabe angegeben, damit man das eben
formulieren kann.
Und dann gibt es eine ganze Reihe Zustände mittendrin.
Hier die Zustandsmenge, die jetzt nur darauf abhebt, wie viel Geld
wurde eingeworfen, damit man tatsächlich dem Wunsch entsprechen kann,
eine Ware auszugeben.
Und hier gehen wir mal davon aus, dass 4 Euro insgesamt eingeworfen
werden sollen, also 1, 2, 3, 4 und das sind die möglichen Zustände.
Dann gibt es einen Übertrag, wenn zu viel Geld eingeworfen wurde.
Und das sind also die Zustände, die wir hier brauchen.
Und das ist auf der nächsten Folie dargestellt.
So sieht jetzt der Automat aus, hier angegeben mit dem
Zustandsdiagramm.
In diesem Fall ist es schon fraglich, was ist eigentlich
übersichtlicher?
Das Zustandsdiagramm, also dieser Graph, der uns angibt, wie die
Übergänge und Ausgaben des Automaten sind, abhängig von den Eingaben,
oder die Zustandstafel.
Und ich glaube, ich erkläre das lieber an der Zustandstafel.
Also wenn nichts eingegeben wurde, 0 der Zustand, und es wird eine
Münze eingeworfen, ist anschließend der Zustand 1, das heißt nicht 1,
Strich, sondern dieser Strich soll heißen, es wird keine besondere
Ausgabe gemacht.
Wenn eine 2-Euro-Münze eingegeben wurde, ist es natürlich der Zustand
2.
Wenn eine falsche Münze eingegeben wurde, ist der Zustand 0, und es
wird das ganze Geld ausgegeben, inklusive der falschen Münze.
Wenn die Wähltaste gedrückt wird, passiert gar nichts, der Zustand
ändert sich nicht, und wenn der Rückgabeknopf gedrückt wird, wird
natürlich im Zustand 0, der Zustand 0 beibehalten, wird auch nichts
ausgegeben.
Und entsprechend geht das weiter mit Zuständen 1, 2, 3, 4, immer etwas
mehr kann man eingeben, hier beim Zustand 3 kommt einmal etwas
anderes, hier kann es sein, wenn eine 2-Euro-Münze eingegeben wird,
dass wir 5 Euro drin haben, und dann wird entsprechend, das
registriert als Übertrag, also zu viel Geld, und hier sehen Sie, wenn
eine falsche Münze eingegeben wurde, wird die falsche Münze
zurückgegeben, aber der Zustand bleibt gleich, also es wird nicht
alles Geld zurückgegeben, nur die falsche Münze.
Und ansonsten, wenn der Rückgabeknopf gedrückt wird, geht man immer
auf den Zustand 0 zurück, und das Geld geht zurück.
Ansonsten, wenn wir im Zustand 4 sind, und es werden noch weitere
Münzen eingegeben, dann haben wir halt einen Übertrag, zu viel Geld,
falsche Münze wird auch ausgegeben, wenn der Wählknopf gedrückt wird,
dann erfolgt eine Warenausgabe, und wir gehen zurück auf den Zustand
0, also es werden für 4 Euro Schokoriegel ausgegeben.
Ich weiß nicht, wie viele, ist ja völlig egal, irgendein riesen
Schokoriegel.
Und der Rückgabeknopf würde bedeuten, dass eben keine Ware, sondern
nur Geld zurückgegeben wird.
Entsprechend für den Zustand Ü passiert im Prinzip das Gleiche, nur
dass eben jetzt Geld zurückgegeben wird und so weiter.
Jetzt sehe ich hier eine Frage, auf die ich jetzt mal kurz reagieren
möchte.
Was macht der Automat, wenn der Zustand nicht definiert wurde?
Hier ist aber jeder Zustand definiert.
Wir haben ja diese Zustände, wir haben 6 Zustände, 0 bis 4 und Ü, das
sind 6 Zustände, die hat der Automat und beim Einschalten, nehmen wir
mal an, ist der im Zustand 0.
Das habe ich hier nicht modelliert, könnte man dazu modellieren.
Da wäre also der Zustand 0, wäre der Startzustand, in den er erstmal
gebracht werden muss.
Wir nehmen aber an, dass er beim Einschalten im Zustand ist und damit
ist dann eigentlich alles weitere definiert.
Also hier sind alle möglichen Übergänge bei den erlaubten Eingaben und
sind hier angegeben.
Da kommt also dieser Fall nicht vor.
Wir werden später sehen, dass es Automaten gibt, bei denen wir nicht
alles angeben müssen.
Das sind sogenannte nicht deterministische Automaten, da kommen wir
später noch drauf.
Hier ist noch eine Frage.
Bitte diese Zustandstafel nochmal erklären.
Also, nochmal, wir sind im Zustand 0, geben 2 Euro ein.
Dann sagt der, wir gehen in Zustand 2 und es passiert nichts weiter.
Im Zustand 2 geben wir 1 Euro ein, sind im Zustand 3, es passiert
immer noch nichts.
Gehen in Zustand 3, geben meinetwegen 2 Euro ein, kommen in den
Übertrag - oder zu viel Geld-Zustand und es passiert immer noch keine
Ausgabe, sind in diesem Zustand.
Und wenn jetzt weiter Münzen eingegeben werden, kann man beliebig
machen, der bleibt in diesem Zustand.
Aber wenn die Wähltaste gedrückt wird, dann wird entsprechend die Ware
ausgegeben, er geht zurück in den Zustand 0 und dann ist er bereit für
die neue Eingabe und gibt außerdem eben das Geld zurück, das
überschüssige, weil er mehr als 4 Euro eingegeben wurden.
Und wenn er den Rückgabeknopf drückt, dann haben wir eben immer den
Effekt, dass er auf den Zustand 0 zurückgeht und das Geld wieder
zurückgibt.
Jetzt gibt es hier noch eine Frage, oder war das die gleiche?
Das war die gleiche Frage, da muss ich nur auf Ansatz gehen.
Also, und es gibt noch, jetzt sollte ich aber mal hier auf die...
Wieso?
Jetzt ist die Frage weg.
So, das zu diesem einfachen Automaten.
Ich hoffe, Sie haben das nachvollziehen können, wie dieser Automat
definiert ist.
Der hat also jetzt etwas mehr Übergänge und Sie sehen, hier stehen
genau diese Übergänge in diesem Zustandsdiagramm, stehen alle
Übergänge, die in der Tafel definiert sind, hier eben grafisch
angedeutet, da sieht man genau, mit welchen Eingaben, weil zum
Beispiel hier von 3 mit M2 passiert keine Ausgabe und man bekommt den
Übertragszustand.
Und entsprechend sind die anderen Übergänge definiert.
Ich glaube, da kann ich weitermachen und das nächste wäre ein Beispiel
für einen Automaten aus der Rechnerarithmetik.
Der hat die Aufgabe, BIT-seriell zu addieren.
Also, erster Summand zum Beispiel 0101, zweiter Summand zum Beispiel
0011.
Ich schreibe die nochmal hier hin, 0101 und 0011.
Was heißt BIT-seriell addieren?
Das heißt, es sind die beiden Summanden A und B, definiert in diesem
Fall durch irgendeine Anzahl von BITs.
Das kennen Sie alles aus der Schule, 5.
oder 6.
Klasse, da lernen Sie binäre Zahlen kennen und da wissen Sie auch, wie
man die addiert und ähnliche Dinge.
Da brauche ich eigentlich gar nichts zu erzählen.
Es werden also die jeweiligen BITs addiert.
Also hier in dem Fall würden wir 1 und 1 addieren, dann kommt 0 raus,
wir haben einen Übertrag von 1.
Es werden 1 und 1 addiert, es kommt ein 0 raus, Übertrag von 1.
Die beiden werden addiert, es kommt 0 raus, Übertrag von 1 und das ist
das Ergebnis.
Also 1000 wäre in dem Fall das Ergebnis.
Genauso werden die hier eingegeben und BIT-seriell heißt eben wirklich
nacheinander von rechts nach links werden die BITs eingegeben.
In der Reihenfolge, wie wir das gerade eben gemacht haben.
Und was wir eben modellieren müssen ist, einerseits diese Addition der
BITs und den Übertrag.
Der Übertrag ist also etwas, was wir uns merken müssen von der
Addition an einer Position für die Addition an der nächsten Stelle.
Etwas merken heißt, unser Automat muss das in seinem Zustand
modellieren.
Das heißt, der Zustand wird der Übertrag sein, der gerade entweder 0
oder 1 sein kann.
Also wir müssen erzeugen unsere Sn bis S0, unsere Summe, die hier
ausgegeben wird.
Da wird also 1000 ausgegeben.
Und was hier steht, eine umgekehrte Reihenfolge.
Normalerweise, wenn wir ein Wort aufschreiben, gehen wir davon aus,
dass das linkeste Zeichen zuerst eingegeben wird.
Hier bei dem BIT-seriellen Addierer muss das rechteste Zeichen zuerst
eingegeben werden.
Das ist einfach hier anders als bei der sonstigen Darstellung.
Und welche Beziehungen bestehen denn jetzt zwischen den einzelnen
Symbolen?
Wir haben diesen Übertrag.
Und der Übertrag ist zu Anfang, nehmen wir an, dass wir einen Übertrag
0 zu Anfang haben.
Dann haben wir da auch einen Übertrag 0.
Und der nächste Übertrag, der gibt sich immer dann, wenn mindestens
zwei der beiden BITs, oder eigentlich drei BITs, nämlich AI, BI und
CI, wenn die eins sind.
Mindestens zwei von denen sollen eins sein.
Das ist so ausgedrückt, dass AI und BI eins sind oder AI und CI oder
BI und CI.
Mindestens zwei von denen sind eins.
Und die Summe von drei BITs in dem Fall, nämlich AI, BI und der
Übertrag CI, das ist gerade im Prinzip die Paritätsfunktion.
Oder das XOR dieser drei BITs, also AI, XOR, BI, XOR, CI.
Und dieses XOR ist das Exklusive.
Exklusive oder, sollten Sie auch kennen, also nur einer von den beiden
ist eins.
Wenn beide null sind oder beide eins sind, ist das Ergebnis null.
Nur wenn einer der beiden eins ist und der andere null, ist das
Ergebnis eins.
Wenn Sie drei Elemente haben, ist also bei drei Elementen der Wert
eins, wann immer Sie eine ungerade Zahl von Einsen haben.
Wenn also eine ungerade Zahl dieser AI, BI und CI eins sind, dann ist
das Ergebnis eins, ansonsten null.
Also wenn alle drei eins sind, kommt eine Eins raus.
Wenn nur einer von denen eins ist, kommt auch eine Eins raus.
Wenn zwei Einsen auftauchen oder gar keine Eins, ist das Ergebnis
null.
Das ist diese XOR-Funktion.
Und die müssen wir in den Addierer einbauen.
Wir werden später sehen, wie man das mit Schaltkreisen macht.
Hier wird nur die Funktion angegeben.
Also wir werden später hineinschauen in diesen schwarzen Kasten.
Hier gucken wir jetzt erstmal nur auf die Funktionalität, den
Übergang.
Und jetzt müssen wir den Automat richtig formulieren.
Wir haben also den Automaten anzugeben mit Eingabealphabet.
Zustandsalphabet habe ich jetzt Z genannt, schön mnemonisch.
Das S konnte ich nicht verwenden, weil das S bereits hier oben bei der
Summe steht.
Wir haben ein Ausgabealphabet A.
Wir haben ein Delta für die Übergangsfunktion, Gamma für die
Ausgabefunktion und ein Z, nur das Anfangszustand.
Was sind die Eingaben?
Die Eingaben dieser Bitserialen Addierers sind jeweils zwei Bits.
Hier 1,1 oder 0,1 und so weiter.
Das sind die beiden Bits.
Diese beiden Bits sind im Prinzip zwei Eingabeports, die wir hier
haben.
Das sind also 0,0, 0,1, 1,0 oder 1,1.
Diese beiden Bits werden hier aufgefasst als jeweils ein Eingabesymbol
unseres Alphabets.
Also das Alphabet, in dem Fall ist das die Menge E, hat vier Elemente,
nämlich 0,0, 0,1, 1,0, 1,1.
Jeweils als ein Symbol aufgefasst.
Die Zustandsmenge soll gerade jetzt den Übertrag symbolisieren, also 0
oder 1.
Der Anfangszustand Z0 ist 0, das steht hier.
C0 ist 0.
Und das Ausgabealphabet, naja, da kommen die einzelnen Summenbits
raus, das sind entweder Nullen oder Einsen.
Und jetzt müssen wir sagen, wie die Übergangsfunktion definiert wird.
Also Delta von Z, in irgendeinem Zustand, und geben jetzt irgendetwas
ein.
Die Eingaben bestehen jeweils aus zwei Bits.
Dann ist halt der Übergang definiert gerade als die Carry- oder die
Übertragsfunktion, A und B oder A und Z oder B und Z.
Und die Ausgabefunktion ist gerade das Summenbit, nämlich das XOR der
drei Elemente, die beiden Eingabekomponenten A und B, geXORed mit dem
Zustand Z.
Also genau das, was hier oben steht als Definition, was wir aus der
Arithmetik kennen, übertragen in die Übergänge eines Automaten.
Damit haben wir einen einfachen Automaten definiert, der
Bitseriellzahlen addieren kann.
Sehr praktische Anwendung von Automaten.
Wir werden später darauf zurückkommen und sehen, wie man einen solchen
Addierer tatsächlich aufbauen kann mit Schaltkreisen.
Das kommt etwas später, nachdem wir die ganzen formalen Modelle hier
bewältigt haben.
Das können wir auch natürlich als Diagramm aufmalen, in diesem Fall
sehr einfach.
Wir haben zwei Zustände, 0 und 1.
Der Zustand 0 ist hier auch unser Anfangszustand.
Und dann gibt es diese ganzen Übergänge jeweils.
Sie sehen, hier haben wir drei Möglichkeiten, im Zustand zu bleiben.
Nämlich bei 00, 10 oder 01 haben wir keinen Übertrag.
Nur wenn wir 11 eingeben, im Zustand 0, dann wird ein Übertrag
erzeugt.
Und dann kommen wir in den Zustand 1 und wir geben eine 0 aus.
Wenn wir im Zustand 1 sind, bleiben wir drin, wenn wir 10, 01 oder 11
eingeben, weil wir in jedem dieser Fälle einen Übertrag erzeugen.
Und wir geben aus, entweder eine 0 oder eine 1, weil bei 11 als
Eingabe und 1 als Übertrag wird natürlich eine 1 ausgegeben.
Und wenn wir im Zustand 1 sind und es werden zwei Nullen eingegeben,
dann wird eine 1 ausgegeben, das ist nämlich hier dieser Übertrag und
wir gehen in den Zustand 0.
Das ist das, was wir hier gerade formuliert haben, die Funktion, hier
als Diagramm nochmal aufgemalt.
Jetzt kennen Sie also den Automaten vollständig.
Und wir kommen zu einem noch komplizierteren Automaten, nämlich einem
sehr einfachen PC.
Nur, dass Sie mal sehen, letztes Mal kam die Frage, ist denn ein
Rechner ein Automat?
Jeder Rechner, so wie Sie ihn vor sich stehen haben, ist ein Automat,
sofern er nicht mit dem Netz verbunden ist.
In dem Augenblick, wo er mit dem Netz verbunden ist, kommt da ein
bisschen mehr.
Warum?
Weil die Menge der Zustände eventuell größer wird.
Sie können auf andere Dinge zurückgreifen und können dann eventuell
noch mehr abspeichern.
Aber intern ist eigentlich so, wenn Sie, nehmen wir das zurück, das
Netz würde nur noch mehr Eingaben Ihnen geben, würde aber nicht die
interne Speichermöglichkeiten verändern.
Also insofern können wir das hierbei belassen.
Was habe ich hier modelliert?
Ich habe einen ganz einfachen PC genommen, einen ganz einfachen
Prozessor, Intel P6, uralter Prozessor.
Ganz einfacher.
Das können Sie nachlesen, die Spezifikation hier auf dieser Webseite.
Der hat 128 Mebibyte.
Wer von Ihnen weiß, was ein Mebibyte ist?
Niemand?
Dann schauen wir doch mal auf die nächste Folie.
Da ist nämlich ein kleiner Einschub zu Größenordnungen.
Was sind Größenordnungen?
Diese hier, die ich hier jetzt aufliste, die kennen Sie alle.
Digitale Größenordnungen sind Ihnen wohl bekannt.
Kilo, Mega, Giga, Tera, Peta, Exa.
Wir könnten es nach unten auch weiter fortsetzen für die negativen
Potenzen.
Hier haben wir einfach nur die positiven genommen.
Und das kennen Sie alles.
Megabyte, Gigabyte, Terabyte, Petabyte und so weiter.
Die üblichen Größenordnungen.
Und das sind alles Zehnerpotenzen.
Also Kilo, 10 hoch 3 oder 2 hoch 10.
Das ist doch gar nicht das Gleiche.
2 hoch 10 ist 1024.
Also den Ingenieur möchte ich sehen, der zufrieden ist, wenn er sagt
1000 und jemand bietet ihm 1024 an.
Das ist nicht das Gleiche.
Und wenn Sie das jetzt etwas anders noch anschauen, die anderen
Zweierpotenzen, also 2 hoch 20, sagt man, na ja, das ist ja so ähnlich
wie 10 hoch 6.
Oder 2 hoch 30, so ähnlich wie 10 hoch 9.
Ist doch fast das Gleiche.
Ist leider nicht der Fall.
Das geht schon bei 10 hoch 3 los mit 1024.
Entsprechend, wenn Sie 1024 mit 1024 multiplizieren, kommt
entsprechend nicht eine Million raus, sondern ein etwas größerer Wert.
Und wenn Sie noch weiter gehen auf Giga oder Tera, da haben Sie also
immer größere Diskrepanzen.
Das ist für keine technische Spezifikation vernünftig, wenn man Mega,
Giga oder Tera oder sowas sagt und Zweierpotenzen meint.
Das geht gar nicht.
Das Problem ist, die Informatiker oder diejenigen, die die Rechner
bauen, die verstehen normalerweise, na ja, das sind doch alles
Zweierpotenzen.
Die Nachrichtentechniker, die Speicherbauer und so weiter, das sind
übliche, typische Techniker, die verstehen nur Zehnerpotenzen.
Und Sie sagen, ich möchte gerne 2 hoch 30 Speicherplatz haben, 2 hoch
30 Byte Speicherplatz und die liefern Ihnen leider nur 10 hoch 9.
Da fehlt einiges.
Und jetzt stellen Sie vor, Sie bauen irgendetwas in irgendeiner
anderen Art, Sie haben Bandbreiten, Sie haben so und so viel Megabit
pro Sekunde oder Gigabit pro Sekunde Übertragungsrate, brauchen Sie
für irgendwelche technischen Kommunikationen.
Und es liefern Ihnen die Nachrichtentechniker aber etwas, was in
Zehnerpotenzen gemacht ist.
Das passt nicht zusammen.
Und deswegen sagt man, man muss es genau spezifizieren, muss also
unterscheiden, Mega und Megabinary.
Megabinary abgekürzt als Maybe oder, da steht es, Maybebyte, Gibibyte,
Gigabinarybyte.
So ist es formal richtig.
Und das Ganze ist also hier nachzulesen und ich will da mal kurz
raufgehen, weil das zum Illustrieren ganz gut ist, dass das National
Institute of Standards hier in den USA, die haben das alles
festgelegt, natürlich international ist das alles, das International
System of Units, internationale Vereinbarung, und die sagt eben für
Binary Multiples, also für binäre Zweierpotenzen, da muss man diese
Bezeichnungen verwenden, Kibi, Mibi und so weiter bis Exbi.
Und wenn man sich anschaut, wie die sich unterschiedlich darstellen,
ich mach das mal ein bisschen größer,
da können Sie ein bisschen größer sehen, da sehen Sie die
Unterschiede.
Also, bei Kilobyte ist es noch nicht ganz so schlimm, da ist es gerade
der Unterschied 24 Bit, bei Megabyte und Mibyte ist der Unterschied
immerhin 48.000, bei Kibibyte und Gigabyte ist der Unterschied 73
Millionen Byte.
Also ein beträchtlicher Unterschied.
Also, merken Sie sich das, das sind die Größenordnungen, mit denen wir
es zu tun haben.
In diesem Fall sind es also dann die Binären, auf die wir aufpassen
müssen.
Gehen wir wieder zurück auf die vorherige Darstellung.
Und hier ist also, lesen Sie sich das durch, der historische Kontext,
was alles passiert ist, was sich alles getan hat, zum Beispiel, nur
ganz kurz, diese eine Darstellung,
in den 1,44 Megabyte Disketten, da wurde noch was seltsameres gemacht,
1,44 Megabyte, da hat man 1024 mal 1000 Bytes genommen, völlig
verquer, Mischung von Kilo und Kibi, völlig daneben.
Also es gibt einiges, was manchmal etwas seltsam ist, man muss wissen,
dass man darauf aufpassen muss.
Und warum zeigt Windows dann Megabyte und Gigabyte an?
Da müssen Sie Windows fragen.
Die Leute sind halt einfach nachlässig, und wenn es nicht so darauf
ankommt, schreibt man halt Megabyte und Gigabyte, und dann müssen Sie
davon ausgehen, dass tatsächlich binäre Potenz, Quatsch, also dezimale
Potenz, da sind es tatsächlich nur 10 hoch 6 oder 10 hoch 9 oder 10
hoch 12.
Und wenn Sie etwas anderes haben wollen, müssen Sie halt die binären
Größenordnungen nehmen.
Leider verwenden nicht alle die binären Größenordnungen.
Deswegen muss man immer genau gucken, was meinen die eigentlich
wirklich.
Sie dürfen nicht darauf vertrauen, dass die tatsächlich Megabyte
meinen, sondern vielleicht meinen sie Maybebyte.
Also, nur dass Sie wissen, da gibt es Unterschiede.
Da gibt es noch eine Frage.
Das war diese Frage, die ich natürlich beantwortet habe.
Damit gehen wir zurück auf die Vorlesung.
Und ich habe noch eine Frage.
Wieso ist die immer noch nicht...
Ich habe doch gesagt, die ist beantwortet.
Das kann es doch gar nicht geben.
Ist das keine irreführende Werbung, wenn ich eine Festplatte mit 1
Terabyte Speicherplatz kaufe und wegen dieser Abweichung statt dem
geworbenen Speicherplatz nur 930 Gigabyte bekomme?
Das ist richtig.
Ist halt leider so.
Der Anbieter wird Ihnen sagen, das weiß doch jeder, dass das so ist.
Aber das ist genau das Problem, was in diesem historischen Kontext
angesprochen wird.
Ist eigentlich nicht in Ordnung.
Man sollte sich beschweren.
Sie können sich beschweren und sagen, da steht Terabyte, damit ich
auch genau das habe.
Aber hier ist eben 1 Terabyte Speicherplatz.
Also die 930 Gigabyte, das sind dann aber Gibibyte.
Also diese Frage ist schon in sich eigentlich nicht in Ordnung.
Weil Sie dann hätten schreiben müssen, gerade eben hier, GI -Byte.
Also passen Sie auf, wie Sie das formulieren.
Das dazu.
Und damit kommen wir...
Das waren die Größenordnungen.
Wir müssen nochmal zurückgehen auf die Seite 11.
Da waren wir noch nicht fertig.
Wir waren beim Rechner.
Der also jetzt hier diese 128 Mibyte hat.
Und 40 Register zu je 32 Bit.
Interne Register.
Die hat er im Inneren.
Also die schwarze Kiste wird immer durchlässiger.
Und wenn der jetzt 40 Register hat mit je 32 Bit, dann heißt das, er
kann in diesen 40 Registern einiges speichern.
Er kann in seinen 128 Mibyte insgesamt einiges speichern.
Byte sind jeweils 8 Bit.
Und das heißt, da wir in jeder Speicherzelle zwei verschiedene Werte
speichern können, also wenn Sie hier irgen...
Das wollte ich gar nicht.
Völlig verkehrt.
Beibehalten.
Und wieder Bildschirmpräsentation ab aktueller Folie.
Und ich wollte auf diese Taste den Stift einschalten.
Also.
Hier sind wir bei diesen Zuständen.
Wir haben, wenn wir ein Zustand haben, dann können wir, also eine
Speicherzelle, dann können wir zwei Zustände speichern.
Haben wir zwei Speicherzellen, können wir in jedem 0 oder 1 speichern.
Dann haben wir 2 hoch 2 gleich 4.
Haben wir 3 Speicherzellen, haben wir 2 hoch 3 gleich 8.
Also die Anzahl der Speicherzellen als Potenz für diese Zweierpotenz.
Die Anzahl der Zustände ist also 2 hoch 128.
Das sind diese 128 Mibyte.
Heißt 1024 x 1024 Byte heißt 8 Bit.
Das heißt, das ist hier die Anzahl der Speicherzellen oben im
Exponenten.
Und 2 hoch dieser Exponent mal weitere Speichermöglichkeiten.
Nämlich in diesen 40 Registern.
40 weitere Register mit je 32 Bit.
40 x 32 macht insgesamt diese Zahl 2 hoch sehr große Zahl mal 2 hoch
1280 Bit Kombination.
Wenn Sie jetzt eine Aussage machen wollen darüber, dass Ihr Rechner in
jedem Zustand fehlerfrei funktioniert.
Müssten Sie mal kurz alle diese Zustände durchprobieren und sehen, ob
der tatsächlich in jedem Zustand das Richtige tut.
Das würde ziemlich lange dauern.
Und das können Sie gar nicht machen.
Das heißt, um etwas sagen zu können darüber, was ein Automat
eigentlich alles tut, muss man sich überlegen, wie kann ich sinnvoll
solche Aussagen machen.
Bei einem PC ist die Anzahl der Zustände so gigantisch, wenn Sie dazu
eine Zustandstafel aufbauen wollten.
Sie haben gar nicht so viel Platz.
Diese Zustandstafel tatsächlich irgendwo aufzuschreiben.
Also das zeigt nur, die Zustandsmenge ist hier sehr sehr sehr sehr
sehr sehr groß.
Aber es ist ein ganz kleiner PC.
Ganz kleiner Prozessor.
Und ist aber im Wesentlichen ein endlicher Automat.
Und wodurch könnte ich die Leistungsfähigkeit vergrößern?
Dadurch, dass ich ein bisschen Speicher zufüge, mehr Register
dazufüge.
Ich erhöhe meinen Hauptspeicher.
Ich baue eine größere Festplatte ein.
Oder ähnliche Dinge.
Oder ich stecke einen Speicherstick rein.
Auf die Art und Weise erweitern wir die Speicherkapazität.
Oder ich habe einen ganzen Sack voll Speichersticks und kann die alle
der Reihe nach reinstecken.
Und kann auf die Informationen reagieren.
Das sind Möglichkeiten, den etwas leistungsfähiger zu machen.
Aber es bleibt in jedem Augenblick immer ein endlicher Automat,
bezogen auf die Anzahl der Speichermöglichkeiten, die er hat.
Anzahl der Zellen, in denen Informationen gespeichert werden können.
Das ist also in dem Sinne jeder Rechner ein endlicher Automat.
Da wir aber jeweils noch Speicher hinzufügen können, im Prinzip
beliebig viel, ist er dann auch wieder kein endlicher Automat.
Braucht man das überhaupt?
Reicht es?
Der ist ja schon gigantisch groß.
Eigentlich müsste das doch reichen, wenn man so ein Automat hat.
Und das werden wir nochmal genauer anschauen.
Also die Automaten hier wurden alle jetzt etwas größer.
Der hier ist gigantisch groß.
Vom Prinzip her ändert sich aber nichts daran, wie wir ihn
modellieren.
Zunächst mal.
Wir modellieren ihn so als Milliautomat mit Zustandsdiagramm oder
Zustandstafel.
Und wir können dann Aussagen über die Eigenschaften von endlichen
Automaten machen.
Und das sind die gleichen Aussagen, unabhängig davon, ob das eine so
gigantische Anzahl von Zuständen ist oder ob das eine kleine Zahl von
Zuständen ist.
Die prinzipiellen Aussagen gelten für alle diese Automaten.
Deswegen ist es so wichtig, ein formales Modell zu haben, mit dem man
diese Art von Aussagen machen kann.
Das war der Einschub zu den Größenordnungen.
Und jetzt kommen wir zu den etwas anderen Automaten, zu den
Murautomaten.
Ein Murautomat, ich hatte gesagt Milli und Mur, Mur war etwas anders,
insofern, dass der Murautomat die Ausgabe nicht abhängig von Zustand
und Eingabe macht, sondern nur abhängig von dem Zustand.
Viel einfacher.
Ich brauche die Eingabe nicht anzuschauen, ich schaue nur den Zustand
an.
Und insofern ist das eigentlich ein kleiner Unterschied.
Das heißt, wir müssen die Darstellung etwas verändern bei dem
Zustandsdiagramm.
Da malen wir jetzt in diesen Knoten mit der Bezeichnung SI auch die
Ausgabe rein für diesen Zustand, das ist in dem Fall AQ.
EK ist eine Eingabe, dann gehen wir einen neuen Zustand über und in
dem Zustand können wir dann eine Ausgabe machen.
Aber die Ausgabe ist abhängig von dem Zustand SJ.
Wenn also Delta von SI und EK gleich SJ ist, dann ist also
entsprechend das AH in dem Fall Gamma von SJ.
Das Interessante ist, ich kann zu jedem Milliautomaten einen
äquivalenten Murautomaten angeben, der also die gleiche Funktionalität
hat.
Und umgekehrt.
Bis auf die Eingabe des leeren Wortes, da sind die unterschiedlich.
Also der Milliautomat kann mit dem leeren Wort, da bleibt er in dem
Zustand, kann nichts ausgeben, der Murautomat gibt die Ausgabe für den
Anfangszustand oder für den aktuellen Zustand an.
Die Anzahl der Zustände kann sich sehr deutlich unterscheiden, aber
man kann es in beide Richtungen äquivalent machen.
Wozu dann diese Unterschiede?
Das Interessante ist, das zeitliche Verhalten der Automaten ist leicht
unterschiedlich.
Also die Äquivalenz vorher heißt nur, die Funktionalität ist die
gleiche, aber das zeitliche Verhalten des Automaten, die unterscheidet
sich durchaus.
Weil nämlich beim Murautomaten eine Ausgabe erfolgt im aktuellen
Zustand, jetzt passiert etwas, es kommt eine Eingabe, der Zustand wird
geändert und erst dann, wenn der neue Zustand angenommen wurde, gibt
es eine neue Ausgabe.
Wir reden normalerweise auch davon, dass wir sogenannte Takte haben,
das heißt, es gibt ein festes Zeitintervall, so ein festes
Zeitintervall, in dem der Zustandsübergang stattfindet und dann ist
der neue Zustand angenommen und dann kommt die Ausgabe für den
Zustand.
Das ist eine sehr wichtige Eigenschaft bei sogenannten Pipeline
-Strukturen.
Was sind Pipeline-Strukturen?
Das sind zum Beispiel mehrere Automaten, die man hintereinander
schaltet.
So, jetzt machen wir hier jeweils ein Pfeil dazwischen und sagen, aha,
wir haben eine Pipeline-Struktur.
Ihre Rechner, die Sie verwenden, haben alle große Pipelines in sich.
Also eine Struktur, die Sie überall finden, in ganz vielen
Situationen, werden wir später kennenlernen, warum.
Das Interessante ist, wenn das ein Milliautomat ist, wenn jeder
einzelne Automat, das ist also unser Automat A1, A2 und so weiter,
wenn das Milliautomaten sind und hier vorne kommt eine Eingabe rein,
dann würde der in diesem, in dem Zustandsübergang, das hier ist eine,
die Zeit für den Zustandswechsel, beim Übergang würde der bereits eine
Ausgabe produzieren, die hier als kleine Ausgabe A1 sichtbar wäre.
Diese Ausgabe würde beim Automaten A2 einen Zustandsübergang bewirken,
der wieder zu einer Ausgabe führt, eine Ausgabe A2, der würde hier,
dieser Automat A3, entsprechend würde angestoßen werden.
Und bevor dieser Takt tatsächlich zu Ende ist und der Automat hier der
erste seinen neuen Folgezustand angenommen hat, haben wir hier am Ende
schon eine Ausgabe, ich nenne die mal AN, die letzte Ausgabe, die in
diesem Zeitraum, die wir für den Zustandsübergang hier brauchen, auch
alle anderen angestoßen hat, sodass wir hier eine Ausgabe bekommen.
Das wollen wir aber nicht.
Wir wollen eigentlich folgendes erreichen, dass in einem bestimmten
Takt, wir hier eine Ausgabe haben, da auch, da auch, da auch, da auch,
und diese Ausgabe soll nur abhängen von dem jeweiligen Zustand.
Das ist die Eingabe für den nächsten Automaten, also das A1 ist die
Eingabe, hier haben wir eine Eingabe E1 für den Automaten A1, der wird
angestoßen, seinen Zustand zu ändern, geht in den nächsten Zustand
über und gleichzeitig gehen alle diese Automaten entsprechend der
aktuellen Eingabe in einen neuen Zustand über und dann sind die neuen
Zustände angenommen und wir bekommen hier auf den Ausgaben jeweils
Änderungen.
Dann haben wir wirklich ein geordnetes Verändern der einzelnen
Ausgaben, die jeweils nur abhängen von der aktuellen Eingabe für den
einzelnen Automaten.
Das ist eine vernünftige Pipeline, wenn es ein Mur-Automat ist, beim
Mili -Automaten ist es keine vernünftige Pipeline.
Und dafür braucht man so eine Unterscheidung, wenn Sie also Pipeline
-Strukturen aufbauen wollen, müssen die Automaten, die Sie dort
modellieren, Mur-Automaten sein.
Das also nur als kurze Bemerkung, warum das so wichtig ist.
Hier nochmal ein Beispiel für eine Ampelsteuerung.
Hier sehen Sie ein Beispiel für einen Mur-Automaten.
Diese Ampelsteuerung ist vom Mur-Typ.
Woran sieht man das?
Wir haben hier Eingaben, das sind SL und SN, die Sensoren auf der
Straße für die Linksabbieger und für die Nord-Süd-Richtung.
Die sind hier angegeben, da und da und hier unten ist auch noch eine.
Und das Ganze kann ich ja auch, wenn ich will, kann ich das starten.
Habe ich Ihnen schon mal gezeigt, wie man das ablaufen lassen kann,
das erspare ich mir jetzt.
Und diese Eingaben, die gehen rein in ein Schaltwerk, das hier
angedeutet ist.
Und wir haben hier am Ende gewisse Ausgaben, die abhängig sind von
dem, was hier in diesen Elementen, die dort stehen, mit D und so
weiter, so komischen Symbolen.
Das sind einzelne Flipflops, Speicherregister, sogenannte D-Flipflops,
auch die werden Sie später kennenlernen und auch selbst damit
Schaltungen bauen können.
Das sind die Zustandskodierungen.
Und aus der aktuellen Zustandskodierung wird hier jeweils die
Bezeichnung des Zustands visualisiert.
In dem Fall Zustand 3, der hier angedeutet ist.
Wenn ich ganz kurz hier raufgehe, dann wird Sie nochmal ein schönes
Video sehen.
Hier also diese Darstellung.
Wenn das in Betrieb ist, dann haben diese Sensoren unterschiedliche
Effekte, die sich entsprechend mit Zustandsänderungen in dem Automaten
äußern.
Entsprechend der Schaltungslogik, die hier dargestellt ist, das sind
UND -Gatter und ODER-Gatter.
Sie können sich das angucken, können daraus schließen, wie man sowas
konkret baut.
Das will ich jetzt gar nicht weiter vertiefen.
Hier steht genau, wie das modelliert ist.
Wir haben die jeweiligen Ampeln also als dargestellt als Hauptstraße,
Linksabbieger und Nebenstraße.
Das Rot oder Grün ist hier gar nicht dargestellt.
Das ist die eigentliche Ausgabe, die wir tatsächlich machen wollen.
Diese Lichter hier für Z1, Z2, Z0, 012 genau, die sind einfach nur
dargestellt, um zu zeigen, ob da 0 oder 1 gespeichert ist.
Die rote und grüne Ampel haben wir nicht dargestellt.
Die Sensoren, hatte ich gesagt, das sind die Eingaben.
Und dann haben wir hier die Ausgaben, die in diesem Bild nicht zu
sehen ist.
Die sieht man nur hier, da sieht man sie natürlich, das sind unsere
Ampeln.
Aber die sieht man nicht in dem Schaltbild.
Und dann haben wir hier die Reihenfolgen, wie die ganzen schalten
können, das ist entsprechend durch die Schaltungslogen oder über die
Übergangsfunktionen dargestellt.
Das ist also der Automat für eine Ampelschaltung und entsprechend kann
man den auch modellieren.
Und jetzt gehen wir einen Schritt weiter und vereinfachen das Ganze.
Ich halte Ihnen ja keine Vorlesung über Spezifikationen von
technischen Bauelementen, sondern es geht uns um Sprachen.
Aber eigentlich wollen wir wissen, wie kann ich Sprachen beschreiben.
Da hatte ich schon gesagt, die Automaten brauchen wir für die
analysierende Methode.
Und diese Methode soll ja für ein Wort, das uns gegeben wird, angeben,
ist dieses Wort ein Element der Sprache oder nicht.
Deswegen analysierend.
Ich analysiere das Wort, das mir eingegeben wird.
Mein Wort W.
Schau an, wie sind hier die einzelnen Zeichen gebaut, entspricht das
irgendeiner Vorschrift und der Automat liest das von links nach rechts
durch und wenn er am Ende angekommen ist, soll er sagen, das Wort ist
in der Sprache oder nicht.
Das wäre ein Akzeptor, der in der Lage ist, festzustellen, ob ein Wort
W akzeptiert werden kann oder nicht.
Wir haben also in dem Fall kein Ausgabealphabet, keine
Ausgabefunktion, abgesehen davon, dass wir feststellen wollen, ob ein
Wort akzeptiert wird oder nicht.
Also diese Ausgabe muss er machen.
Und dafür haben wir eine Menge von Endzuständen.
Wir können also feststellen, ob ein Automat ein Endzustand ist oder
nicht.
Wenn es ein Endzustand ist, sagen wir, aha, das Wort ist akzeptiert.
Wenn es kein Endzustand ist, sagen wir, das Wort wurde nicht
akzeptiert.
Der ist also etwas einfacher zu modellieren.
Wir haben nur noch ein Eingabeband.
Wir haben einen Lesekopf und wir haben die internen Zustände wie
vorher und entsprechende Übergangsfunktionen, also wir brauchen die
Ausgabemenge nicht mehr, wir brauchen nur die
Zustandsübergangsfunktion, brauchen aber dazu noch eine Menge F, die
Teilmenge der Zustandsmenge, das sind die finalen Zustände, deswegen
F, das sind die Endzustände.
Also F für final, haben nicht E genommen für Endzustände, E haben wir
schon für die Eingaben genommen.
Deswegen F für final oder final states.
Okay.
Hier die Arbeitsweise genau wie vorher, wir gehen erstmal entsprechend
in den Anfangszustand, wir gehen wie üblich davon aus, dass das
bereits alles initialisiert ist und dann laufen wir einfach das Band
von links nach rechts hier durch, bzw.
schieben das Band an dem Lesekopf vorbei und wenn wir das Wort ganz
gelesen haben, gucken wir rein in den Automaten, Endzustand oder nicht
und sagen akzeptiert oder nicht akzeptiert.
Ganz einfach.
Dargestellt wieder in der Zustandstafel, wir brauchen also in diesen
Feldern hier uns um Ausgaben nicht mehr zu kümmern, wir geben nur den
nächsten Zustand an und da haben wir das alles gesagt und bei dem
Zustandsdiagramm müssen wir einerseits den Anfangszustand geeignet
darstellen, also einen Kringel mit dem S0 drin oder irgendwas anderem,
was Sie als Anfangszustand bezeichnen und dann ein Pfeil, der dort
reingeht und von nirgendwo kommt, also der Anfangszustand, der
Übergang, einfach ein Pfeil zwischen den beiden Zuständen und
dazwischen steht, welche Eingabe diesen Übergang bewirkt und wir
müssen Endzustände darstellen können, das deuten wir dadurch an, dass
wir hier einen Doppelkringel machen, um den Zustands und die
Zustandsbezeichnung und es geht manchmal so, dass wir mehrere
Übergangsmöglichkeiten haben, EI und EJ und mit diesen beiden Eingaben
würden wir von SJ nach SK übergehen.
Das ist also die Definition der Automaten und jetzt müssen wir uns
überlegen, wir wollen ja eigentlich nicht nur für den einzelnen
Zeichen reden, wir hatten schon bei den Miliautomaten gesagt, wir
erweitern die Übergangsfunktion auf Wörter.
Wir wollen also wissen, was passiert, wenn ich in einem Zustand bin
und ein Wort noch gelesen werden muss.
Also stellen Sie sich vor, Sie sind in irgendeinem Zustand und hier
steht noch etwas auf dem Band, was noch gelesen werden muss.
Dann ist es völlig egal, was links davon gestanden hat, das hat dazu
geführt, dass Sie in dem Zustand S sind.
Um in den Endzustand oder Nicht-Endzustand zu kommen, brauchen Sie nur
zu wissen, was steht an aktueller Position, wo der Zustand ist.
Also eine Konfiguration des endlichen Automaten, und Sie werden solche
Konfigurationsdefinitionen noch öfter sehen, die Konfiguration muss
alles das enthalten, was ich brauche, um das weitere Verhalten dieses
Automaten richtig ableiten zu können.
Ich gehe davon aus, dass ich die Zustandsübergangsfunktion kenne, also
das Delta, die Zustandstafel oder das Zustandsdiagramm und dann muss
ich wissen, was ist der aktuelle Zustand und das Restwort auf dem
Band.
Und dann muss ich sehen, wie ich von einer Konfiguration in die
nächste übergehen kann.
Das heißt, wir brauchen eine Übergangsrelation auf der Menge aller
Paare von Zustand und Wort, das sind also genau die Konfigurationen.
Und für jeden Zustand, für jedes Wort und für jedes Eingabezeichen,
müssen wir also sagen, wenn wir in einem Zustand sind und das Zeichen,
das aktuelle Zeichen hier E auf diesem Feld ist dort, dann muss der
Automat den Übergang machen, Delta von S, E, muss also bei Eingabe von
E im Zustand S auf den Folgezustand übergehen und anschließend die
nächsten Zeichen bearbeiten.
Ganz einfache Übergangsfunktion.
Und natürlich kann man das Ganze auch dann noch erweitern, kann das
reflexiv transitiv erweitern.
Reflexiv heißt, wenn ich nichts eingebe, bleibe ich in dem Zustand und
es passiert gar nichts weiter.
Also jede Konfiguration ist mit sich selbst in Relation.
Und ansonsten transitiv ist auch klar, wie vorher schon bei den
anderen Beschreibungen.
Und das heißt also, ich habe jetzt für jeden Zustand, wenn ich dort
zwei Wörter W1 und W2 nacheinander drauf stehen habe, ein solches
Band, also wenn ich hier ein langes Eingabewort habe, hier habe ich W1
stehen, da W2.
Wenn ich das abarbeite, dann kann ich natürlich erst mal dieses Wort
hier abarbeiten, bin dann in einem Zustand, Delta-Stern von S, W1 und
dann mache ich mit W2 weiter.
Also egal, wie ich das aufteile, das sind hier diese Beziehungen
zwischen den Konfigurationen.
Und jetzt kann ich die Sprache des Automaten definieren auf zwei
unterschiedliche Art und Weise.
Ich kann zunächst mal sagen, wann ein Wort akzeptiert wird, das ist
klar.
Wenn ich vom Anfangszustand bei Eingabe des Wortes in einen Endzustand
komme und ich kann es auch so ausdrücken, also dass ich dann die
Menge, die Sprache insgesamt darstelle, also alle akzeptierten Wörter,
das sind alle Wörter über dem Eingabealphabet, die vom Automaten
akzeptiert werden, die also in einen Endzustand führen, oder über
Konfigurationen ausgedrückt, die anfangend mit der Startkonfiguration
S0, W über diese Übergangsrelation in einen Zustand führen, bei dem
rechts oder ab der aktuellen Position auf dem Eingabeband nichts mehr
steht.
Ich habe das Wort vollständig abgearbeitet, das steht jetzt links vom
Eingabekopf und ich bin im Endzustand.
Das ist also eine äquivalente Definition, entweder über
Konfigurationsübergänge definiert oder über diese einfachen Übergänge
entsprechend diesem Delta.
Eigentlich müsste hier noch ein Stern dran stehen, dann wäre es völlig
korrekt.
Okay, das ist also ganz einfach jetzt die Übergangsfunktion eines
endlichen Automaten und solche Automaten ohne Ausgabe nennen wir auch
Akzeptoren, weil die uns eben Auskunft geben, ob Wörter akzeptiert
werden oder nicht.
Jetzt gebe ich Ihnen dazu noch ein Beispiel, nämlich dieses hier, ein
ganz einfaches Beispiel.
Wir haben in diesem Fall drei Zustände.
Hier offensichtlich der Anfangszustand S0.
Wir haben gewisse Übergänge, schauen wir uns mal an, eine ganz
einfache Übergangstafel.
Was können denn hier für Wörter akzeptiert werden?
Der Endzustand ist der Zustand S2.
Wie komme ich in den Endzustand?
Nur über diese eine Kante mit B.
Aus dem Zustand S1.
Wie kann ich in den Zustand S1 gekommen sein?
Nur von dem S0 mit einem B.
Das heißt, wenn ich zwei Bs nacheinander gehabt habe, komme ich in den
Endzustand S2.
Und danach kann ich beliebig viele Bs schreiben, bleibe immer noch in
dem S2.
Dann muss ich mit einem A, würde ich wieder auf S0 gehen, dann würde
ich hier rüber laufen.
Und dann kann ich erst wieder in einen Endzustand kommen, wenn ich
zwei Bs gelesen habe.
Mit einem A würde ich nämlich zurück nach S0 kommen von S1.
Das heißt, wenn wir uns jetzt die Konfigurationsübergänge anschauen,
S0 mit diesem Wort hier, ABBABB, würde zunächst mal das A abarbeiten.
Ich bleibe in S0.
Habe als Restwort noch BBABB stehen.
Mit einem B komme ich in S1.
Ich habe noch BABB stehen.
Mit dem B komme ich in S2.
Habe noch ABBB zu verarbeiten.
Mit dem A komme ich in S0.
Habe noch BB zu verarbeiten.
Und mit B und B komme ich in die Endkonfiguration S2 und Lambda.
Es ist nichts mehr auf dem Band.
Das heißt, das Wort ist akzeptiert.
Wenn ich mir das Wort BABA anschaue, mit B komme ich von S0 nach S1.
Dann habe ich noch ABA.
Ich gehe zurück nach S0.
Habe noch BA stehen.
Gehe mit B nach S1.
Habe noch A draufstehen.
Gehe zurück nach S0.
Habe nichts mehr zu lesen.
Bin aber nicht im Endzustand.
Das Wort wird nicht akzeptiert.
Also das ist relativ einfach.
BABA gehört nicht zur Sprache des Automaten.
Sehr einfach.
Und das heißt, hier sind es genau die Wörter, die auf zwei Bs kommen
zum Endzustand.
Alle anderen führen nicht dahin.
Und damit habe ich sofort festgestellt, was das für eine Sprache ist.
Noch ein Beispiel.
Zwei Zustände.
S0 und S1.
Mit 0 bleiben wir in S0.
Mit 1 gehen wir nach S1.
Mit 0 bleiben wir in S1.
Mit 1 gehen wir zurück.
Das heißt, in S1 kommen wir mit einer 1.
Und dann kommen wir erst wieder nach S1 zurück, wenn wir zwei Einsen
gelesen haben.
Das heißt, entweder mit einer 1, mit drei Einsen, mit fünf Einsen oder
sieben Einsen kommen wir jeweils nach S1.
Danach können beliebig viele Nullen eingegeben werden.
Und das heißt, das ist unser ganz einfacher Automat, der im Prinzip
hier kurz dargestellt, das kann ich jetzt sehr schnell ausfüllen, das
sind genau die Wörter, die eine ungerade Anzahl von Einsen haben.
Gibt es eine kurze Frage?
Was bedeutet Konfiguration A?
Wo habe ich hier eine Konfiguration A?
Das muss ich auf eine Folie davor beziehen.
Das muss ich erstmal wieder zurück.
Ah, das A hier unten.
Das A steht für den Automaten.
Ja, ich habe eine Konfiguration, das ist die Übergangsfunktion dieses
Automaten A.
Also, das ist die Konfiguration.
In diesem Automaten A habe ich diesen Übergang auf eine nächste
Konfiguration.
Entsprechend dieser Zustandsübergangsfunktion.
Ich nehme an, dass das gemeint war.
Ganz kurz nochmal zurück, die habe ich also beantwortet.
jetzt wollte ich ganz kurz mal eine andere Frage, jetzt mal Ihnen eine
Frage stellen.
Und zwar, damit Sie mal ein bisschen was anderes tun.
Was war das dann?
Das hier, richtig.
Welche Eigenschaften interessieren uns bei formalen Sprachen?
Schönheit, Ausdrucksfähigkeit, Effizienz, Anzahl der Programme.
Was interessiert uns?
Diese vier Möglichkeiten.
Sie dürfen also beliebig antworten.
Wir werden dann sehen, was dabei rauskommt.
Ich kann ja mal...
Achso, ich muss die Frage erst mal Ihnen erst mal bereitstellen.
Wenn ich die nicht bereitstelle, kann gar nichts passieren.
Jetzt können Sie die Frage abrufen.
Und dann kann ich die Ergebnisse zeigen.
Noch passiert hier gar nichts.
Einer sagt Effizienz, einer sagt Ausdrucksfähigkeit.
Naja.
War ja auch sehr einfach.
Genau.
Entsprechend.
Also es ist nicht nur eine...
Hier steht ja auch Multiple Choice, also mehrere Möglichkeiten hier.
Richtig.
Es sagen sogar Leute, auch Schönheit und Anzahl der Programme kommt es
auch an.
Naja.
Bei Programmiersprachen...
Also ganz falsch ist es nicht.
Bei Programmiersprachen gibt es durchaus noch weitere Dinge zu
interessieren.
Nämlich, wie gut man eine Sprache lesen kann.
Das wäre Schönheit.
Also da ist Java oder C sind hässliche Sprachen.
Die kann man nämlich nicht lesen, als jemand, der dann nicht das genau
kennt.
Eine Sprache wie Kobol oder in gewissem Maße auch Algol.
Das sind Sprachen, die kann man hervorragend lesen.
Auch wenn man die Sprache gar nicht kennt.
Man liest und sieht sofort, was gemeint ist.
Bei C und Java sind sie völlig verloren.
Da muss man sehen, muss man erstmal einiges lernen, um zu wissen, was
daran eigentlich damit eigentlich gemeint ist.
Also das sei jetzt mal zu dieser Frage genug.
Eine kurze weitere Frage.
Das ist ein bisschen anders.
Achso.
Erstmal Closed Question.
Und jetzt sage ich diese hier.
Die nächste Frage können wir abrufen.
Wann ist eine Regel U nach V Sie wissen, U nach V, links steht U,
rechts steht V, einer kontextsensitiven
Grammatik nicht kontextfrei.
Habe ich letztes Mal alles erzählt.
U, also die linke Seite, enthält ein Terminalzeichen oder zweitens, U
besteht aus einem einzigen Nicht-Terminal Zeichen.
Drittens, V ist länger als U.
Viertens, U enthält mehr als ein Zeichen.
Also V war, die rechte Seite ist länger als die linke Seite.
Das vierte ist, U enthält mehr als ein Zeichen.
Und die Frage ist, wann ist die Regel nicht kontextfrei.
Schauen wir mal, was Sie meinen.
Nicht kontextfrei.
Interessant.
Also
interessant.
Warte mal einen Augenblick.
Da kann ja mal jemand, der auf zwei gegangen ist, sagen, was daran
falsch ist, wenn auf der linken Seite nur ein Nicht-Terminalzeichen
steht.
Was ist daran falsch?
Links steht nur ein Nicht-Terminalzeichen.
Die Mehrheit, die meisten sagen, das ist so richtig, da kommt eine
Frage.
Die kann ich aber jetzt nicht abrufen, weil ich hier in diesem Detail
drin bin.
Mal gucken.
Was ist kontextfrei?
Schauen Sie nach, was ich Ihnen voriges Mal erzählt habe.
Also.
Wie beantworte ich die?
Also jetzt kurzer Einschub.
Ich mach mal kurz hier wieder meinen Stift.
Also so eine Regel, kurzer Einschub, a auf b, c, die ist kontextfrei.
Aber a auf c, die ist nicht kontextfrei.
Weil ich hier das a nur im Kontext klein a durch c ersetzen darf.
Das ist kontextsensitiv.
Hier habe ich links nur ein Nicht-Terminalzeichen.
Das ist kontextfrei.
Das ist kein Kontext angegeben.
Deswegen kontextfrei.
Also zurück zu unserem Wo ist denn jetzt?
Wo sind denn jetzt?
Achso, da muss ich nochmal hin.
Show results, genau.
Also die größte Zahl hat leider völlig daneben getippt.
Wenn u aus einem einzigen Nicht-Terminalzeichen besteht, ist es gerade
kontextfrei.
Wenn u ein Terminalzeichen enthält, das ist diese Situation dort nicht
kontextfrei.
Das ist richtig.
Das dritte, v ist länger als u, gar kein Problem.
Das ist, wenn ich links etwas habe und rechts darf beliebig langes
Wort stehen, gar kein Problem.
Und das vierte, u enthält mehr als ein Zeichen, selbstverständlich ist
es dann nicht kontextfrei.
Dann ist es kontextsensitiv oder monoton oder irgendwas, aber nicht
kontextfrei.
Es ist ja kontextsensitiv auf jeden Fall, aber mehr als ein Zeichen,
dann ist es nicht kontextfrei.
Okay, damit will ich auch diese Frage hier beenden, das hier auch
zumachen und wir kommen zurück zur Vorlesung.
Es gibt aber hier noch eine Frage.
Was ist überhaupt ein Terminalzeichen?
Auch das habe ich Ihnen erklärt, das sind die Zeichen, die in dem
konstanten Alphabet, also die Zeichen der Sprache, an der wir
eigentlich Interesse haben, die Nicht-Terminalzeichen, also aus denen
ich noch etwas ableiten kann, sind die Variablen, über die ich diese
Ableitung laufen lasse und damit, also diese Groß A, Groß B und Groß C
sind Nicht-Terminalzeichen, das kleine A soll ein Terminalzeichen
bedeuten, dass ich nicht durch irgendetwas anderes mehr ersetzen kann.
Das dürfte damit auch erledigt sein, das war ein kurzer Rückblick und
jetzt kommen wir zurück zur Vorlesung.
Also, das war endlicher Automat Akzeptor mit in diesem Fall hier
einigen wenigen Zuständen und wir waren hier schon gewesen, bei dem
Automaten, der eine Sprache akzeptiert, in der ich eine ungerade
Anzahl von Einzelnen habe.
Und das war hier schon alles durchgeklickt und jetzt haben wir hier
noch einen Automaten, der hat entweder A, A oder B, B als...
also eine Sprache, beschreibe ich, die alle Wörter enthält, die auf A,
A oder B, B enden.
Wie konstruiere ich einen solchen Automaten, der jetzt genau diese
Sprache akzeptiert?
Die erste Idee wäre, naja, es soll also, wenn ich mit dem
Anfangszustand anfange, man muss ja einen Anfangszustand haben, dann
muss ich unterscheiden können, ob ich einen A oder einen B eingebe.
Das muss unterschiedliche Folgezustände bewirken.
Deswegen mit A und B gehe ich auf neue Zustände, S1 und S2.
Und wenn ich noch einen A eingebe, A, A, dann soll dieses Wort
sicherlich akzeptiert werden.
Genauso wenn auf ein B ein B folgt, soll das Wort auch akzeptiert
werden.
Das ist die gleiche Situation.
Aber da fehlt noch einiges.
Was ist, wenn ich nach einem A ein B eingebe?
Das ist auf dem nächsten Diagramm dargestellt.
Wenn ich nach einem A ein B eingebe, dann ist das die gleiche
Situation, als wenn ich zu Beginn ein B eingegeben hätte, in Bezug auf
diese Eigenschaft, die wir abprüfen wollen.
Und mit einem weiteren B wäre ich fertig.
Wenn ich ein B eingegeben habe und es kommt ein A, gehe ich hier oben
hin.
Mit einem weiteren A würde ich akzeptieren.
Und was danach passiert, ist mir eigentlich völlig egal.
Weil ich ja bereits ein AA oder ein BB gesehen habe, dann kann hier
was Beliebiges eingegeben werden.
Also das ist eine einfache Art, wie wir hier einen Automaten
konstruieren, für diese einfache Sprache.
Sie können sich vorstellen, dass das Konstruieren von Automaten
manchmal auch schwieriger sein kann.
Genauso kann das Ableiten oder das Identifizieren, welche Sprache wird
durch einen Automaten akzeptiert, ausgehend von einer
Automatendefinition, manchmal auch schwieriger sein.
Damit werden Sie sich in den Übungen intensiv beschäftigen dürfen.
Und dann gibt es eine ganze Reihe weiterer Fragen.
Kann das leere Wort Lambda zur Sprache eines Automaten gehören?
Die Antwort steht hier von Ja.
Aber warum?
Hat einer von Ihnen eine Idee?
Sie dürfen sich mal melden jetzt, wenn Sie wollen.
Hat einer eine Idee, warum das leere Wort zur Sprache eines Automaten
gehören kann?
Was ist dafür die Voraussetzung?
Wann kann bei Eingabe des leeren Wortes, wann kann ich sagen, ich bin
in einer Endkonfiguration, in dieser Anfangskonfiguration?
Hat keiner eine Idee?
Was war die Bedingung für eine Endkonfiguration?
Wir sind in einer Konfiguration S, Lambda und S ist ein Endzustand.
Was war eine Startkonfiguration?
S0, W.
S0 ist der Anfangszustand und W ist das einzugebende Wort.
Wenn das Lambda akzeptiert werden soll, muss also diese
Anfangskonfiguration S0, Lambda bereits eine Endkonfiguration sein.
Das heißt, das S0 muss ein Endzustand sein.
Dann ist das leere Wort auch akzeptiert.
Geht also problemlos.
Gibt es endliche Automaten, deren Sprache eine endliche Menge ist?
Ja, gibt es.
Ganz einfach.
Sie können ja ein einfacher Automat, der könnte Zustand 0 haben und
würde also, wenn das ein Endzustand ist, würde er bereits das leere
Wort akzeptieren.
Und für jede andere, hier stehen also E aus E, jedes andere Zeichen
führt auf irgendeinen Zustand und hier gehen wir mit jedem Zeichen E
aus E, bleiben wir in dem Zustand 1.
Das heißt, er würde nur dieses Lambda akzeptieren.
Und so können Sie sich beliebig andere Dinge überlegen, wie man das
machen kann.
Ich gebe Ihnen da noch ein Beispiel dafür.
Es sind alle endlichen Sprachen eines endlichen Automaten.
Auch das kann man sich überlegen, dass man für jede endliche Menge von
Wörtern einen Automaten konstruieren kann, der genau dieses Wort
akzeptiert.
Also wenn ich das Wort, also ich will einen Automaten konstruieren,
der das Wort Wort ähm Wort akzeptiert.
So, der hätte einen Anfangszustand und mit dem Zeichen W-O-R-T würde
er in einen Endzustand übergehen.
Ich müsste jetzt für alle anderen Übergänge irgendeinen Sonderzustand
mitnehmen, in den die auch noch führen, der nicht akzeptiert wird.
Also für alle anderen Zeichen würde ich in irgendeinen anderen
Endzustand oder irgendeinen anderen Zustand gehen, der kein Endzustand
ist.
Und damit hätte ich einen Automaten konstruiert, der nur das Wort W-O
-R -T akzeptiert.
Und entsprechend könnte ich andere Wörter natürlich auch entsprechend
hier einbauen in so einen Automaten.
Gar kein Problem.
Hier ist ein anderes Beispiel angegeben.
Dieser Automat hier unten, der hier vollständig spezifiziert ist, mit
Tupelangabe, Eingabealphabet, Zustandsmenge, Endzustandsmenge und
Zustandsdiagramm, der würde das leere Wort akzeptieren, der würde das
Zeichen B akzeptieren, der würde...
ja, was noch?
Nur das Zeichen B und Lambda.
Das alles.
Ein weiteres Zeichen, alle anderen Zeichen führen in einen Zustand,
aus dem ich nicht wieder rauskomme.
Also ganz einfache Fragen.
Jede endliche Menge wird von einem endlichen Automaten akzeptiert und
insofern ist das schon mal geklärt.
Die endlichen Mengen sind Sprachen, die von einem solchen Akzeptor
akzeptiert werden können.
Jetzt gebe ich Ihnen noch ein anderes Beispiel.
Endlicher Automat, der enthält nach jedem A genau ein B.
Also, ich möchte gerne nach jedem A genau ein B haben.
Da ist ein A, ein B.
Hier ist auch bei diesem Wort ist nach jedem A genau ein B.
Da gibt es nämlich gar kein A.
Und bei dem letzten hier, nach dem A ist ein B.
Hier habe ich eine andere Situation.
Bei diesem Wort B steht ABB.
Da stehen zwei Bs.
Ist nicht drin.
Hier habe ich ein A, darauf folgt ein C.
Auch nicht drin.
Hier habe ich das gleiche.
Auf ein A folgt ein A und auf das A folgt ein B oder noch ein B.
Da habe ich zwar genauso viele Bs wie As drin, aber ich habe nicht
genau nach dem A ein B.
Also, ein einfacher Automat, einfache Sprache, kann man sich sofort
überlegen.
Wie muss der Automat aussehen dafür?
Sieht ein bisschen aufwendiger aus, wie hier angegeben.
Ich kann also im Anfangszustand, der natürlich akzeptierender Zustand
sein muss, weil das leere Wort diese Bedingungen erfüllt, kann ich
beliebig viele Bs oder Cs eingeben und wenn ein A kommt, muss ich
testen, ob genau ein B folgt.
Also mit einem B bin ich im Endzustand.
Wenn dann noch ein B kommt, ist das Wort nicht in der Sprache, dann
bin ich also in so einer Sackgasse, aus der ich nicht wieder
rauskomme.
Wenn auf das B ein A folgt, dann darf wieder ein B folgen und so
weiter.
Wenn ein C folgt auf das B, bin ich wieder in der Anfangssituation und
dann habe ich hier alle Möglichkeiten drin.
Und wenn nach dem A ein C folgt oder ein A, dann muss ich auch in
diesen Sackgassenzustand rein.
Auch das ist relativ einfach anzugeben.
Was bedeutet das F im Tuple A?
Stand vor ein paar Folien, das ist die Menge der Endzustände.
Und der Endzustand in dem Fall, Endzustände sind S0 und S2 in dem
Beispiel Finalzustände, deswegen F.
Dann ist die Frage, ob jede Menge L und wenn jetzt alle endlichen
Sprachen von endlichen Automaten waren, kann ich dann beliebige
Teilmenge nehmen und die mit dem endlichen Automaten akzeptieren.
Und da ist es so, dass das nicht der Fall ist, das werden Sie gleich
sehen.
Und wenn das nicht der Fall ist, wie kann man feststellen, ob ein Wort
oder eine Sprache von einem endlichen Automaten akzeptiert wird,
natürlich dadurch, dass ich den Automaten angebe.
Oder, wie kann ich sagen, diese Sprache wird garantiert von keinem
endlichen Automaten akzeptiert.
Da muss ich über alle endlichen Automaten eine Aussage machen.
Und Sie haben gesehen, wie riesig die sein können.
Und trotzdem muss ich sagen können, egal wie groß der Automat wird,
diese Sprache ist nicht von einem endlichen Automaten akzeptierbar.
Das kann ja irgendwie kaum sein.
Aber ich habe Ihnen hier eine Sprache angegeben, von der wir
feststellen werden, sie wird von keinem Automaten akzeptiert.
Da steht A hoch N, B hoch N.
Ganz einfache Sprache.
Die ist übrigens, kann man sofort in einen Kontext bringen, der etwas
näher zu tun hat mit Dingen, die wir in Programmiersprachen
formulieren.
Ich kann zum Beispiel sagen, A wäre eine Klammer auf, B eine Klammer
zu.
Und wenn ich hier eine Klammer auf habe, muss ich da eine Klammer zu
haben.
Also gleich viele Klammer auf, Klammer zu.
Das ist ein Sonderfall davon, dass ich sage, okay, ich muss für jede
öffnende Klammer, muss ich auch eine schließende Klammer haben.
Das kann natürlich sein, dass ich hier eine öffnende Klammer, doch
eine öffnende habe und da eine schließende und nochmal eine öffnende
und eine schließende und nochmal wieder eine schließende.
Das hier wären sogenannte wohlgeformte Klammerausdrücke.
Das hier ist eine Teilmenge davon, wo ich nur einfach öffnende und
schließende Klammern habe.
Wir werden feststellen, auch diese hier kann man nicht mit einem
endlichen Automaten akzeptieren.
Das sind genau Strukturen, wie wir sie in jedem Programm verwenden.
Also wenn wir das hier zeigen können, dann haben wir damit gezeigt,
dass egal, was für einen Automaten wir nehmen, ein endlicher Automat
eine solche Sprache nicht akzeptieren kann.
So, warum kann das sein?
Wenn wir versuchen, dafür einen Automaten zu bauen, dann würde das
doch bedeuten, wir haben irgendeinen Anfangszustand.
Wenn dort ein B eingegeben wird, dann gehen wir in irgendeinen
Zustand, sag ich mal, nenne ich mal einfach S, Sackgassenzustand.
Wird nicht akzeptiert.
Wenn ein A eingegeben wird, muss ich in der Lage sein, zu überprüfen,
ob ein B eingegeben wird.
Wenn nach dem A und dem Zustand, den ich dann erreicht habe, ein B
eingegeben wird, muss ich sagen, dieses Wort wird akzeptiert.
Wenn darauf aber noch ein B folgt, muss ich in Sackgassenzustand
gehen.
Die andere Situation wäre, dass in dem Zustand hier kein A, sondern
kein B, sondern ein A eingegeben wird.
Dann würde das Wort akzeptiert werden, wenn ich zwei Bs eingebe.
Dann müsste ich einen Endzustand erreicht haben, das könnte der
gleiche sein wie der.
Und wenn von dem aus ein weiteres B oder ein A eingegeben wird, muss
ich in Sackgassenzustand gehen.
Und so können Sie hier beliebig weit nach rechts laufen und werden
feststellen, Sie brauchen immer mehr Zustände.
Sie müssen nämlich zählen können.
Sie müssen in der Lage sein, für ein beliebiges N zu zählen.
Das sind N-As gewesen.
Ich bin also irgendwo ganz nach rechts gekommen.
Das muss ich genauso weit nach oben laufen können, bis zu einem
Zustand, in dem ich festgestellt habe, es sind genauso viele Bs wie As
jetzt schon da gewesen.
Und wenn ich das nicht habe, dann kann ich diese Sprache nicht
akzeptieren, weil es dann irgendein N gibt, das größer ist als alles,
was ich mit meinen endlich vielen Zuständen darstellen kann.
Also macht das wohl Schwierigkeiten.
Jetzt war das eine sehr einfache, intuitive Argumentationsweise.
Und um da weiterzukommen, will ich Ihnen noch ganz schnell ein Bild
zeigen.
Eine Überlegung, die zu dem Pumping Lemma für EASprachen führen wird.
Das ich Ihnen nächstes Mal darstelle, nur das Bild, das dazu führt,
male ich Ihnen jetzt schon mal auf.
Stellen Sie sich vor, Sie geben ein Wort ein in einen Automaten.
Dieser Automat, der hat irgendeine Anzahl von Zuständen, N.
Jetzt geben Sie ein Wort ein, Sie sind hier im Zustand S0.
Fangen mit dem ersten Zeichen E1 an, kommen auf einen Zustand
irgendwie S1, haben ein E2 und so weiter.
So geht das hier immer weiter.
Das heißt, Sie geben ein Wort ein, E1, ich male das mal hier oben auf,
das ist unser Wort W.
Und dieses Wort, das hat Zeichen E1, E2 und so weiter bis EN.
So.
Mindestens N oder vielleicht sogar M Zeichen und ich habe mehr als N
auf jeden Fall.
Also das M sei größer gleich N.
Dann nehme ich ja jedes Mal einen neuen Zustand an und wenn ich also
hier bei dem Zeichen EN gelandet bin, dann komme ich hier auf einen
Zustand SN und von S0 bis SN sind es aber insgesamt N plus 1 Zustände,
die ich gar nicht unterscheiden kann.
Also muss ich doch irgendwann, irgendwann einmal muss ich hier zwei
Zustände SI und SJ gehabt haben, die identisch sind.
Weil N plus 1, unterschiedliche Zustände habe ich nicht, ich habe nur
N verschiedene.
Also müssen zwei von diesen S0 bis SN identisch gewesen sein.
Und dann heißt das, ich hätte dieses Stück hier drin gar nicht lesen
müssen, ich hätte gleich weitermachen können mit dem Stück oder ich
hätte hier beliebig rumlaufen können.
Und das heißt, dieser Automat, der kann also Wörter eine ganze Zeit
lang lesen, kann dann eine Schleife machen und anschließend noch ein
Endwort lesen und kommt dann in irgendeinen Endzustand hier doppelt
gekringelt.
Und was dazwischen steht, kann er beliebig oft machen, kann er pumpen.
Und jedes solche Wort, das beliebig viele Wiederholungen hat, von
diesem Teil in der Mitte, der hier schraffiert ist, jedes solche Wort
wird akzeptiert, wenn das Originalwort W akzeptiert wird.
Wenn ich mit dem Wort W von E1 bis EM in einen Endzustand komme, wird
auch jedes andere Wort, das hier beliebig oft den schraffierten Teil
drin hat, auch zu einem Endzustand führen, zu dem gleichen nämlich.
Das heißt, dieser endliche Automat kann das gar nicht unterscheiden,
wie häufig hier dieser Mittelteil drin ist und deswegen würde die alle
akzeptieren.
Deswegen nennt man das Pumping Lemma.
Das schauen wir uns nächstes Mal noch genauer an, warum man auf diese
Formulierung kommt.
Okay, das war es für heute, ich danke Ihnen für die Aufmerksamkeit.