close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Formale Sprachen und Grammatiken

EinbettenHerunterladen
Technische Universität München
Zusammenspiel: Grammatiken und Automaten
Problem:
• Gegeben sei eine Grammatik G.
• Wie kann man erkennen, ob ein gegebener Zeichenstring w ein
Wort der von G erzeugten Sprache L(G) ist, also w∊ L(G)?
Lösung:
• Über erkennende, akzeptierende Automaten (später noch genauer)
Generierende Grammatiken
Reguläre Sprachen, Typ 3
Kontextfreie Sprachen, Typ 2
Kontextsensitive Sprachen, Typ 1
Freie Sprachen, Typ 0
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
Erkennende Automaten
Endliche Automaten (DFA)
Kellerautomat
Linear beschränkter Automat
Turing-Maschine
1
Technische Universität München
10.4.1 Typ-3 Grammatik, Reguläre Sprachen
Eine Grammatik ist vom Typ 3 (regulär), falls
alle Produktionen p ∊ P die folgende Form haben:
A ::= w | wB | Bw mit A, B ∊ N, und w ∊ T*
D.h. bei regulären Grammatiken steht auf der rechten Seite einer
Produktion (Regel) höchstens ein Nichtterminal.
Die von einer Typ-3 Grammatik erzeugte Sprache heißt
Reguläre Sprache.
Spezielle reguläre Grammatiken:
das Nichtterminal in den betreffenden Regeln steht entweder
• stets ganz rechts – rechtslineare Grammatik (A :: = wB ) oder
• stets ganz links – linkslineare Grammatik (A :: = Bw ).
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
2
Technische Universität München
Beispiele: Regulärer Grammatiken
Beispiel 1: Gegeben sei die Grammatik G=(T,N,S,P) mit
T = {a, b, c}, N = {S, A}
P = { p1= S::= abS; p2=S::= cA; p3=A::=baA; p4=A::=a }
P umfasst vier Produktionsregeln.
Das Wort mit den wenigsten Buchstaben ist w = ca, S::= cA =:: ca
Die Grammatik G erzeugt die Sprache L(G), mit
L(G) = { (ab)nc(ba)ma, mit m, n  0 }
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
3
Technische Universität München
Beispiele: Regulärer Grammatiken
Beispiel 2: Grammatik zur Erzeugung von Binärzahlen
T = { 0, 1}, N = { D, Z }, S = D (Dualzahl)
P = { D::= 0, D::= 1Z; Z::= 1Z; Z::= 0Z; Z::= ε}.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
4
Technische Universität München
Definition: Regulärer Ausdruck (RegA)
Gegeben sei ein endliches Alphabet von Terminalzeichen T.
• ∅ ist ein regulärer Ausdruck.
• Ein beliebiges Zeichen a aus dem Alphabet T ist ein RegA.
• Die Sequenz r1r2 (r1 gefolgt von r2) ist ein RegA, wenn
r1 und r2 RegAs sind
• Alternative: r1| r2 (entweder r1 oder r2) ist ein RegA,
wenn r1 und r2 RegAs sind.
• r* iterierte Sequenz, r | rr | … ist ein RegA.
• r+ Iteration, ein oder mehrere Male angewandt, ist ein RegA.
Eine reguläre Sprache L kann durch
• einen regulären Ausdruck beschrieben und
• durch eine reguläre Grammatik erzeugt werden.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
5
Technische Universität München
Beispiele: Gegeben sei das Alphabet T ={0,1}
Reguläre Ausdrücke sind z.B.
(1) 0
(2) 1
(3) (01)
(4) ((01)0)
(5) (0|1)
(6) (0*)
Die von einem regulären Ausdruck R beschriebene Sprache L(R)
ist wie folgt definiert:
• L(∅) = {}.
• Für alle a ∊ T ist L(a) = {a}.
• Seien R1 und R2 RegA, dann ist L(R1|R2) = L(R1) ∪ L(R2).
• R1 und R2 RegA: L(R1R2) = L(R1)L(R2) = {uv| u ∊L(R1), v∊L(R2)}
• Sei R ein RegA, dann ist L(R*) = L(R)*
Ist w ∊ L(R) dann sagen wir, dass w auf das Muster R passt.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
6
Technische Universität München
Beispiele: Regulärer Ausdruck („grep“ Syntax)
Populäres Programm für reguläre Ausdrücke ist „grep“.
Nahezu jede Skriptsprache (Perl, Python, Javascript, Ruby, etc.) kann
mit regulären Ausdrücken umgehen.
Titel einer HTML Seite: <title>(.*)</title>
Gültige Telefonnummer: ^(\(?\+?[0-9]*\)?)?[0-9_\\(\)]*$
Gültige IP-Adresse: \b(([01]?\d?\d|2[0-4]\d|25[05])\.){3}([01]?\d?\d|2[0-4]\d|25[0-5])\b
Datum der Form dd-mm-yyyy oder dd/mm/yyyy:
(0[1-9]|[12][0-9]|3[01])[- /.](0[1-9]|1[012])[/.](19|20)\d\d
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
7
Technische Universität München
Erläuterung zur Syntax von Regulären Ausdrücken
[0-9] : Eine Ziffer von 0 bis 9.
\d
: Entspricht dem Ausdruck [0-9].
^
: Steht für den Zeilenanfang.
$
: Zeilenende.
{n}
: Der voranstehende Ausdruck muss exakt n-mal
vorkommen.
?
: Der voranstehende Ausdruck ist optional, er kann
einmal vorkommen, muss es aber nicht, d. h. der
Ausdruck kommt null- oder einmal vor.
+
: Der voranstehende Ausdruck muss mindestens einmal
vorkommen, darf aber auch mehrfach vorkommen.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
8
Technische Universität München
Problem:
• Wie erkennt man, ob eine Grammatik G regulär ist oder nicht?
Lösung: Pumping-Lemma für reguläre Sprachen
Sei L ⊆ T* eine reguläre Sprache.
Dann gibt es eine natürliche Zahl n>0, so dass es für jedes w  L
mit |w|  n x,y,z  T* gibt, so dass gilt:
• w = xyz
•|y|1
• | xy |  n
•  i  0 ; xyiz  L
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
9
Technische Universität München
Beweis
Sei A ein DFA mit A= (Q,Σ,δ,q0,F).
Sei n = |Q|.
Sei w  L mit |w|  n
Sei q0 = q(0), q(1), … , q(|w|) die beim Lesen des Eingabestrings w
durchlaufene Folge von Zuständen von A.
Dann muss es 0 ≤ i < j ≤ n ≤ |w| geben, mit q(i) = q(j).
Seien nun x die ersten i-Zeichen von w , y die nächsten j-1 Zeichen
und z der Rest.
Dann gilt: w = xyz, |y|  1, |xy|  n, xykz  L, für alle k  0
y
qo
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
x
qi
n
z
F
10
Technische Universität München
Beispiel: Anwenden des Pumping Lemmas
Gegeben sei die Sprache L01 = { 0n1n, mit n  0 }
Frage: Ist L01 regulär ?
Ann.: L01 ist regulär, dann ist das Pumping Lemma anwendbar:
Das Wort
w = 0n1n ist in der Sprache L01. für ein n  0
w ist zerlegbar: w = xyz mit y  , | xy |  n
Es gilt:
• Da gilt, | xy |  n, kann x nur aus Nullen bestehen.
• Für z muss dann gelten: z= 1n
da auch xz  L01 , da mit Pumping-Lemma gilt: xykz  L für k=0
• Unter Anwendung des Pumping-Lemmas können aber auch
Worte der Form: 0n+k1n gebildet werden (Aufpumpen von y),
diese Worte liegen aber nicht in L01 und L01 ist damit nicht regulär.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
11
Technische Universität München
Beispiel lehrt:
• Reguläre Grammatiken sind nicht geeignet, um Sprachen mit
symmetrischen Schachtelungsstrukturen wie Klammerungen, zu
erzeugen.
• Solche Schachtelungsstrukturen treten aber in der Praxis u.a.
bei der maschinellen Verarbeitung von Programmen, häufig auf.
Beispiel:
• (a+(b-c))*(d-(x-(y-z)))
• if (x < y) if (y < z) a = 5 else a = 6 else a = 7
• Schachtelung (Nesting) erfordert das Verwalten von Zählern, um
Anzahl der öffnenden und schliessenden Klammern zu zählen.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
12
Technische Universität München
Beispiel: Grenzen der endlichen Automaten
Prüfen der korrekten Klammerung eines Ausdrucks:
• endlicher Automat akzeptiert korrekte, aber
auch einige inkorrekte Programme
• oder endlicher Automat weist inkorrekte
Programm ab, aber auch einige korrekte
Beispiele: (1) ) )
(2) ( ( ) ( ) )
Problem:
• der endliche Automat kann nicht ‚mitzählen‘,
wieviele Klammern aufgetreten sind
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
)
)
(
(
(
(
)
)
)
)
)
13
Technische Universität München
10.4.2 Typ-2 Grammatik, kontextfreie Sprachen
Eine Grammatik ist vom Typ 2 (kontextfrei), falls
alle Produktionen p ∊ P die folgende Form haben:
A ::= w mit A ∊ N, und w ∊ (N ∪ T)*
D.h. auf der linken Seite einer Produktionsregeln darf stets nur
genau ein Nichtterminalsymbol stehen (ohne Kontext).
Die rechte Seite einer Regel kann aus belieben Strings
aus Terminal- und Nichtterminalsymbolen bestehen.
Unterschied zu regulärer Sprache:
• dort max 1 Nichtterminal auf der rechten Seite. kf-Sprachen
Es gilt: jede reguläre Sprache ist auch eine
kontextfreie Sprache, aber nicht umgekehrt.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
Reguläre
Sprachen
14
Technische Universität München
Beispiel 1: Kontextfreie Grammatik für arithmetische Ausdrücke
Vereinfachung: sei v eine Variable und z eine Zahl
Terminale T = { +, -, *, /, (, ), v, z }
Nichtterminale N= { A, T, F }
Produktionsregeln P = {
A ::= T; A::= -T; A::= +T;
A ::= T+ A; T ::= F; T ::= F*A;
A ::= F/T;
F ::= v; F ::= z; F ::= (A) }
Abkürzungen:
• A für arithmetischen Ausdruck;
• T für Term, F für Faktor
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
15
Technische Universität München
Beispiel 2:
Die Sprache L01 = { 0n1n, mit n  0 } ist kontextfrei (aber nicht regulär).
Sie wird durch eine Grammatik mit der Produktionsregel:
S::= 0S1 | ε
erzeugt.
Regel: 0S1 ermöglicht die Beibehaltung der Klammerung,
bei regulären Sprachen: nur rechte Seiten der Art: 0S| 1S| S1
Wichtig für Programmiersprachen: u.a Regel für If-Anweisung
If_stmt::= IF <Bedingung> THEN <statement> ELSE <statement>
Kontextfreie Sprachen werden u.a. bei Compilern in der
Phase der Syntaxanalyse (durch den Parser) verwendet.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
16
Technische Universität München
Beispiel 2:
Die Sprache L01 = { 0n1n, mit n  0 } ist kontextfrei (aber nicht regulär).
Sie wird durch eine Grammatik mit der Produktionsregel:
S::= 0S1 | ε
erzeugt.
Kontextfreie Sprachen werden u.a. bei Compilern in der
Phase der Syntaxanalyse (durch den Parser) verwendet.
Grenzen kontextfreier Sprachen:
In der Praxis gibt es viele Anwendungsbereiche, in denen der Kontext eine Rolle spielt. Um derartige Szenarien zu beschreiben,
reichen kontextfreie Sprachen nicht aus, man muss auf kontextsensitive Sprachen übergehen.
Beispiele: Typüberprüfung in Programmen
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
17
Technische Universität München
10.4.3 Typ-1 Grammatik, kontextsensitive Sprachen
Eine Grammatik ist vom Typ 1 (kontextsensitiv), falls
alle Produktionen p ∊ P die folgende Form haben:
uAv::= uwv mit A ∊ N, u,v ∊ N* und w ∊ (N ∪ T)
D.h.
Das Nichtterminalsymbol A kann nur in der Umgebung,
dem „Kontext“ u und v, in w umgesetzt werden.
Dabei muss gelten: w ≠ 
Satz:
Jede kontextfreie Sprache ist auch kontextsensitiv, aber die Umkehrung gilt nicht (siehe Beispiel nächste Folie).
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
18
Technische Universität München
Beispiel: Kontextsensitive Grammatik
Die Sprache L = { akbkck, k  1 } ist kontextsensitiv,
aber nicht kontextfrei.
L wird durch eine Grammatik mit den Produktionsregeln:
S::= ACB | ASCB
CB ::= CX
CX ::= BX
BX ::= BC
BB ::= BY
AB ::= AY
YY ::= Yb
AY ::= Ab
A ::= a
CC ::= Cc
BC ::= Bc
erzeugt.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
19
Technische Universität München
Beispiel (Forts.)
S::= ACB | ASCB
L = { akbkck, k  1 } mit
CB ::= CX
BX ::= BC
AB ::= AY
AY ::= Ab
CC ::= Cc
CX ::= BX
BB ::= BY
YY ::= Yb
A ::= a
BC ::= Bc
Einige Erläuterungen:
• Die ersten zwei Regeln erzeugen Wörter der Form: Ak(CB)k mit k  1
• Die nächsten Regeln sorgen für das Vertauschen von C mit B,
so dass entsteht
AkBkCk ; k  1.
• Schließlich sorgen die letzten Regeln für akbkck ; k  1,
wenn man sie von rechts nach links anwendet.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
20
Technische Universität München
10.4.4 Typ-0 Grammatik, freie, rekursiv aufzählbare Sprachen
Eine Grammatik ist vom Typ 0 (rekursiv aufzählbar (r.a.)), falls
alle Produktionen p ∊ P die folgende Form haben:
v::= w mit v, w ∊ (N ∪ T)*
Die Regelmenge heißt auch Semi-Thue-System.
Mit Typ-0-Regeln kann man die zuvor angegebene Sprache
noch einfacher erzeugen: CB ::= BC
Satz:
Jede kontextsensitive Sprache ist auch Typ 0 Sprache, aber die
Umkehrung gilt nicht.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
21
Technische Universität München
Zusammenfassung der Sprachen der Chomsky-Hierarchie
Die Inklusionen sind echt.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
22
Technische Universität München
10.5 Erkennende Automaten
Für jeden der 4 Grammatik-Typen gibt es eine Klasse von
Automaten, die geeignet sind, um zu analysieren, ob ein Wort w
zu einer Sprache L(G) gehört, die durch die Grammatik G vom Typ i
erzeugt wird.
10.5.1 DFAs und Typ3 Grammatiken
In 10.2 wurde der deterministische endliche Automat (DFA) definiert.
Sei M =(Q, Σ, A, δ, g, q0, F) ein deterministischer, endlicher Automat.
Die von M erkannte Sprache L(M) ist gegeben durch:
L(M) = { w ∊ Σ* | δ*(q0, w) ∊ F}
d.h. die Menge aller Wörter w, bei deren Eingabe der Automat
ausgehend vom Startzustand q0 in einen Endzustand übergeht.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
23
Technische Universität München
Erläuterungen und Bezug zu Typ3 Grammatiken
• Gegeben sei ein DFA M =(Q, Σ, A, δ, g, q0, F) mit der
erkannten Sprache L(M) = { w ∊ Σ* | δ*(q0, w) ∊ F}.
• Der DFA arbeitet als akzeptierender/analysierender Automat,
indem die Zustandsübergangsfunktion δ seriell auf alle Zeichen
des Eingabewortes w angewandt wird.
Gegeben sei eine Typ3 Grammatik G.
Wir bilden kanonisch ab:
• Σ auf T, Q auf N, q0 auf S und δ auf P, also
• sei p ∊ P gegeben mit: Ai-1 ::= aAi, so gilt qi ::= δ(a, qi-1).
• Ist Ai = ε, so geht δ in einen Endzustand aus F über.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
24
Technische Universität München
Bezug zu Typ3 Grammatiken (Forts.)
Um Typ3-Sprachen von DFAs erkennen zu lassen, ist es
nützlich zu fordern, dass die zugrundeliegende Typ3-Grammatik
eine bestimmte Form, eine Normalform, hat, so dass nur einzelne
Zeichen betrachtet werden müssen:
Normalform (nur informell hier)
Eine Produktionsregel der Form A ::= e1e2 ... ekB
kann umgesetzt werden in
A ::= e1B1, B1 ::= e2B2, ... Bk-1 ::= ekBk
mit neuen Nichtterminalsymbolen B1, ..., Bk-1.
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
25
Technische Universität München
Beispiel 1: Erkennender Automat für eine Typ3 Grammatik
Sprache in Normalform
S ::= aS1, A::= bA1
Startzustand S
S1 ::=bS,
A1::= aA
Endzustand F
S ::= cA,
A ::= a
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
26
Technische Universität München
Beispiel 1: Erkennender Automat für eine Typ3 Grammatik
Sprache in Normalform
S ::= aS1, A::= bA1
Startzustand S
S1 ::=bS,
A1::= aA
Endzustand F
S ::= cA,
A ::= a
b
S
S1
a
a
c
A1
b
A
a
F

Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
27
Technische Universität München
Beispiel 1: Erkennender Automat für eine Typ3 Grammatik
Sprache in Normalform
S ::= aS1, A::= bA1
Startzustand S
S1 ::=bS,
A1::= aA
Endzustand F
S ::= cA,
A ::= a
A1
S1
S
A
F
b
S1
a
F

S
a
a
F
A
S1
c
A1
b
A
a
F
b
S
A1

c
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
A
28
Technische Universität München
Beispiel 1: (Forts.)
Gegeben sei das Wort w = a b c b a a,
Der Automat durchläuft beim seriellen Lesen der Zeichen des
Wortes w die Zustände S, S1, S, A, A1, A ,F
b
S
S
S1
a
S1
A
A1

F
F
a
c
a
A1
b
A
a
F

b
c
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
F
S1
S
A
A1
A
29
Technische Universität München
Beispiel 2: Erkennender Automat für Binärzahlen
T = { 0, 1}, N = { D, Z }, S = D
P = { D::= 0; D::= 1Z; Z::= 1Z; Z::= 0Z; Z::= }.
Grammatik liegt in Normalform vor.
D

Z
F
0
F
Z
1
Z
Z
1
F
F
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
Z
1
D
0

0
F

30
Technische Universität München
Beispiel 3: Erkennender Automat für die Sprache L, mit
L = {w ∊ {0,1}* | in w kommen vor jeder 1 mindestens zwei 0 vor}
Der Automat M, der L erkennt, kann wie folgt konstruiert werden:
Vorlesung Algorithmen und Datenstrukturen, WS09/10, C. Eckert
31
Document
Kategorie
Seele and Geist
Seitenansichten
15
Dateigröße
748 KB
Tags
1/--Seiten
melden