Autor: Sebbi

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:

• Typ 0: alle Grammatiken
• Typ 1: heißt auch kontextsensitiv; wenn für w1->w2 in P gilt: |w1| < = |w2|
• Typ 2: heißt auch kontextfrei; wenn Grammatik von Typ 1 und falls für w1->w2 in P gilt: w1 ist eine einzelne Variable (also nicht zusammengesetzt)
• Typ 3: oder auch regulär; wenn Gramatik von Typ 2 und falls w2 entweder nur aus T oder einem Element aus T gefolgt von einem aus V

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: