86
Formale Sprachen Teil 2 Klaus Becker 2006

Formale Sprachen Teil 2

  • Upload
    viet

  • View
    66

  • Download
    0

Embed Size (px)

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

Page 1: Formale Sprachen Teil 2

Formale SprachenTeil 2

Klaus Becker2006

Page 2: Formale Sprachen Teil 2

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

Page 3: Formale Sprachen Teil 2

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>

Page 4: Formale Sprachen Teil 2

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.

Page 5: Formale Sprachen Teil 2

5 Teil 1

Reguläre Sprachen

Page 6: Formale Sprachen Teil 2

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>

Page 7: Formale Sprachen Teil 2

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)], ...

Page 8: Formale Sprachen Teil 2

8 AufgabeEntwickeln Sie eine (mehrere) Grammatik(en) zur Beschreibung der Klammersprache K3. Entwickeln Sie auch einen (mehrere) endliche Automaten zur Erkennung der Klammersprache K3.

Page 9: Formale Sprachen Teil 2

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

Page 10: Formale Sprachen Teil 2

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

Page 11: Formale Sprachen Teil 2

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.

Page 12: Formale Sprachen Teil 2

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?

Page 13: Formale Sprachen Teil 2

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

Page 14: Formale Sprachen Teil 2

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

Page 15: Formale Sprachen Teil 2

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

Page 16: Formale Sprachen Teil 2

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

Page 17: Formale Sprachen Teil 2

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

Page 18: Formale Sprachen Teil 2

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

Page 19: Formale Sprachen Teil 2

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.

Page 20: Formale Sprachen Teil 2

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>.

Page 21: Formale Sprachen Teil 2

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.

Page 22: Formale Sprachen Teil 2

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.

Page 23: Formale Sprachen Teil 2

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?

Page 24: Formale Sprachen Teil 2

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.

Page 25: Formale Sprachen Teil 2

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.

Page 26: Formale Sprachen Teil 2

26

Page 27: Formale Sprachen Teil 2

27 Teil 2

Kontextfreie Sprachen

Page 28: Formale Sprachen Teil 2

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...

Page 29: Formale Sprachen Teil 2

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.: (), (()), (()()), ..., ((())()(()(()()))), ...

Page 30: Formale Sprachen Teil 2

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.

Page 31: Formale Sprachen Teil 2

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.

Page 32: Formale Sprachen Teil 2

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.

Page 33: Formale Sprachen Teil 2

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.

Page 34: Formale Sprachen Teil 2

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.

Page 35: Formale Sprachen Teil 2

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

Page 36: Formale Sprachen Teil 2

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

Page 37: Formale Sprachen Teil 2

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.

Page 38: Formale Sprachen Teil 2

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.

Page 39: Formale Sprachen Teil 2

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.

Page 40: Formale Sprachen Teil 2

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.

Page 41: Formale Sprachen Teil 2

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

Page 42: Formale Sprachen Teil 2

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

Page 43: Formale Sprachen Teil 2

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.

Page 44: Formale Sprachen Teil 2

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?

Page 45: Formale Sprachen Teil 2

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

Page 46: Formale Sprachen Teil 2

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.

Page 47: Formale Sprachen Teil 2

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

Page 48: Formale Sprachen Teil 2

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))

Page 49: Formale Sprachen Teil 2

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.

Page 50: Formale Sprachen Teil 2

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.

Page 51: Formale Sprachen Teil 2

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.

Page 52: Formale Sprachen Teil 2

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

Page 53: Formale Sprachen Teil 2

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.

Page 54: Formale Sprachen Teil 2

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.

Page 55: Formale Sprachen Teil 2

55 Teil 3

Kontextsensitive und allgemeine Sprachen

Page 56: Formale Sprachen Teil 2

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>

Page 57: Formale Sprachen Teil 2

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>

Page 58: Formale Sprachen Teil 2

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>

Page 59: Formale Sprachen Teil 2

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>

Page 60: Formale Sprachen Teil 2

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>

Page 61: Formale Sprachen Teil 2

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, ...

Page 62: Formale Sprachen Teil 2

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.

Page 63: Formale Sprachen Teil 2

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

Page 64: Formale Sprachen Teil 2

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

Page 65: Formale Sprachen Teil 2

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.

Page 66: Formale Sprachen Teil 2

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....

Page 67: Formale Sprachen Teil 2

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.

Page 68: Formale Sprachen Teil 2

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.

Page 69: Formale Sprachen Teil 2

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

Page 70: Formale Sprachen Teil 2

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

Page 71: Formale Sprachen Teil 2

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.

Page 72: Formale Sprachen Teil 2

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?

Page 73: Formale Sprachen Teil 2

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

Page 74: Formale Sprachen Teil 2

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

Page 75: Formale Sprachen Teil 2

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.

Page 76: Formale Sprachen Teil 2

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.

Page 77: Formale Sprachen Teil 2

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.

Page 78: Formale Sprachen Teil 2

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

Page 79: Formale Sprachen Teil 2

79 Teil 4

Exkurs: natürliche Sprachen

Page 80: Formale Sprachen Teil 2

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)

Page 81: Formale Sprachen Teil 2

81 Sprache und ihre VerwendungNatürliche Sprachen sind Zeichensysteme, die u. a. für Kommunikation genutzt werden.

Page 82: Formale Sprachen Teil 2

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

Page 83: Formale Sprachen Teil 2

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)

Page 84: Formale Sprachen Teil 2

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 | ...

Page 85: Formale Sprachen Teil 2

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.

Page 86: Formale Sprachen Teil 2

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....