Was mich bewegt
Hab nach einiger Zeit damit angefangen, das einzig richtige zu machen; die Prüfungsaufgaben zur Vorbereitung auf das nächste Mal abzuschreiben :-) Nunja …
[Nachtrag:]
Hier (pdf, 164 kB) findet ihr die abgetippte Version der Klausur :-)
[Nachtrag 2:]
163 Downloads bis jetzt (1 Uhr). Wieviele glauben denn da von sich durchgefallen zu sein? :-)
Noch ein paar Minuten, dann heißt es „Stifte weg“. Und was steht auf meinem Blatt? Nicht viel … mal sehen :-)
Die 2. Stunden ist angebrochen. Verzweiflung breitet sich aus. Es gibt nur noch wenige, die wirklich mit den Aufgaben zu tun haben bzw. noch nicht aufgegeben haben …
1 Stunde ist vorbei … die ersten sind frustriert aufgestanden. Sebbi hält durch …
Man setzt sich, wartet auf die Aufgabenblätter. 16 Stück an der Zahl werden es sein, eine irrsinniger als die andere …
In einer Stunde geht’s los :-)
Endliche Automaten:
5-Tupel M = viel zu kompliziert um hier hingeschrieben zu werden :-)
Wichtig ist: Man wirft dem Automaten ein Wort hin und der Automat kommt hoffentlich im gewollten Endzustand an. Wenn nicht, dann ist das Wort nicht Element der Sprache, die der endliche Automat definiert. Wenn doch, dann prima, es ist ein Element der Sprache! Ach und ja, wenn’s erkannt wird, ist die Sprache natürlich regulär (Typ 3), was sonst :-)
So … und hier an diesem Punkt gebe ich auf das ganze Zeug von TI1 in diesen/s Blog zu quetschen … lol … war keine gute Idee :twisted::twisted:
4-Tupel: G= (V, T, P, S) mit V ist endliche Menge der Variablen, T ist endliche Menge (Terminalalphabet). V geschnitten T ist die Leere Menge. P ist endliche Menge der Produktionen – formal: Teilmenge von (V vereinigt T)+ x (V vereinigt T)*. S ist Element von V und ist Startvariable.
Erzeugbare Sprache von G:
L(G) = { w Element von T* | S ->*G w }
->*G: reflexive und transitive Hülle von ->G
Beispiel:
G = ({E,T,F}, {(,),a,+,*}, P, E)
P = {E->T,
E->E+T,
T->F,
T->T*F,
F->a,
F->(E) }
„a * a * (a +a) + a“ wäre damit ein Element von L(G)
Ausgehend von der Startvariable kann man einen Baum mit möglichen Wörtern zeichnen (Blätter = Wörter). Es kann dabei unendlich lange Pfade geben und es kann auch Sackgassen geben, die sich nicht zu einem Terminalwort ableiten lassen.
Chomsky:
Es gibt Typ 0 Sprachen, die entscheidbar sind. Auf jeden Fall entscheidbar sind alle Typ 1-3 Sprachen. Entscheidbar heißt, es gibt einen Algorithmus, der in endlicher Zeit feststellt, ob ein Wort zu der Sprache gehört oder nicht.
Eine Grammatik heißt mehrdeutig, wenn es mehrere Syntaxbäume für ein und dasselbe Wort gibt, am sonsten heißt sie eindeutig. Eine kontextsensitive Sprache (Typ 1) heißt inhärent mehrdeutig, wenn es keine Möglichkeit gibt eine eindeutige Grammatik zu finden. Es ist i.A. nicht möglich durch einen Algorithmus Mehrdeutigkeit festzustellen.
Backus-Naur-Form (BNF):
Kompakte Beschreibung von Typ 2 Grammatiken
A->b1
A->b2
A->b3
wird: A-> b1|b2|b3
A->ac
A->abc
wird: A->a[b]c
A->ac
A->abc
A->abbc
A->ab….bc (oder: A->aBc, B->b, B->bB)
wird: A->a{b}c
Dieses Posting bitte ignorieren. Ich hab’s nur spaßeshalber mal online gestellt. Der Inhalt befindet sich den nächsten Seiten…
Mangels guter Todoliste (findet mal eines im Internet, gibt’s nicht) und weil ich’s nicht auf Papier schreiben will, hier meine Todoliste für’s Sommersemester 2004:
500+ Seiten sehen gar nicht so viel aus, wenn man 8 davon auf ein Din A4 Blatt quetscht (doppelseitig). Trotzdem bleiben 500 Seiten, 500 Seiten. Verdammt wird das unlustig. Heute wird der Lernplan aufgestellt … hurray! Ich suche nach einer (multiuserfähigen) Todoliste, die auch „Unteraufgaben“ hat und mich keine 5 Minuten Einrichtungszeit kostet und auch ausgedruckt nett anzusehen ist. Hat das wer was?