View
66
Download
0
Category
Preview:
DESCRIPTION
Formale Sprachen Teil 2. Klaus Becker 2006. Theorie formaler Sprachen. S aAS S bBS S c Aa aA Ab bA Ac ca Ba aB Bb bB Bc cB. Komplexität von Grammatiken Automatenmodelle Zusammenhänge zwischen Grammatiken und Automaten. S (T) T T (T). - PowerPoint PPT Presentation
Citation preview
Formale SprachenTeil 2
Klaus Becker2006
2 Theorie formaler Sprachen
Komplexität von Grammatiken Automatenmodelle Zusammenhänge zwischen
Grammatiken und Automaten
A [BB ]B (CC xDD )B
S (T)T T (T)
S aAS S bBSS cAa aAAb bA Ac caBa aBBb bBBc cB
3 Beispiel: KlammersprachenKorrekt geklammerte Rechenausdrücke:(56 – 34) * 17((34 – 17) * (89 + 11))(((45 – 6) * (67 / 5)) – (6 * 5)) ...
HTML-Dokument:<html> <head> ... </head> <body> <h1>Weiterbildungskurse Informatik</h1> <p>Der Weiterbildungslehrgang Inf....</p> <p>Der Lehrgang besteht ...</p> <p>Der Lehrgang schliesst ...</p> </body></html>
XML-Dokument:<?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>
<type>grammar</type><!--The list of productions.--
><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production><production>
<left>A</left><right>a</right>
</production></structure>
4 Zielsetzung und VorgehensweiseZiel ist es, die Beschreibung von Klammersprachen mit Hilfe von Grammatiken und die Erkennung von Klammersprachen mit Hilfe von Automaten genauer zu untersuchen. Diese Untersuchungen führen direkt zur Theorie über formale Sprachen und Automaten. Um den Arbeits- und Schreibaufwand etwas zu verringern, werden die zu betrachtenden Sprachen zunächst strukturgetreu vereinfacht.
5 Teil 1
Reguläre Sprachen
6 Vereinfachtes HTMLInformelle Beschreibung:Ein vereinfachtes HTML-Dokument besteht aus einem Kopf mit Titelangabe und einem Rumpf mit Abschnitten. Es sind keine Umlaute erlaubt. Es sollen auch keine Tabellen, Links, Bilder etc. integriert werden. Der unten abgebildete HTML-Quelltext ist in diesem Sinne ein vereinfachtes HTML-Dokument.<html><head><title>Weiterbildungskurs Informatik</title> </head><body><p>Der Weiterbildungslehrgang Informatik in Rheinland-Pfalz ist ein Ersatzstudium der Informatik für Lehrerinnen und Lehrer, die bereits eine Lehrbefaehigung in einem naturwissenschaftlichen Fach haben.</p><p>Der Lehrgang besteht aus sechs Wochenkursen, in denen jeweils typische Themen der Informatik bearbeitet werden.</p><p>Der Lehrgang schliesst dann mit einer Pruefung zum Erwerb der Unterrichtserlaubnis fuer das Grundfach Informatik ab.</p></body></html>
7 StrukturanalyseKlammerstruktur:Hier werden verschiedene Sorten von Klammern benutzt. Die verschiedenen Klammersorten können geschachtelt werden, aber nur in einer bestimmten Form. Der Rumpf-Teil hat z. B. die Struktur <body><p>...</p><p>...</p>...<p>...</p></body>. Wir abstrahieren im Folgenden von der Darstellung der Klammern und betrachten Klammerausdrücke der Gestalt [(x)(x)...(x)]. <body><p>Der Weiterbildungslehrgang ... in einem naturwissenschaftlichen Fach haben.</p><p>Der Lehrgang besteht aus ... Themen der Informatik bearbeitet werden.</p><p>Der Lehrgang schliesst ... fuer das Grundfach Informatik ab.</p></body>Klammersprache K3:Das Alphabet von K3 ist die Zeichenmenge { [, ], (, ), x }. Zu K3 gehören alle Wörter über dem Alphabet { [, ], (, ), x }, die mit [ beginnen, dann eine beliebige Anzahl (evtl. auch 0) von Ausdrücken der Gestalt (x) enthalten und mit ] enden.Bsp.: [], [(x)], [(x)(x)], [(x)(x)(x)], ...
8 AufgabeEntwickeln Sie eine (mehrere) Grammatik(en) zur Beschreibung der Klammersprache K3. Entwickeln Sie auch einen (mehrere) endliche Automaten zur Erkennung der Klammersprache K3.
9
Beschreibung und Erkennung von K3
Klammersprache K3:Das Alphabet von K3 ist die Zeichenmenge { [, ], (, ), x }. Zu K3 gehören alle Wörter über dem Alphabet { [, ], (, ), x }, die mit [ beginnen, dann eine beliebige Anzahl (evtl. auch 0) von Ausdrücken der Gestalt (x) enthalten und mit ] enden.Bsp.: [], [(x)], [(x)(x)], [(x)(x)(x)], ...
[q0 q1 q2
q3 q4
]
x
( )
Grammatik G1 für K3:A []A [B]B CB CBC (x)
Grammatik G2 für K3:A [BB ]B (CC xDD )B
Endlicher Automat für K3:
K3GR1.jff
K3GR2.jff
10 Erkennung von K3
[q0 q1 q2
q3 q4
]
x
( )
Grammatik G1 für K3:A []A [B]B CB CBC (x)
Grammatik G2 für K3:A [BB ]B (CC xDD )B
Endlicher Automat für K3:
Beobachtung:Es fällt auf, dass die Grammatik G2 genau das Verhalten des endlichen Automaten A mit Hilfe von Produktionen nachbildet.
A
B
K3GR1.jff
K3GR2.jff
C D
11 AufgabeÖffnen Sie die Datei K3GR2.jff. Lassen Sie JFlap zu dieser Grammatik automatisch einen endlichen Automaten erzeugen: <Convert><Convert Right-Linear Grammar to FA><Show All>.Gehen Sie auch umgekehrt vor und lassen Sie sich von JFlap zum Automaten K3DA1.jff die entsprechende Grammatik erzeugen.
12 AufgabeÖffnen Sie die Datei K3GR1.jff. Lassen Sie JFlap zu dieser Grammatik automatisch einen endlichen Automaten erzeugen: <Convert><Convert Right-Linear Grammar to FA><Show All>. Warum funktioniert das nicht?
13 Aufgabe
1q0 q1
q2
0
Wir betrachten die Sprache der Binärzahlen. Entwickeln Sie eine Grammatik zu dieser Sprache, die das Verhalten des gezeigten endlichen Automaten mit Hilfe von Produktionen nachbildet. Testen Sie Ihren Lösungsvorschlag mit Hilfe von JFlap.
10
14 AufgabeWir betrachten die Sprache der Binärzahlen.Versuchen Sie jetzt, umgekehrt zu einer Grammatik für diese Sprache einen entsprechenden endlichen Automaten zu entwickeln. Testen Sie Ihren Lösungsvorschlag mit Hilfe von JFlap. Was fällt hier auf?
A 0A 1A 1BB 0BB 1BB 0B 1
15 Rechtlineare GrammatikEine Produktion heißt rechtslinear genau dann, wenn auf der linken Seite ein Nichtterminalsymbol steht und die rechte Seite folgende Gestalt hat: - ein Terminalsymbol gefolgt von einem Nichtterminalsymbolen oder- ein Terminalsymbol. alternativ:- ein Terminalsymbol gefolgt von einem Nichtterminalsymbolen oder- das leere Wort.Eine Grammatik heißt rechtslinear / regulär genau dann, wenn alle Produktionen der Grammatik rechtslinear sind. Beispiele für rechtslineare Produktionen:A 0 A 1BB 0 B 1B 0B B 1B
Beispiele für rechtslineare Produktionen:A 0C C A 1BB 0D B 1D D B 0B B 1B
Beispiele für nicht-rechtslineare Produktionen:A 0B1 A A1
16 ÄquivalenzsatzSatzZu jedem endlichen Automaten gibt es eine rechtslineare Grammatik, mit der die Sprache des Automaten erzeugt werden kann.
Entsprechende Grammatik:A 1B A 0CB 0B B 1B B C 0D C 1D C D 0D D 1D
Endlicher Automat:
Idee: Zu jedem Zustandsübergang wird eine entsprechende Produktion gebildet. Zu jedem Endzustand wird eine entsprechende Produktion mit dem leeren Wort als rechter Seite hinzugefügt.
1q0 q1
q2
0
10
10 q3
10
A
B
C D
17 Schwierigkeit bei der UmkehrungBei der Umwandlung einer rechtslinearen Grammatik in einen endlichen Automaten kann ein sog. nichtdeterministischer Automat entstehen. Von einem Zustand aus können bei gleicher Eingabe Übergänge in verschiedene Zustände erfolgen.
Nichtdeterministischer Endlicher Automat:
1q0 q2
q1
10
10
Rechtslineare GrammatikA 1B A 0C A 1C C B 0B B 1BB 0D B 1D D
q310
A
B
Nicht-determinismu
sC
D
18
Nichtdeterministischer Endlicher Automat:
ÄquivalenzsatzSatzZu jeder rechtslinearen Grammatik gibt es einen nichtdeterministischen endlichen Automaten, der die von der Grammatik erzeugte Sprache erkennt.
Idee: Man geht wie oben beschrieben vor.
1q0 q2
q1
10
10
Rechtslineare GrammatikA 1B A 0C A 1C C B 0B B 1BB 0D B 1D D
q310
A
B
Nicht-determinismu
sC
D
19 AufgabeÖffnen Sie die Datei BinZahlNA1.jff. Dieser nichtdeterministische Automat erkennt die Sprache der Binärzahlen. Lassen Sie diesen Automaten verschiedene Wörter verarbeiten (z. B. 1001). Machen Sie sich hieran die „Arbeitsweise“ eines nichtdeterministischen Automaten klar.
20 AufgabeÖffnen Sie die Datei BinZahlNA1.jff. Dieser nichtdeterministische Automat erkennt die Sprache der Binärzahlen. Lassen Sie JFlap diesen Automaten in einen deterministischen Automaten umwandeln: <Convert to DFA>.
21 ÄquivalenzsatzSatzZu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Idee: Jede Menge von Zuständen des NEA ergibt einen Zustand des DEA. Nicht benötigte Zustände des DEA werden weggelassen.
22 ÄquivalenzsatzSatzZu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. Bemerkung:Da jeder deterministische Automat auch ein nichtdeterministischer Automat ist, gilt trivialerweise auch die Umkehrung: Zu jedem deterministischen Automaten gibt es einen nichtdeterministischen Automaten, der dieselbe Sprache erkennt.Folgerung:Deterministische und nichtdeterministische Automaten sind gleich mächtige Sprachverarbeitungsmodelle / erkennen dieselben Sprachen.
23 AufgabeÖffnen Sie die Datei BinZahlDA2.jff. Dieser deterministische Automat erkennt die Sprache der Binärzahlen. Lassen Sie JFlap diesen Automaten in einen regulären Ausdruck umwandeln: <Convert FA to RE>. Exportieren Sie anschließend diesen regulären Ausdruck und lassen Sie ihn wieder in einen endlichen Automaten umwandeln. Was zeigen diese Experimente?
24 ÄquivalenzsatzSatz (Kleene)Jede durch einen endlichen Automaten erkennbare Sprache kann durch einen regulären Ausdruck beschrieben werden.Jede durch einen regulären Ausdruck beschreibbare Sprache kann durch einen endlichen Automaten erkannt werden.
25 Reguläre SprachenEine Sprache heißt regulär genau dann, wenn sie durch einen regulären Ausdruck dargestellt werden kann.
Bemerkung:Eine Sprache ist regulär genau dann, wenn sie- durch einen regulären Ausdruck dargestellt werden kann /- von einem deterministischen endlichen Automaten erkannt werden kann /- von einem nichtdeterministischen endl. Automaten erkannt werden kann /- von einer rechtslinearen Grammatik erzeugt werden kann.Die genannten Sprachbeschreibungs- bzw. Sprachverarbeitungskonzepte sind demnach alle gleich mächtig.
26
27 Teil 2
Kontextfreie Sprachen
28 RechenausdrückeRechenausdrücke können Klammern enthalten, mit denen die Reihenfolge von Berechnungen genau festgelegt wird.
Beispiele für korrekt geklammerte Rechenausdrücke:((56 – 34) * 17)((34 – 17) * (89 + 11))... Beispiele für inkorrekt geklammerte Rechenausdrücke:)13 + 12) * 4((25 – 16) * 7...
29 Vereinfachte RechenausdrückeInformelle Beschreibung:Wir betrachten nur Rechenterme, die vollständig geklammert sind. Jede Rechenoperation muss umklammert werden – wie z. B. bei (12+3). Eine Rechenoperation bezieht sich auf Zahlen oder Rechenterme – wie z. B. bei ((13 – 7) * 4). Rechenterme können beliebig komplex verschachtelt werden – wie z. B. bei (((45 – 6) * (67 / 5)) – (6 * 5)).Klammerstruktur:Zu jeder öffnenden Klammer muss es eine passend folgende schließende Klammer geben. Lässt man die eigentlichen Rechnungen weg, so ergeben sich Klammerausdrücke der Gestalt ((()())()).
Klammersprache:Das Alphabet der Sprache ist die Zeichenmenge { (, ) }. Zur Sprache gehören alle Wörter über dem Alphabet { (, ) }, die zu jeder öffnenden Klammer die passende schließende Klammer haben.Bsp.: (), (()), (()()), ..., ((())()(()(()()))), ...
30 AufgabeWir vereinfachen die Klammersprache weiter (s. u.). Versuchen Sie, eine Grammatik zur Beschreibung von K2 sowie einen endlichen Automaten zur Erkennung von K2 zu entwickeln.
Klammersprache K2:Das Alphabet von K2 ist die Zeichenmenge { (, ) }. Zu K2 gehören alle Wörter über dem Alphabet { (, ) }, die nach einer beliebigen Anzahl öffnender Klammern genau dieselbe Anzahl schließender Klammern enthält. Bsp.: (), (()), ((())), (((()))), ...Bem.: Statt ( bzw. ) benutzt man häufig die Zeichen a bzw. b. Bsp.: Statt ((())) schreibt man aaabbb.
31
Beschreibung von Klammerausdrücken
Eine Grammatik für K2 lässt sich leicht angeben:
Klammersprache K2:Das Alphabet von K2 ist die Zeichenmenge { (, ) }. Zu K2 gehören alle Wörter über dem Alphabet { (, ) }, die nach einer beliebigen Anzahl öffnender Klammern genau dieselbe Anzahl schließender Klammern enthält. Bsp.: (), (()), ((())), (((()))), ...
Grammatik:S (A) A A (A)
Schwieriger ist es dagegen, einen endlichen Automaten zur Erkennung von K2 anzugeben.
32
Erkennung von Klammerausdrücken
Problem: Gesucht ist ein endlicher Automat, der die Sprache K2 der Klammerausdrücke erkennt.
EAok(((())))
Fehler((())
Schwierigkeit: Der endliche Automat (EA) muss sich merken, wie viele Klammern geöffnet sind. Zum Merken hat ein endlicher Automat nur Zustände zur Verfügung. Mit endlich vielen Zuständen kann man sich aber nicht beliebig viele geöffnete Klammern merken.
33 Die Sprache {anbn|n aus IN}SatzEs gibt keinen endlichen Automaten, der die Klammersprache L = {anbn | n 1} akzeptiert.
Wir betrachten eine Sprache, die die „Klammer-auf-Klammer-zu“-Struktur abstrahierend beschreibt. Diese Sprache besteht aus den Wörtern über dem Alphabet {a, b}, bei denen auf eine bestimmte Anzahl von a´s („Klammer auf“) genau dieselbe Anzahl von b´s („Klammer zu“) folgt.Also: L = {ab, aabb, aaabbb, aaaabbbb, ...} Im Folgenden soll nachgewiesen werden, dass kein noch so komplizierter oder spitzfindig ausgedachter Automat in der Lage ist, die Klammersprache L zu akzeptieren. Wir benutzen hierzu – wie in der Informatik üblich – ein mathematisches Beweisverfahren, also eine exakte, logisch zweifelsfreie Argumentationskette.
34 BeweisAnnahme: Es gibt einen endlichen Automaten A, der L akzeptiert.A hat endliche viele Zustände. m bezeichne die Anzahl dieser Zustände. (Zur Illustration der Beweisidee gehen wir hier von m = 15 aus.) Wir betrachten jetzt ein Wort w = akbk mit k > m. (Zur Illustration der Beweisidee gehen wir hier von k = 16 aus. D. h., w = a16b16 besteht aus 16 a´s gefolgt von 16 b´s.) Das Wort w hat dann einen Anfangsteil, der mehr a‘s enthält als A Zustände hat. Bei der Verarbeitung des a-Anfangsteils von w muss zwangsläufig mindestens ein Zustand von A mindestens zweimal durchlaufen werden. (Zur Illustration der Beweisidee gehen wir hier davon aus, dass der Zustand, der mit dem dritten a erreicht wird, auch wieder mit dem siebten a erreicht wird.). Somit ist eine Schleife entstanden, die erst mit Beginn des b-Endteils wieder verlassen wird.
35 BeweisDie folgende Grafik soll die Situation verdeutlichen:- A hat m Zustände (hier m = 15).- A akzeptiert w = akbk mit k > m (hier w = a16b16).- Bei d. Verarbeitung des a-Anfangsteils von w wird ein Zustand mindestens zweimal durchlaufen werden (hier wird q3 insgesamt 4 mal durchlaufen).Weitere spezielle Eigenschaften von A, die in der Grafik zu erkennen sind, sind für den Beweisgang nicht von Bedeutung.
Grafik entnommen aus: http://hsg.region-kaiserslautern.de/faecher/inf/material/automaten/anbn/index.php
36 BeweisDer a-Anfangsteil lässt sich zerlegen in die Teile „vor der Schleife“, „in der Schleife“, „nach der Schleife“. Es gilt: w = akbk = ap(aq)iarbk mit p+q*i+r=k (hier: w = a16b16 = a3a4a4a4a1b16). Die Zahl i beschreibt die Anzahl der Schleifendurchläufe beim gegebenen w.
(In der Grafik erkennt man direkt, dass A auch
w´ = a4b16 oderw´´ = a8b16 akzeptiert.) Grafik entnommen aus: http://hsg.region-kaiserslautern.de/faecher/inf/material/automaten/anbn/index.php
37 BeweisWir betrachten ein w´ = ap(aq)jarbk mit einem j, das von i verschieden ist – z. B. j = i+1. Das neue Wort w´ hat dann mehr a´s als b´s. Jetzt gilt:- w´ wird von A akzeptiert (da w´ genau wie w den AZ in einen EZ überführt).- w´ gehört nicht zur Sprache L (da w´ mehr a’s als b’s enthält).A akzeptiert also ein Wort, das nicht zur Sprache L = {anbn | n 1} gehört. Das ist ein Widerspruch zur Annahme, dass A die Sprache L akzeptiert. Die Annahme muss daher falsch sein. Die Aussage des Satzes muss folglich wahr sein.
38 FolgerungenEs gibt Sprachen (wie z. B. die gezeigte Klammersprache), die- nicht von einem endlichen Automaten erkannt werden können,- nicht mit einer regulären Grammatik beschrieben werden können,- nicht mit einem regulären Ausdruck beschrieben werden können.Dieses Ergebnis zeigt insbesondere eine prinzipielle Grenze von endlichen Automaten auf: Sie sind nicht in der Lage, komplexere Sprachen wie z. B. eine Klammersprache zu erkennen.
39 ZielsetzungUm auch Klammersprachen erkennen zu können, muss das bisher betrachtete Automatenkonzept erweitert werden.Ziel der folgenden Betrachtungen ist es, ein erweitertes Automatenmodell und seine Spracherkennungsmöglichkeiten zu erkunden.
40 AufgabeStarten Sie das Programm „Automaton Simulator“ und öffnen Sie die Datei „Klammersprache1“ im Verzeichnis „MaterialAutomatonSimulator“.Lassen Sie den gezeigten erweiterten Automaten verschiedene „abstrakte Klammerausdrücke“ wie aabb oder aaab oder aabbbb verarbeiten. Versuchen Sie herauszufinden, wie Spracherkennung mit diesem erweiterten Automaten funktioniert.
41 Ein Automat mit Zusatzspeicher
öffnen
aabb
a
öffnen
aabb
aa
öffnen
aabb
a
schliessen
aabb
schliessen
Keller
Der Automat wird um einen Zusatzspeicher (Keller) erweitert, mit dem er sich die „öffnenden“ Klammern merken kann.
push a
push a
pop pop Kellerautomat
42 Keller / StapelEin Keller / Stapel ist ein Speicher, der nach dem LIFO-Prinzip (last in, first out) arbeitet.:
push(...) top pop
... auf den Stapel
legen
liefert das oberste
Stapelelement
das oberste Stapelelement
entfernen
43 Kellerautomat – Version 1Ein Kellerautomat ist ein um einen Kellerspeicher erweiterter Automat: - Der Kellerautomat verfügt zusätzlich über ein Kelleralphabet, das alle Zeichen enthält, die im Keller gespeichert werden können. - Die Zustandsübergänge hängen nicht nur von den Eingaben, sondern auch vom jeweils obersten Kellerzeichen ab.- Bei jedem Übergang wird eine Kelleroperation durchgeführt.
Oberstes Kellerzeichen / Eingabezeichen: Kelleroperation
Beim vorliegenden Kellerautomaten wird ein Wort genau dann akzeptiert, wenn der Keller nach Abarbeitung des Wortes leer ist.
44 AufgabeStarten Sie das Programm „JFLAP“ und öffnen Sie die Datei „Klammersprache1“ im Verzeichnis „MaterialJFlap“.Lassen Sie den gezeigten erweiterten Automaten verschiedene „abstrakte Klammerausdrücke“ wie aabb oder aaab oder aabbbb verarbeiten. Was ist anders bei diesem Kellerautomaten?
45 Kellerautomat – Version 2
Z
q0: öffnen aabb
aZ
q0: öffnen aabb
aaZ
q0: öffnen aabb
aZ
q1: schliessen
aabb
aabb q2: korrekt
Endzustand
Anfangszustand
Aktueller Zustand
Oberstes Kellerzeichen
Leere Eingabe
Z
Z Kellerstart-zeichen
q1: schliessen
a, Z; aZ a, a; aa b, a;
b, a; , Z; Z
Oberstes Kellerzeichen
Eingabe-zeichen
neue Kellerzeichen
46 Kellerautomat – Version 2Ein Kellerautomat ist ein um einen Kellerspeicher erweiterter Automat: - Der Kellerautomat verfügt zusätzlich über ein Kelleralphabet, das alle Zeichen enthält, die im Keller gespeichert werden können. Hierzu gehört auch das Kellerstartzeichen, das zu Beginn im Keller gespeichert ist.- Die Zustandsübergänge hängen nicht nur von den Eingaben, sondern auch vom jeweils obersten Kellerzeichen ab.- Bei jedem Übergang wird eine Kelleroperation durchgeführt. Das oberste Kellerzeichen wird dabei durch eine (ggf. leere) Folge „neuer“ Zeichen ersetzt. - Oft erlaubt man zusätzlich, dass auch spontane Übergänge stattfinden können (d. h. dass leere Eingaben verarbeitet werden) und dass Zustandsübergänge nicht-deterministisch erfolgen können.
47 Kellerautomat – Version 2
Beim vorliegenden Kellerautomat wird ein Wort genau dann akzeptiert, wenn sich der Kellerautomat nach Abarbeitung des Wortes in einem Endzustand befindet.
Eingabezeichen (evtl. leer) , oberstes Kellerzeichen ; Folge von neuen Kellerzeichen
48 AufgabenEntwickeln Sie einen Kellerautomaten, der verallgemeinerte Klammerausdrücke der folgenden Gestalt erkennt. Die Sprache dieser Klammerausdrücke wird im Folgenden K2´genannt. ((x)(x)), (((x)((x)))(x))
Entwickeln Sie einen Kellerautomaten, der vereinfachte Rechenausdrücke mit Binärzahlen erkennt.Bsp.:((100 – 11) * 101)((11010 – 101) * (111 + 1100))
49 Ein Blick auf die GrammatikenWir betrachten Klammersprachen im Vergleich:
Klammersprache K3:K3 = { [], [(x)], [(x)(x)], [(x)(x)(x)], ... }Alphabet: { [, ], (, ), x }. Produktionen:A []A [B]B CB CBC (x)
Klammersprache K2´:K2´ = {((x)(x)), (((x)((x)))(x))... }Alphabet: { (, ), x }. Produktionen:A BA BAB (C)B (A)C x
Anhand der Grammatiken kann man hier – zumindest auf den ersten Blick – nicht unterscheiden, welche der beiden Sprachen komplexer ist.Die Situation ändert sich, wenn man zur ersten Sprache eine einfachere Grammatik angibt.
50 Ein Blick auf die GrammatikenWir betrachten Klammersprachen im Vergleich:
Klammersprache K3:K3 = { [], [(x)], [(x)(x)], [(x)(x)(x)], ... }Alphabet: { [, ], (, ), x }. Produktionen:A [BB ]B (CC xDD )B
Klammersprache K2´:K2´ = {((x)(x)), (((x)((x)))(x))... }Alphabet: { (, ), x }. Produktionen:A BA BAB (C)B (A)C x
Die Grammatik zur Sprache K3 ist rechtslinear, während die Grammatik zur Sprache K2´ eine komplexere Struktur hat. Auf der rechten Seite einer Produktion stehen hier komplexere Wörter aus Terminal- und Nichtterminalsymbolen.
51 Kontextfreie Grammatiken
Beispiel für eine kontextfreie Grammatik:A BA BAB (C)B (A)C x
Eine Produktion heißt kontextfrei genau dann, wenn für jede Regel gilt: - Auf der linken Seite steht ein Nichtterminalsymbol.- Auf der rechten Seite steht ein beliebiges Wort bestehend aus Terminal- und Nichtterminalsymbolen.Eine Grammatik heißt kontextfrei genau dann, wenn alle Produktionen der Grammatik kontextfrei sind. Eine Sprache heißt kontextfrei genau dann, wenn sie mit Hilfe einer kontextfreien Grammatik beschrieben werden kann.
52
Suche nach einfachen Grammatiken
Bemerkung:Zur Beschreibung einer Sprache lassen sich oft viele verschiedene Grammatiken angeben. Die „einfachste“ mögliche Grammatik legt den Komplexitätsgrad der Sprache fest.Beispiel: K3 ist regulär, da es eine reguläre Grammatik zu dieser Sprache gibt.
Klammersprache K3:K3 = { [], [(x)], [(x)(x)], [(x)(x)(x)], ... }Alphabet: { [, ], (, ), x }. Produktionen:A []A [B]B CB CBC (x)
Klammersprache K3:K3 = { [], [(x)], [(x)(x)], [(x)(x)(x)], ... }Alphabet: { [, ], (, ), x }. Produktionen:A [BB ]B (CC xDD )B
53 AufgabeGeben Sie die Grammatik zur Klammersprache K2´ in JFlap ein. Lassen Sie JFlap dann diese Grammatik in einen nichtdeterministischen Kellerautomaten („convert CFG to PDA (LL)“) übersetzen. Testen Sie diesen Kellerautomaten, indem Sie ihn das Wort ((x)((x))) überprüfen lassen. („fast run“). Aus dem Ablaufprotokoll („trace“) lässt sich erkennen, wie der Kellerautomat arbeitet.
54 ÄquivalenzsatzSatzEine Sprache ist kontextfrei genau dann, wenn sie von einem nichtdeterministischen Kellerautomaten erkannt wird.
Beweis: StudiumBeachte:Mit deterministischen Kellerautomaten kann man nur eine echte Teilmenge der kontextfreien Sprachen erkennen.
55 Teil 3
Kontextsensitive und allgemeine Sprachen
56 XMLJFlap benutzt – wie viele andere Programme auch – die standardisierte Dokumentenbeschreibungssprache XML zur Darstellung der abzuspeichernden Strukturen. <?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>
<type>grammar</type><!--The list of productions.--><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production><production>
<left>A</left><right>a</right>
</production></structure>
57 XMLDie Extensible Markup Language (engl. für „erweiterbare Auszeichnungs-Sprache“), abgekürzt XML, ist ein Standard zur Erstellung maschinen- und menschenlesbarer Dokumente in Form einer Baumstruktur, der vom World Wide Web Consortium (W3C) definiert wird. Siehe: http://de.wikipedia.org/wiki/XML<?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>
<type>grammar</type><!--The list of productions.--><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production> ...</structure>
58 XMLXML benutzt Tags zur Strukturierung von Dokumenten. Im Gegensatz zu HTML können hier beliebige Tags zur Strukturierung eingeführt werden. Wie bei HTML muss zu jedem Anfangstag ein passendes Endtag folgen. <?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>
<type>grammar</type><!--The list of productions.--><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production><production>
<left>A</left><right>a</right>
</production></structure>
59 Vereinfachtes XMLInformelle Beschreibung:Ein vereinfachtes XML-Dokument besteht aus ineinandergeschachtelten Elementen. Ein Element besteht aus einem Anfangstag, einem Bezeichner oder einer Elementliste und einem passenden Endtag. Ein Bezeichner besteht aus beliebigen alphanumerischen Zeichen.Der unten abgebildete XML-Quelltext ist in diesem Sinne ein vereinfachtes XML-Dokument.<structure>
<type>grammar</type><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production><production>
<left>A</left><right>a</right>
</production></structure>
60 StrukturanalyseKlammerstruktur:Hier werden beliebig konstruierbare Sorten von Klammern benutzt. Die verschiedenen Klammersorten können beliebig geschachtelt werden. Es ist nur darauf zu achten, dass entsprechende Klammern auch zusammenpassen.
<structure><type>grammar</type><production>
<left>S</left><right>a</right>
</production><production>
<left>S</left><right>A</right>
</production><production>
<left>A</left><right>a</right>
</production></structure>
Im Folgenden betrachten wir den Aspekt, dass beliebig konstruierbare Klammern zusammenpassen.Bsp. für „wohlgeformte“ Klammerausdrücke:<type>grammar</type><left>S</left><right>a</right>Bsp. für „nicht-wohlgeformte“ Klammerausdr.:<right>grammar</thgir><type>grammar<type><left>S</right>
61 AufgabeWir vereinfachen die Klammersprache weiter (s. u.). Die unten gezeigte Grammatik beschreibt diese Sprache K1. Testen Sie dies zunächst mit Hilfe verschiedener Beispiele und Gegenbeispiele.Schauen Sie sich Ableitungen von Wörtern, die zu K1 gehören, genauer an und versuchen Sie zu verstehen, wie die Grammatik die zu K1 gehörenden Wörter erzeugt.
S aAS S bBSS cAa aAAb bA Ac caBa aBBb bBBc cB
Klammersprache K1:Das Alphabet von K1 ist die Zeichenmenge {a, b, c}. Zu K1 gehören alle Wörter über dem Alphabet {a, b, c}, die mit einem beliebigen Wort w über dem Alphabet {a, b} beginnen, die dann das Trennsymbol c enthalten und anschließend mit genau demselben Wort w enden.Bsp.: c, aca, abcab, bacba, abbacabba, ...
62 AufgabeDie Sprache LMyXML soll vereinfachte XML-artige Ausdrücke beschreiben. - Jedes zu L gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen.- Anfangs- und Endtag sollen identisch sein.- Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen.- Der Text zwischen den Anfangs- und End-Tag besteht nur aus den Buchstaben a, b und c bestehen. Beispiele:<ab>acaa<ab>...Entwickeln Sie ausgehende von der gezeigten Grammatik für K1 eine Grammatik für LMyXML.
63 Eine Grammatik für MyXMLS <aAT>S <bBT>T aATT bBTT MAa aAAb bAAM MaBa aBBb bBBM MbM >NM aMM bMM cMM <
MyXML.jff
64 Grammatiken im VergleichA BA BAB (x)B (A)
S aAS S bBSS cAa aAAb bA Ac caBa aBBb bBBc cB
Bisher stand auf der linken Seite einer Produktion immer ein einzelnes Nicht-Terminalsymbol. Die jetzt betrachteten Grammatiken enthalten ganze Wörter mit Terminal- und Nichtterminalsymbolen auf der linken Seite.
K1.jff
KlammerX.jff
S <aAT>S <bBT>T aATT bBTT MAa aAAb bAAM MaBa aBBb bBBM MbM >NN aNN bNN cNN <MyXML.jff
65 Allgemeine ProduktionenEine Produktion u v heißt allgemein genau dann, wenn u und v beliebige Wörter aus Terminal- und Nichtterminalsymbolen sind.Eine Produktion u v heißt (Wortlängen-)monoton genau dann, wenn u und v beliebige Wörter aus Terminal- und Nichtterminalsymbolen sind und wenn v mindestens so lang wie u ist.Eine Produktion u v heißt kontextsensitiv genau dann, wenn diese Produktion die Gestalt xAy xwy hat, wobei - A ein Nichtterminalsymbol ist und- x und y beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind. - w ein beliebiges, nicht-leeres Wort bestehend aus Terminal- und Nichtterminalsymbolen ist.Beachte: Bei einer kontextsensitiven Produktion xAy xwy darf das Nichtterminalsymbol A nur dann durch das Wort w ersetzt werden, wenn A im Kontext x..y steht. Beachte, dass die Wörter x und y auch das leere Wort sein können.
66
Monotone und kontextsensitive Prod.
N aNallgemein, monoton, kontextsensitiv, kontextfrei, rechtslinearS bBSallgemein, monoton, kontextsensitiv, kontextfrei, nicht rechtslinearAa aAallgemein, monoton, nicht kontextsensitiv, nicht kontextfrei, nicht rechtslinear
S <aAT>S <bBT>T aATT bBTT MAa aAAb bAAM MaBa aBBb bBBM MbM >NN aNN bNN cNN <
MyXML.jff
Beachte: Jede rechtslineare Produktion ist kontextfrei.Jede kontextfreie Produktion ist kontextsensitiv....
67
Monotone / kontextsensitive Sprachen
Eine Grammatik heißt allgemein genau dann, wenn alle Produktionen allgemein sind.Eine Grammatik heißt (Wortlängen-)monoton genau dann, wenn entweder alle Produktionen monoton sind, oder wenn alle Produktionen monoton sind außer S , sofern das Startsymbol S nie auf der rechten Seite einer Produktion vorkommt. Eine Grammatik heißt kontextsensitiv genau dann, wenn entweder alle Produktionen kontextsensitiv sind, oder wenn alle Produktionen kontextsensitiv sind außer S , sofern das Startsymbol S nie auf der rechten Seite einer Produktion vorkommt. Eine Sprache heißt monoton / kontextsensitiv genau dann, wenn sie von einer monotonen / kontextsensitiven Grammatik erzeugt wird.
68
Monotone und kontextsensitive Prod.
S aAS S bBSS cAa aAAb bA Ac caBa aBBb bBBc cb
S NaAS S NbBSS NcANa NaAANb NbA ANc NcNaBNa NaBBNb NbBBNc NcNbNa a Nb bNc c
ANa ADAD CDCD CNaCNa ANa
Das Beispiel soll verdeutlichen, wie man von monotonen Produktionen zu kontextsensitiven Produktionen gelangt.
ANb AFAF EFEF ENbENb ANb
ANc AHAF GHGH GNcGNc ANc
SatzJede kontextsensitive Sprache ist monoton. Jede monotone Sprache ist auch kontextsensitiv. D.h.: Zu einer monotonen Sprache lässt sich eine kontextsensitive angeben, die diese Sprache erzeugt.
69 MyXMLDie Sprache MyXML ist- allgemein (klar)- monoton (offensichtlich)- kontextsensitiv (nach Satz)
Eine Grammatik für MyXML:S <aAT>S <bBT>T aATT bBTT MAa aAAb bAAM MaBa aBBb bBBM MbM >NN aNN bNN cNN <
MyXML.jff
70 MyXMLDie Sprache MyXML ist nicht kontextfrei. Um dies nachzuweisen, muss man zeigen, dass es keine kontextfreie Grammatik gibt, die MyXML erzeugt. Man zeigt dies, indem man nachweist, dass es keinen Kellerautomaten gibt, der diese Sprache akzeptiert. (Beweis: Studium)
Eine Grammatik für MyXML:S <aAT>S <bBT>T aATT bBTT MAa aAAb bAAM MaBa aBBb bBBM MbM >MM aMM bMM cMM <
MyXML.jff
71
Erweiterung des Automatenmodells
Zielsetzung:Ziel ist es, ein Automatenmodell zu entwickeln, das auch komplexere Sprachen (wie kontextsensitive / allgemeine Sprachen) erkennen kann. Vorgehensweise:Wir betrachten zunächst wieder die Sprache K1 / Lwcw der Wörter der Gestalt wcw, wobei w ein beliebiges Wort über {a, b} ist. Zunächst testen wir ein neues Maschinenmodell und analysieren dann seine Arbeitsweise.
72 AufgabeStarten Sie das Programm „JFlap“ und öffnen Sie die Datei „wcwTM“ im Verzeichnis „MaterialJFlap“.Lassen Sie den gezeigten erweiterten Automaten folgende Wörter verarbeiten: aabcaab, abbacabba, c, aacaab, aabcaa, ... Wie arbeitet diese Maschine?
73 TuringmaschinenEine Turingmaschine ist ein Automat, der zustandsabhängig Zeichen bearbeiten kann, die sich auf einem (nach links und rechts unbegrenzten) Band befinden. Die Turingmaschine verfügt hierzu über einen Schreib-/Lesekopf, der sich auf dem Band in beide Richtungen bewegen kann und zustandsabhängig die Bandbeschriftung verändern kann.
Aktueller ZustandBand mit
aktueller Beschriftung
Schreib-/Lesekopf
Zustandsbasierte
Verarbeitungseinheit
74 Arbeitsweise der Turingmaschine- Die Turingmaschine befindet sich zu Beginn in einem Startzustand.- Die Turingmaschine liest das Zeichen aus der Zelle, auf dem sich der Schreib-/Lesekopf befindet, schreibt ein neues Zeichen in die Zelle und bewegt den Schreib-/Lesekopf dann nach rechts oder links bzw. stoppt. - Die Turingmaschine darf für Zwischenergebnisse zusätzliche Zeichen verwenden, die nicht in den zu analysierenden Wörtern vorkommen.- Ein Wort wird genau dann akzeptiert, wenn sich die Turingmaschine nach Abarbeitung des Wortes in einem Endzustand befindet.
Gelesenes Zeichen; Geschriebenes Zeichen, Kopfbewegung
75 AufgabeEntwickeln Sie eine Turingmaschine, die die Sprache L = {anbn | n 1} akzeptiert.Entwerfen und testen Sie eine Turingmaschine, die die Sprache L = {anbncn| n 0} akzeptiert.
76 AufgabeZeigen Sie, dass die Sprache MyXML mit Hilfe einer Turingmaschine erkannt werden kann.Die Sprache MyXML kann sogar mit Hilfe einer sog. linear beschränkten Turingmaschine erkannt werden. Eine linear beschränkte Turingmaschine ist eine Turingmaschine, bei der die Eingabe durch Randmarkierungen # und # eingeschlossen wird. Die Turingmaschine darf bei der Bearbeitung diese Markierungen weder überschreiten noch überschreiben.
77 ÄquivalenzsatzSatzEine Sprache ist allgemein genau dann, wenn sie von einer deterministischen (oder nichtdeterministischen) Turingmaschine erkannt wird.
SatzEine Sprache ist kontextsensitiv genau dann, wenn sie von einer linear beschränkten nichtdeterministischen Turingmaschine erkannt wird.
Bemerkung:Deterministische und nichtdeterministische Turingmaschinen sind gleich mächtig.
78 Chomsky-HierarchieKlassifikation von Sprachen (nach Noam Chomsky / 1958)
Typ Grammatik äquivalenter Automat0 allgemein (nicht)deterministische Turingmaschine1 kontextsensitiv nichtdet. linear beschr. Turingmaschine2 kontextfrei nichtdeterministischer Kellerautomat3 regulär (nicht)deterministischer endl. Automat
79 Teil 4
Exkurs: natürliche Sprachen
80 Noam ChomskyNoam Chomsky hat die Darstellung natürlicher Sprachen formalisiert. Die Neuerung war, die einzelsprachlichen Ausdrücke mit Hilfe einer Metasprache rekursiv zu definieren. Die aus der Metasprache abgeleiteten Klassen von Grammatiken können in eine Hierarchie eingeteilt werden, die heute Chomsky-Hierarchie genannt wird. Seine Arbeit stellt einen wichtigen Meilenstein für die Linguistik dar. Formale Sprachen und die Chomsky-Hierarchie spielen auch in der Informatik eine wichtige Rolle, insbesondere in der Komplexitätstheorie und im Compilerbau.Zusammen mit den Arbeiten Alan Turings begründen sie einen eigenen Bereich in der Mathematik und machen strukturelle Bereiche und Formalismen natürlicher Sprachen einer mathematischen Betrachtung zugänglich, unter anderem mit dem Ergebnis, dass maschinelle Übersetzungen prinzipiell möglich sind.Vielen Forschern innerhalb der Computerlinguistik gelten Chomskys Theorien, insbesondere die Generative Transformationsgrammatik und seine Government and Binding-Ansätze, allerdings seit ungefähr 1980 zwar als bedeutende Pionierleistung, jedoch als heute veraltet, insofern sie sich auf natürliche Sprachen beziehen - im Gegensatz zu Programmiersprachen und anderen formalen Sprachen, wo seine Formalismen weiterhin mit Gewinn verwendet werden können.(siehe: http://www.philosophenlexikon.de/chomsky.htm)
81 Sprache und ihre VerwendungNatürliche Sprachen sind Zeichensysteme, die u. a. für Kommunikation genutzt werden.
82 Syntax, Semantik, PragmatikAspekte natürlicher Sprachen:
Pragmatik: Lehre von der Verwendung sprachlicher Konstrukte in Handlungssituationen Beziehung zwischen Zeichen und Zeichenbenutzer
Semantik: Bedeutungslehre Beziehung zwischen Zeichen und Bezeichnetem
Syntax: Lehre vom SatzbauAnordnung der Zeichen
83 Eine einfache Grammatik<S> ::= <NP> <VP>Ein Satz besteht aus einer Nominalphrase und einer Verbalphrase.
<NP> ::= <N> | <A> <N> | <N> <PP>Eine Nominalphrase muss immer aus einem Nomen bestehen, welchem unter Umständen ein Artikel vorangestellt ist. Ferner kann dem Nomen eine oder mehrere Präpositionalphrasen nachgestellt sein.
<VP> ::= <V> | <V> <NP> | <VP> <PP>Eine Verbalphrase besteht aus einem Verb, dem eine Nominal- oder Präpositionalphrase nachgestellt sein kann.
<PP> ::= <P> <NP>Eine Präpositionalphrase besteht aus einer Präposition und einer Nominalphrase.
<A> ::= der | die | das | dem | ein | einem | ...<P> ::= mit | in | ...<N> ::= Anna | Kuh | Park | Fernglas | ...<V> ::= betrachtet | ...
(nach U. Schöning: Ideen der Informatik. Oldenbourg 2002)
84 Test der Grammatik
<S> <NP> <VP> <N> <VP> <N> <VP> Anna <VP> Anna <VP> <PP> Anna <V> <NP> <PP> Anna betrachtet <NP> <PP> Anna betrachtet <A> <N> <PP> Anna betrachtet die <N> <PP> Anna betrachtet die Kuh <PP> Anna betrachtet die Kuh <P> <NP> Anna betrachtet die Kuh mit <NP> Anna betrachtet die Kuh mit <A> <N> Anna betrachtet die Kuh mit einem <N> Anna betrachtet die Kuh mit einem Fernglas
<S> ::= <NP> <VP><NP> ::= <N> | <A> <N> | <N> <PP><VP> ::= <V> | <V> <NP> | <VP> <PP><PP> ::= <P> <NP><A> ::= der | die | das | einem | ...<P> ::= mit | in | ...<N> ::= Anna | Kuh | Fernglas | ...<V> ::= betrachtet | ...
85 Automatische Übersetzung
Die Beschreibung, Erkennung und Übersetzung natürlicher Sprachen ist sehr schwierig. Der Beschreibungsansatz über Grammatiken hat bisher nicht zum Erfolg geführt. Heute versucht man, natürliche Sprachen mit statistischen Methoden automatisch zu übersetzen.
86 LiteraturhinweiseF. Gasper, I. Leiß, M. Spengler, H. Stimm: Technische und theoretische Informatik. Bsv 1992.E. Modrow: Automaten, Schaltwerke, Sprachen. Dümmlers Verlag 1988.R. Baumann: Informatik für die Sekundarstufe II, Band 2. Klett-Verlag 1993.Informatik heute, Band 2. Schroedel-Verlag 1988.U. Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag 2001.J. E. Hopcroft / J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley 1988.S. H. Rodger, T. W. Finley: JFLAP. Jones and Bartlett Publishers 2006....
Recommended