Quoted

Lexikalische Analyse

Formale Sprachen

Vorübung:
· deutsche Sprache = {Wörter}
Ein Wort der deutschen Sprache wird über dem Alphabet {a,b,...,y,z,A,B,...,Y,Z} gebildet.
Wort ® Zeichenfolge
„Computer ® „C,o,m,p,u,t,e,r“
® Zeichenfolge
Wort ¬ „o,C,m,u,r,e,t,p“

· Programmiersprache
= {Schlüsselwörter, Bezeichner, Operatoren,...}

Wörter der Programmiersprache

· Maschinensprache
= {Dualzahlen}
Dualzahlen über dem Alphabet {0,1}
z.B.: 11101011
10100111
11001100


Definitionen
· Eine endliche Zeichenkette, die über dem Zeichen einer überlieferten oder vereinbarten Zeichenmenge gebildet ist, heißt Wort.
· Eine Teilmenge der Menge aller Wörter über einer Zeichenmenge nennt man Formale Sprache.
· Die zu Grunde liegende Zeichenmenge nennt man Alphabet.
· Die Anzahl der Zeichen in einem Wort heißt Länge des Wortes.

Beispiel:
Sei M die Menge aller Wörter (Dualzahlen) über {0,1}. Die Menge L={00,01,10,11}, Menge aller 2-stelliger Dualzahlen ist eine Teilmenge von M. L Ì M.
L ist eine formale Sprache.

Über den Mengen und somit über den formalen Sprachen gelten alle Mengenoperationen, hier: Sprachenoperationen. Für die formalen Sprachen brauchen wir insbesondere die Vereinigung und die Konkatenation:
Vereinigung „È“ <-> „+“
Konkatenatoin = Zusammensetzung

Beispiele
· Vereinigung
L1, L2 seien formale Sprachen über M mit
L1 = {10,100,110,1000,1010,...}
L2 = {1,11,101,111,1001,...}
L3 = L1 + L2 = {1,10,11,100,101,...}


alle nat. Zahlen
L4 = L2 + L1 = L1 + L2

Für die Vereinigung formaler Sprachen gilt das Kommutativgesetz.
L1 + L2 = L2 + L1

· Konkatenation
L1 = {1,11,101}
L2 = {10,0}
L1L2 = {110,10,1110,110,10110,1010}
L2L1 = {101,1011,10101,01,011,0101} = {101,1011,10101,1,11}

Für die Konkatenation formaler Sprachen gilt nicht das Kommutativgesetz.
L1L2 ¹ L2L1

Definition:
Die Zusammensetzung zweier Wörter heißt Konkatenation. Sind L und M zwei formale Sprachen, dann bezeichnet LM die Sprache aller Wörter, die durch Konkatenation aller Wörter von L mit allen Wörtern von M entstehen. Seien x und y zwei Wörter, dann wird ihre Konkatenation durch xy bzw. yx bezeichnet (i.a. xy ¹ yx)
Beispiel: x = 1000 x Î L1
y = 11 y Î L2
xy = 100011 xy Î L1L2
yx = 111000 yx Î L2L1
Beachte L1L2 ¹ L2L1

Bemerkung:
Die kürzesten Wörter einer Sprache sind die, die nur ein Zeichen enthalten ({0} bzw. {1}). Wörter größerer Länge können durch Konkatenation von Wörtern der Länge 1 erzeugt werden.
z.B.: L1 = {1} L2 = {0}
L = L1 L2 L1 L1 L2
= {10110}


Vereinbarung zur Mengenschreibweise
Mengenklammer: [ « {
] « }


Die n-fache Konkatenation einer formalen Sprache L
Definition
Sei L eine formale Sprache, dann ist LLL...L = L­n die n-Potenz von L.

Beispiel:
L = [10,11]
L­1 = L
L­2 = LL
= [10,11] [10,11]
= [1010,1011,1110,1111]
L­3 = LLL
:
L­n = LLL...L 2n Elemente
Die Menge der Wörter der Länge n über A
Definition:
Ist A ein Alphabet, dann bezeichnet A­n die Menge der Wörter der Länge n über A.

Beispiel:
A =[0,1]
A­1 = A
A­2 = AA
= [0,1] [0,1]
= [00,01,10,11]
A­3 = AAA
= [0,1] [0,1] [0,1]
= [000,001,010,011,100,101,110,111]

2³ = 8 Elemente (Menge aller 3-stelligen Wörter)




Die Menge aller Wörter über A
Vorübung:
A­1 = A = [0,1]
A­2 = AA = [00,01,10,11]
A­3 = AAA = [000,...,111]
A­n = AAA...A = [alle Wörter der Länge n]

A+ = A­1 + A­2 + ­3 + ... + A­n nÎN