Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
Diskrete Mathematik I
Vorlesung 11
Grammatiken, Sprachen und
deren Verarbeitung
14
15
16
17
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Wo bin ich?
$GPGLL,3455.45,N,74565.87,E,215421.54,V*23
17
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Beispiel: Satzbau in deutscher Sprache (Auszug)
Grammatik:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
<Satz>
<Subjekt>
<Objekt>
<Prädikat>
<Prädikat>
<Artikel>
<Substantiv>
<Substantiv>








<Subjekt> <Prädikat> <Objekt>
<Artikel> <Substantiv>
<Artikel> <Substantiv>
jagt
beißt
die
Maus
Katze
Ableitung:
<Satz>  <Subjekt> <Prädikat> <Objekt>
 <Artikel> <Substantiv> <Prädikat><Artikel> <Substantiv>
 die <Substantiv> <Prädikat> die <Substantiv>
 die Katze jagt die Maus
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Übersicht
•
•
•
•
•
•
•
•
•
Beispiel: Grammatik der deutschen Sprache (Auszug)
Grammatik: formale Definition
Ableitung, von Grammatik erzeugte Sprache
Hierarchie von Sprachen/Grammatiken
'kontextfreie' Sprachen/Grammatiken
•
Beispiel 'Arithmetische Ausdrücke'
•
Ableitungsbäume
'reguläre' Sprachen/Grammatiken
Einlesen/Verarbeiten von Sprachen
'endliche Automaten' (Zustandsübergangsgraphen)
Beispiel: Einlesen/Verarbeiten von GPS-Daten (NMEA-Format)
15
16
17
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Motivation
•
•
•
Grammatik: formale Beschreibung von Sprachen
•
natürliche Sprachen
•
Fokus: formale Sprachen (Java, arithmetische Ausdrücke, HTML, XML, ...)
Überprüfung der syntaktischen Korrektheit
•
Überprüfung, ob Wort zur Sprache gehört (grammatikalisch richtig ist)
Voraussetzung für Verarbeitung
•
Erkennung/Verarbeitung natürlicher Sprachen
•
Kompilieren/Ausführen von Java-Programmen
•
Berechnen arithmetischer Ausdrücke
•
Einlesen/Verarbeiten von GPS-Signalen, Dateien mit TachymeterMesspunkten, GIS-Daten,....
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Grammatik: formale Definition
Eine Grammatik G ist definiert durch G = (N, T, S, P), mit
•
N: endliche Menge der Nichtterminalsymbole
•
T: endliche Menge der Terminalsymbole (N und T sind disjunkt)
•
S: Startsymbol, aus N
•
P: endliche Menge von Ersetzungsregeln p  q, wobei p und q aus (N  T)*
sind
*: Stern-Operator: M* ist die Menge aller Worte, die sich aus den Symbolen
aus M bilden lassen.
Bsp: {a}* = {, a, aa, aaa, aaaa, aaaaa, ...}
Bsp: {a,b}* = {, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab,...}
: leeres Wort, ist immer dabei
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Grammatik: Beispiel Satzbau
Eine Grammatik G ist definiert durch G = (N, T, S, P) mit
•
N: {<Satz>,<Subjekt>,<Prädikat>,<Objekt>,>Artikel>,<Substantiv>}
•
T: {die, Katze, Maus, jagt, beißt}
•
•
S: <Satz>
P: Menge der Ersetzungsregeln p  q
<Satz>
<Subjekt>
<Objekt>
<Prädikat>
<Prädikat>
<Artikel>
<Substantiv>
<Substantiv>
 <Subjekt> <Prädikat> <Objekt>
 <Artikel> <Substantiv>
 <Artikel> <Substantiv>
 jagt
 beißt
 die
 Maus
 Katze
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ableitungsschritt, ableitbar
•
•
•
•
•
•
Gegeben: Grammatik G = (N,T,S,P)
X ist Wort aus (N  T)* (d.h. beliebige Kombination aus Terminal- und
Nichtterminalsymbolen)
p  q ist Ersetzungsregel aus P
X = apb, d.h. p taucht in X auf
dann ist Y = aqb aus X = apb ableitbar durch die Ersetzungsregel p  q
Schreibweise: apb  aqb oder X  Y
Beispiel:
Das Wort
Y=
die <Substantiv> jagt die <Substantiv>
ist aus
X=
die <Substantiv> <Prädikat> die <Substantiv>
ableitbar durch die Regel
<Prädikat>  jagt
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ableitungsbaum
•
Zur Darstellung der Ableitungsschritte können Bäume verwendet werden.
Beispiel:
<Satz>
<Subjekt>
<Artikel>
<Substantiv>
die
Katze
<Prädikat>
jagt
<Objekt>
<Artikel>
<Substantiv>
die
Maus
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Sprache
•
•
Gegeben: Grammatik G = (N,T,S,P)
Die von G erzeugte Sprache ist die Menge aller Worte,
die aus S durch Anwendung der Ersetzungsregeln P ableitbar sind, und
die nur aus Terminalsymbolen T bestehen.
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sprache: Beispiel Satzbau in deutscher Sprache
•
Die von der Satzbau-Grammatik erzeugte Sprache ist
{ die Maus jagt
die Maus,
die
die
die
die
die
die
die
•
Maus
Maus
Maus
Katze
Katze
Katze
Katze
jagt
beißt
beißt
jagt
jagt
beißt
beißt
die
die
die
die
die
die
die
Katze,
Maus,
Katze,
Maus,
Katze,
Maus,
Katze
}
Keine Worte dieser Sprache sind:
•
•
•
die Katze <Prädikat> die Maus
die Katze frisst die Maus
Katze beißt Maus
17
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Klassifikation von Sprachen/Grammatiken
Informatik:
ChomskyHierarchie
Sprache/Grammatik
Einschränkung der Regeln
regulär
(Typ 3)
A  wB oder
Aw
A,B: Nichtterminalsymbol
w: Wort aus Terminalsymbolen
kontextfrei
(Typ 2)
Aa
A: Nichtterminalsymbol
a: beliebiges Wort, |a| > 0
kontextsensitiv
(Typ 1)
pq
|q|  |p|
p,q: beliebig
rekursiv aufzählbar
(Typ 0)
beliebig
nur die grau
unterlegten
Grammatiken werden
hier behandelt
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Kontextfreie Grammatiken und Sprachen
•
Definition: Ein Grammatik G heißt kontextfrei, wenn die Regeln die Form
•
Aa
haben, wobei A ein Nichtterminalsymbol und a ein beliebiges Wort ist (|a| > 0)
•
Eine Sprache heißt kontextfrei, wenn sie von einer kontextfreien Grammatik
erzeugt wird
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Kontextfreie Grammatik: Bsp. Arithmetische Ausdrücke
G sei definiert durch
•
•
•
•
•
Nichtterminalsymbole: {A}
Terminalsymbole: {+, —, * ( , ),a,b,c}
Startsymbol: A
Regeln:
(1)
AA*A
(2)
AA+A
(3)
AA—A
(4)
A  (A)
(5)
(6)
(7)
(8)
Aa
Ab
Ac
A  —A
Ableitung (Bsp): A  A * A  A * (A)  A * (A + A)  —A * (A + A) 
—A * (—A + A)  —A * (—(A) + A)  A * (—(A — A) + A) 
—c * (—(A — A) + A)  c * (—(b — A) + A)  c * (—(b — a) + A) 
—c * (—(b — a) + c)
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Arithmetische Ausdrücke: Ableitungsbaum
Ableitung:
A
A*A
A * (A) 
A * (A + A) 
—A * (A + A) 
—A * (—A + A) 
—A * (—(A) + A) 
—A * (—(A — A) + A) 
—c * (—(A — A) + A) 
—c * (—(b — A) + A) 
—c * (—(b — a) + A) 
—c * (—(b — a) + c)
A
A
—
*
A
A
(
A
)
c
A
+
A
—
(
A
c
A
A
b
—
)
A
a
17
18
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Reguläre Grammatiken und Sprachen
•
Definition: Ein Grammatik G heißt regulär, wenn die Regeln die Form
•
A  wB oder
•
Aw
haben, wobei A und B Nichtterminalsymbole sind und w ein Wort aus
Terminalsymbolen ist
•
Eine Sprache heißt regulär, wenn sie von einer regulären Grammatik erzeugt
wird
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Reguläre Grammatiken/Sprachen: Beispiel
•
•
Sprache: waa...axbb...bycc...cz
Grammatik G:
•
•
•
•
Nichtterminalsymbole: {S,A,B,C}
Terminalsymbole: {a,b,c,w,x,y,z}
Startsymbol: S
•
Regeln: (1) S  wA
(5) B  yC
(2) A  aA
(6) C  cC
(3) A  xB
(7) C  z
(4) B  bB
Ableitung (Beispiel):
S  wA  waA  waaA  waaaA  waaaxB  waaaxbB  waaaxbbB
 waaaxbbbB  waaaxbbbbB  waaaxbbbbyC  waaaxbbbbycC 
waaaxbbbbyccC  waaaxbbbbycccC  waaaxbbbbyccccC 
waaaxbbbbyccccz
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Erkennung/Verarbeitung von Sprachen
•
•
•
•
Grammatiken: Erzeugung von Worten einer Sprache
Komplementäres Problem: Erkennung eines Wortes
• Gehört ein Wort zur Sprache oder nicht?
• z.B. ist Java-Programm syntaktisch korrekt (keine Syntaxfehler)?
• z.B. ist ein HTML-Dokument syntaktisch korrekt?
Voraussetzung zur Verarbeitung eines Wortes
• Zerlegen von Datensätzen, Extrahieren von Informationen
• z.B. Erkennung von Subjekt, Prädikat, Objekt
• z.B. Extraktion von Koordinaten aus GPS-Daten
• Begriff: 'parsen' (vgl. Vorlesung Java: Token)
zu jedem Grammatik-Typ (3-0) gibt es entsprechendes
Erkennungsverfahren
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Erkennung/Verarbeitung von Sprachen
Sprache/
Grammatik
Einschränkung der
Regeln
Mechanismus zur
Erkennung
regulär
(Typ 3)
A  wB
Aw
A,B: Nichtterminalsymbol
w: Wort aus
Terminalsymbolen
Endlicher Automat
kontextfrei
(Typ 2)
Aa
A: Nichtterminalsymbol
a: beliebig, |a| > 0
Kellerautomat
kontextsensitiv
(Typ 1)
pq
|q|  |p|
p,q: beliebig
linear beschränkte
Turing-Maschine
rekursiv aufzählbar
(Typ 0)
beliebig
Turing-Maschine
nur die grau
unterlegten
Konzepte werden
hier behandelt
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Endliche Automaten
•
Ein endlicher Automat besteht aus
•
einer endlichen Menge Q von Zuständen
•
einem Anfangszustand aus Q
•
einer Menge von Endzuständen (Teilmenge von Q)
•
einer Zustandsüberführungsfunktion:
überführt einen Zustand q1 durch Lesen eines Terminal-Wortes w in den
Zustand q2
•
Beispiel (graphische Notation):
S
abc
A
d
xyz
B
x
Ende
y
Ein endlicher Automat
ist ein gerichteter,
markierter Graph
(vgl. nächste Vorlesung:
Dijkstra)
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Endliche Automaten und reguläre Sprachen
•
•
Gegeben: eine reguläre Grammatik G = (N,T,S,P)
Konstruktion des endlichen Automaten zu G:
•
Zustandsmenge ist Menge der Nichtterminalsymbole, plus einem extra
Endzustand
•
Anfangszustand entspricht Startsymbol
•
Jede Ersetzungsregel entspricht einem Zustandsübergang:
•
•
•
A  wB: Übergang von A nach B durch Lesen des Wortes w
•
A  w: Übergang von A in Endzustand durch Lesen des Wortes w
Ein endlicher Automat zu einer Grammatik G akzeptiert ein Wort, wenn er
•
beginnend im Anfangszustand
•
das Wort schrittweise gemäß der Zustandsübergangsfunktion liest, und
•
nach dem Lesen in einem Endzustand ist
Ein endlicher Automat zu einer Grammatik G akzeptiert ein Wort w genau
dann, wenn das Wort w von der Grammatik G erzeugt wird
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Endlicher Automat zu regulärer Grammatik: Beispiel
•
Sprache: waa...axbb...bycc...cz
•
Regeln:
(1)
(2)
(3)
(4)
•
S  wA
(5)
A  aA
A  xB
B  bB
(6)
(7)
Zugehöriger endlicher Automat:
S
w
x
A
a
•
•
•
•
B  yC
C  cC
Cz
z.B.
z.B.
z.B.
z.B.
wird
wird
wird
wird
Wort
Wort
Wort
Wort
y
B
b
C
z
Ende
c
waaaaaaxycccccz akzeptiert
waxbbyccz akzeptiert
waaafbbyccz nicht akzeptiert
waxby nicht akzeptiert (kein Endzustand erreicht)
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Beispiel: Interpretation eines GPS-Formats
•
•
•
•
•
•
•
•
Standard NMEA 0183 (National Marine Electronics Association)
Auslesen von Informationen aus GPS-Geräten
wird von fast allen GPS-Geräten unterstützt
Protokoll besteht aus mehreren Sätzen (ASCII/Text)
Satz beginnt mit Dollarsymbol ($) und endet mit neuer Zeile(<CR><LF>)
Nach $ kommt Kennung des Satzes, z.B.
•
$GPGLL: Geographic Position – Latitude/Longitude
•
$GPWNC: Distance - Waypoint to Waypoint
•
$GPGSV: Satellites in view
•
......
Kennung bestimmt das Format des Satzes
Endlicher Automat zum Einlesen von NMEA....
19
20
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
NMEA: GLL: Geographic Position – Latitude/Longitude
$GPGLL,llll.ll,a,yyyyy.yy,a,hhmmss.ss,A*hh<CR><LF>
Kennung
geogr. Breite
N or S (North or South)
geogr. Länge
$GPGLL, zzzz
S1
S2
S3
Prüfsumme
Zeit (UTC)
Status (A: Valid, V: Invalid)
E or W (East or West)
zz
.
S4
S5
,
S6
c
S7
,
S8
zzzzz
<CR><LF>
zz
,
S20
S19
c
S18
,
zz
S17
S16
.
c ist Buchstabe
z ist Zahl
S21
.
zzzzzz
S15
S14
,
S13
S9
c
S12
,
zz
S11
S10
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
NMEA: WNC - Distance - Waypoint to Waypoint
$GPWNC,x.x,N,x.x,K,c--c,c--c*hh<CR><LF>
Kennung
Prüfsumme
Name des TO Waypoint
Name des FROM Waypoint
Abstand in naut. Meilen
N: Naut. Meilen
Abstand in Kilometern
$GPWNC,
S22
z
K: Kilometer
S23
.
S24
z
S25
,
S26
N
S27
,
S28
z
S1
<CR><LF>
S29
.
S37
zz
S36
*
,
S35
c
S34
c
,
K
S33
S32
,
S31
z
S30
Diskrete Mathe 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Endlicher Automat zum Einlesen von NMEA
......
<CR><LF>
S2
$GPGLL,
S1
......
$GPWNC,
$GPGSV,
S38
<CR><LF>
S22
......
<CR><LF>
......
17
18
19
20

(4) A