Theorie formaler Sprachen Klaus Becker 2004. KB Theorie formaler Sprachen 2 Formale Sprachen und Automaten Reguläre SprachenEndliche Automaten Kontextfreie

Theorie formaler SprachenTheorie formaler Sprachen

Klaus Becker2004

2

KB

Th

eori

e f

orm

ale

r S

pra

chen

Formale Sprachen und AutomatenFormale Sprachen und Automaten

Reguläre SprachenReguläre Sprachen Endliche AutomatenEndliche Automaten

Kontextfreie SprachenKontextfreie Sprachen KellerautomatenKellerautomaten

Kontextsensitive Sprachen

Kontextsensitive Sprachen Linear beschränkte TMLinear beschränkte TM

Allgemeine SprachenAllgemeine Sprachen TuringmaschinenTuringmaschinen

3

KB

Th

eori

e f

orm

ale

r S

pra

chen

Teil 1 Teil 1

Reguläre Sprachen

4

KB

Th

eori

e f

orm

ale

r S

pra

chen

Festlegung formaler SprachenFestlegung formaler Sprachen

ZielsetzungZielsetzung

Ziel ist es, verschiedene Möglichkeiten zur Festlegung formaler Sprachen zu vergleichen.

B zNN 0 N 1N 0N N 1N

Automat

Grammatik

5

KB

Th

eori

e f

orm

ale

r S

pra

chen

Die Sprache der ZustandsbezeichnerDie Sprache der Zustandsbezeichner

z0

z10

z01101

z000000

(Vereinfachte) Zustandsbezeichner(Vereinfachte) Zustandsbezeichner

Regeln zur Bildung vereinfachter ZustandsbezeichnerRegeln zur Bildung vereinfachter Zustandsbezeichner

/1/ Der Bezeichner beginnt mit einem z.

/2/ Danach kommt beliebig oft, aber mindestens einmal eine der Ziffern 0 oder 1.

6

KB

Th

eori

e f

orm

ale

r S

pra

chen

GrammatikGrammatik

S zAA 0A 1A 0AA 1A

z0

z10

z01101

z000000

(Vereinfachte) Zustandsbezeichner(Vereinfachte) Zustandsbezeichner

GrammatikregelnGrammatikregeln

7

KB

Th

eori

e f

orm

ale

r S

pra

chen

Übersetzung: Grammatik Übersetzung: Grammatik Automat Automat

S zAA 0A 1A 0AA 1A

S zAA 0A 1A 0AA 1A

8

KB

Th

eori

e f

orm

ale

r S

pra

chen

Übersetzung: Automat Übersetzung: Automat Grammatik Grammatik

B A 0BA 1BS zAA 1AA 0A


9

KB

Th

eori

e f

orm

ale

r S

pra

chen

Exkurs: Nichtdeterministische Exkurs: Nichtdeterministische AutomatenAutomaten

Bei einem nichtdeterministischen Automaten besteht Wahlfreiheit: Der Automat kann bei einer gegebenen Eingabe von einem Zustand in verschiedene Folgezustände überführt werden.Bei einem deterministischen Automaten ist genau festgelegt, in welchen Folgezustand der Automat bei einer gegebenen Eingabe von einem Zustand aus überführt wird.

Wahlmöglichkeit

Wahlmöglichkeit

10

KB

Th

eori

e f

orm

ale

r S

pra

chen


Unter der Sprache eines nichtdeterministischen Automaten versteht man die Menge aller Wörter (über dem Alphabet der Eingabezeichen), die den Automaten vom Anfangszustand (allg. von einem Anfangszustand) in einen Endzustand überführen können.

11

KB

Th

eori

e f

orm

ale

r S

pra

chen


Das Teilwort z00 kann den Automaten in die Zustände q1 und q2 überführen. Wird das nächste Zeichen 1 verarbeitet, so erweist sich die bisherige Überführung in q2 als Sackgasse (rot). Die Verarbeitung von q1 aus führt in q1 (grau) oder q2 (grün).

12

KB

Th

eori

e f

orm

ale

r S

pra

chen

Überführung: NFA Überführung: NFA DFA DFA

nichtdeterministischer Automat (NFA)

deterministischer Automat (DFA)

13

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÄquivalenzsatzÄquivalenzsatz

Bemerkungen:

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.

Deterministische und nichtdeterministische Automaten erkennen somit dieselben Sprachen.

Satz (Rabin, Scott)

Zu jedem nichtdeterministischen Automaten gibt es einen deterministischen Automaten, der dieselbe Sprache erkennt.

Satz (Rabin, Scott)

Zu jedem nichtdeterministischen Automaten gibt es einen deterministischen Automaten, der dieselbe Sprache erkennt.

14

KB

Th

eori

e f

orm

ale

r S

pra

chen

BeweisideeBeweisidee

Jede Menge von Zuständen des NFA ergibt einen neuen Zustand des DFA. Nicht benötigte Zustände werden weggelassen.

15

KB

Th

eori

e f

orm

ale

r S

pra

chen

Zusammenhang: Grammatik – AutomatZusammenhang: Grammatik – Automat

S zAA 0A 1A 0AA 1A

S zAA 0A 1A 0AA 1A



Grammatik NFA NFA Grammatik

Die Übersetzung Grammatik NFA bzw. NFA Grammatik funktioniert nur, wenn die Grammatikregeln eine sehr einfache Gestalt haben: - Auf der linken Seite steht ein Nichtterminalsymbol.- Auf der rechten Seite steht genau ein Terminalsymbol oder ein Terminalsymbol gefolgt von einem Nichtterminalsymbol.

16

KB

Th

eori

e f

orm

ale

r S

pra

chen

Reguläre GrammatikenReguläre Grammatiken

Eine Grammatik heißt regulär genau dann, wenn für jede Regel gilt: - Auf der linken Seite steht ein Nichtterminalsymbol.- Auf der rechten Seite steht genau ein Terminalsymbol oder ein Terminalsymbol gefolgt von einem Nichtterminalsymbol.

Eine Sprache heißt regulär genau dann, wenn sie mit Hilfe einer regulären Grammatik beschrieben werden kann.

Eine Grammatik heißt regulär genau dann, wenn für jede Regel gilt: - Auf der linken Seite steht ein Nichtterminalsymbol.- Auf der rechten Seite steht genau ein Terminalsymbol oder ein Terminalsymbol gefolgt von einem Nichtterminalsymbol.

Eine Sprache heißt regulär genau dann, wenn sie mit Hilfe einer regulären Grammatik beschrieben werden kann.

Beispiele für reguläre Grammatikregeln:

A cA aBA cA

Beispiele für nicht-reguläre Grammatikregeln:

A aBaAB c

17

KB

Th

eori

e f

orm

ale

r S

pra

chen


S zAA 0A 1A 0AA 1A

S zAA 0A 1A 0AA 1A



Grammatik NFA NFA Grammatik

Satz

Jede durch einen endlichen Automaten erkennbare Sprache ist regulär.

Jede reguläre Sprache kann durch einen endlichen Automaten erkannt werden.

Satz

Jede durch einen endlichen Automaten erkennbare Sprache ist regulär.

Jede reguläre Sprache kann durch einen endlichen Automaten erkannt werden.

18

KB

Th

eori

e f

orm

ale

r S

pra

chen

Überführung: NFA Überführung: NFA RE RE

(z((1+0)*))(0+1)

19

KB

Th

eori

e f

orm

ale

r S

pra

chen

Überführung: RE Überführung: RE NFA NFA

(z((1+0)*))(0+1)

20

KB

Th

eori

e f

orm

ale

r S

pra

chen

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

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

21

KB

Th

eori

e f

orm

ale

r S

pra

chen

Beschreibung regulärer SprachenBeschreibung regulärer Sprachen

Folgende Sprachbeschreibungskonzepte sind äquivalent:

- deterministische endliche Automaten

- nichtdeterministische endliche Automaten

- reguläre Grammatiken

- reguläre Ausdrücke

S zAA 0A 1A 0AA 1A

S zAA 0A 1A 0AA 1A

(z((1+0)*))(0+1)

22

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÜbungenÜbungen

Aufgabe 1Wir betrachten die Sprache der Wörter über dem Alphabet {a,b}, die mit a beginnen und mit b enden. Zeigen Sie, dass diese Sprache regulär ist. Entwerfen Sie zu dieser Sprache eine reguläre Grammatik, einen endlichen Automaten und einen regulären Ausdruck.

Aufgabe 2Wir betrachten die Sprache der Wörter über dem Alphabet {a,b,c}, die nach jedem a genau ein b enthalten. Zeigen Sie, dass diese Sprache regulär ist. Entwerfen Sie zu dieser Sprache eine reguläre Grammatik, einen endlichen Automaten und einen regulären Ausdruck.

Aufgabe 3Wir betrachten die Sprache der korrekt gebildeten ganzen Zahlen. Hierzu gehören z. B. 0, 3, +3, -3. Zeigen Sie, dass diese Sprache regulär ist.

23

KB

Th

eori

e f

orm

ale

r S

pra

chen

Teil 2 Teil 2

Kontextfreie Sprachen

24

KB

Th

eori

e f

orm

ale

r S

pra

chen

KlammersprachenKlammersprachen

<a> <zm> <z>off</z> <z>low</z> <z>high</z> </zm> <az> <z>off</z> </az> ...</a>

Vereinfachte ZustandsmengenVereinfachte Zustandsmengen

ATag

ETag

Element

Elementliste

Ein Element besteht aus einem Anfangstag, einem Bezeichner oder einer Elementliste und einem passenden Endtag.

25

KB

Th

eori

e f

orm

ale

r S

pra

chen


<a> <zm><z>off</z><z>low</z><z>high</z></zm> <az><z>off</z></az> ...</a>


Terminalsymbole: '<', '>', '/', 'a', 'b', 'c', 'd', ...Startsymbol: <Element>Produktionen:<Abc> ::= 'a' | 'b' | 'c' | 'd' | ... <Bezeichner> ::= <Abc> | <Abc> <Bezeichner><ATag> ::= '<' <Bezeichner> '>' <ETag> ::= '<' '/' <Bezeichner> '>' <Element> ::= <ATag> <Bezeichner> <ETag> [*]<Element> ::= <ATag> <ElementListe> <ETag> [*]<ElementListe> ::= <Element> | <Element> <ElementListe>[*] Anfangs- und Endtag müssen zusammenpassen

GrammatikGrammatik

26

KB

Th

eori

e f

orm

ale

r S

pra

chen


< < <off> <low> <high> > < <off> > ...>

XML mit vereinfachten TagsXML mit vereinfachten Tags

Terminalsymbole: '<', '>', 'a', 'b', 'c', 'd', ...Startsymbol: <Element>Produktionen:<Abc> ::= 'a' | 'b' | 'c' | 'd' | ... <Bezeichner> ::= <Abc> | <Abc> <Bezeichner><Element> ::= '<' <Bezeichner> '>' | '<' <ElementListe> '>'<ElementListe> ::= <Element> | <Element> <ElementListe>

<a> <zm> <z>off</z> <z>low</z> <z>high</z> </zm> <az> <z>off</z> </az> ...</a>

ATag

ETag

Element

Elementliste

27

KB

Th

eori

e f

orm

ale

r S

pra

chen


< < <> <> <> > < <> > ...>

XML mit vereinfachten Tags ohne InhalteXML mit vereinfachten Tags ohne Inhalte

Terminalsymbole: '<', '>'Startsymbol: <Element>Produktionen:<Element> ::= '<' '>' | '<' <ElementListe> '>'<ElementListe> ::= <Element> | <Element> <ElementListe>

< < <off> <low> <high> > < <off> > ...>

28

KB

Th

eori

e f

orm

ale

r S

pra

chen


< < <> >>

Klammer auf, Klammer zuKlammer auf, Klammer zu

Terminalsymbole: '<', '>'Startsymbol: <Element>Produktionen:<Element> ::= '<' '>' | '<' <Element> '>'

aaabbb

Terminalsymbole: a, bStartsymbol: SProduktionen:S ::= ab | aSb

L = {anbn | n 1}L = {anbn | n 1}

29

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erkennen von KlammersprachenErkennen von Klammersprachen

Problem: Gesucht ist ein endlicher Automat, der Klammersprachen erkennt.Problem: Gesucht ist ein endlicher Automat, der Klammersprachen erkennt.

< < <> <> <> > < <> >>

Fehler

EA

<< <<<>>>>

ok

30

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erkennen von KlammersprachenErkennen von Klammersprachen

Fehler

EA

<< <<<>>>>

Schwierigkeit:Schwierigkeit:

Der endliche Automat muss sich merken, wie viele Klammern geöffnet sind.

Zum Merken hat ein EA nur Zustände zur Verfügung.

Mit endlich vielen Zuständen kann man sich aber nicht beliebig viele geöffnete Klammern merken.

31

KB

Th

eori

e f

orm

ale

r S

pra

chen

Grenzen des endlichen AutomatenGrenzen des endlichen Automaten

Annahme: Es gibt einen endlichen Automaten A, der L akzeptiert.

A hat endliche viele Zustände. m bezeichne die Anzahl dieser Zustände.

Wir betrachten jetzt ein Wort w = akbk mit k > m. Das Wort w hat also 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.

Es ergibt sich folgende Situation:

Satz

Es gibt keinen endlichen Automaten, der die Klammersprache L = {anbn | n 1} akzeptiert.

Satz

Es gibt keinen endlichen Automaten, der die Klammersprache L = {anbn | n 1} akzeptiert.

... ...

...

...

a a ...a

a

aa a b b

32

KB

Th

eori

e f

orm

ale

r S

pra

chen


... ...

...

...

a a ...a

a

aa a b b

Es gilt: w = akbk = apaqarbk mit p+q+r=k.

Betrachte w´ = apaqaqarbk. Beachte: p+q+q+r>k (mehr a‘s als b‘s).

Es 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 mehr a’s als b’s).

Dies ist ein Widerspruch zur Annahme, dass A die Sprache L = {anbn | n 1} akzeptiert. Die Annahme muss daher falsch sein. Die Aussage des Satzes ist folglich wahr.

ap

aq

ar bk

33

KB

Th

eori

e f

orm

ale

r S

pra

chen


Folgerungen:Folgerungen:

Es gibt Sprachen (wie z. B. die oben gezeigten Klammersprachen), 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.

34

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erweiterung des AutomatenmodellsErweiterung des Automatenmodells

...< < < > > >

...

>

>

...

Kellerautomat

Eingabeband

Keller

LesekopfZustandsbasiert

e Verarbeitungseinh

eit

35

KB

Th

eori

e f

orm

ale

r S

pra

chen

Spracherkennung mit KellerautomatenSpracherkennung mit Kellerautomaten

Oberstes Kellerzeichen

Kelleraktionen:Kelleraktionen:

push z Das Zeichen z auf den Stapel legen.

pop Das oberste Zeichen des Stapels entfernen.

Zustandsübergang:Zustandsübergang:

z / e: Aktion

Gelesene Eingabezeiche

n

Spracherkennung:Spracherkennung:

Ein Wort wird akzeptiert, wenn der Keller nach Abarbeitung des Wortes leer ist.

36

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erkennung einer KlammerspracheErkennung einer Klammersprache

Erstellt mit „Automaton Simulator“

Beispiel:

Der Kellerautomat erkennt die Klammersprache L = {<n>n | n 1}.

Oberstes Kellerzeichen / Gelesene Eingabe : Kelleraktion

37

KB

Th

eori

e f

orm

ale

r S

pra

chen

Nichtdeterministische KellerautomatenNichtdeterministische Kellerautomaten

Nichtdeterminismus


Eingabe , Pop-Aktion; Push-Aktion

Nichtdeterminismus

38

KB

Th

eori

e f

orm

ale

r S

pra

chen

Nichtdeterministische KellerautomatenNichtdeterministische Kellerautomaten

39

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÜbungÜbung

Entwickeln Sie Kellerautomaten, die die folgenden Sprachen akzeptieren:

Terminalsymbole: '<', '>', 'a', 'b', 'c'Startsymbol: <Element>Produktionen:<Abc> ::= 'a' | 'b' | 'c' <Bezeichner> ::= <Abc> | <Abc> <Bezeichner><Element> ::= '<' <Bezeichner> '>' | '<' <ElementListe> '>'<ElementListe> ::= <Element> | <Element> <ElementListe>


40

KB

Th

eori

e f

orm

ale

r S

pra

chen

LösungsvorschlagLösungsvorschlag


41

KB

Th

eori

e f

orm

ale

r S

pra

chen

Struktur der RegelnStruktur der Regeln

Auf der linken Seite steht jeweils ein Nichtterminalsymbol.Auf der rechten Seite steht ein Wort, das aus Terminal- und Nichtterminalsymbolen bestehen kann.



Strukturanalyse:Strukturanalyse:

42

KB

Th

eori

e f

orm

ale

r S

pra

chen

Kontextfreie GrammatikenKontextfreie Grammatiken

Beispiele für kontextfreie Grammatikregeln:

E abE aLbL EL EL

Beispiele für nicht-kontextfreie Grammatikregeln:

aAb bAa

Eine Grammatik 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 Sprache heißt kontextfrei genau dann, wenn sie mit Hilfe einer kontextfreien Grammatik beschrieben werden kann.

Eine Grammatik 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 Sprache heißt kontextfrei genau dann, wenn sie mit Hilfe einer kontextfreien Grammatik beschrieben werden kann.

43

KB

Th

eori

e f

orm

ale

r S

pra

chen

Übersetzung: Grammatik Übersetzung: Grammatik KellerautomatKellerautomat

Nichtdeterministischer Zustandsübergang

44

KB

Th

eori

e f

orm

ale

r S

pra

chen


Satz

Eine Sprache ist kontextfrei genau dann, wenn sie von einem nichtdeterministischen Kellerautomaten erkannt wird.

Satz

Eine Sprache ist kontextfrei genau dann, wenn sie von einem nichtdeterministischen Kellerautomaten erkannt wird.

Beachte:

Mit deterministischen Kellerautomaten kann man nur eine echte Teilmenge der kontextfreien Sprachen erkennen.

45

KB

Th

eori

e f

orm

ale

r S

pra

chen

Teil 3 Teil 3

Kontextsensitive und allgemeine Sprachen

46

KB

Th

eori

e f

orm

ale

r S

pra

chen

BeispielBeispiel



Regeln zur Bildung von XML-AusdrückenRegeln zur Bildung von XML-Ausdrücken

/1/ Ein Element besteht aus einem Anfangstag, einem Bezeichner oder einer Elementliste und einem passenden Endtag.

/2/ Ein Bezeichner besteht aus beliebigen alphanumerischen Zeichen.

47

KB

Th

eori

e f

orm

ale

r S

pra

chen

XMLXML



Terminalsymbole: '<', '>', '/', 'a', 'b', 'c', 'd', ...Startsymbol: <Element>Produktionen:<Abc> ::= 'a' | 'b' | 'c' | 'd' | ... <Bezeichner> ::= <Abc> | <Abc> <Bezeichner><ATag> ::= '<' <Bezeichner> '>' <ETag> ::= '<' '/' <Bezeichner> '>' <Element> ::= <ATag> <Bezeichner> <ETag> [*]<Element> ::= <ATag> <ElementListe> <ETag> [*]<ElementListe> ::= <Element> | <Element> <ElementListe>[*] Anfangs- und Endtag müssen zusammenpassen

GrammatikGrammatik

48

KB

Th

eori

e f

orm

ale

r S

pra

chen

Eine vereinfachte Tag-KlammerspracheEine vereinfachte Tag-Klammersprache

aab bcaab

ATag-Wort-ETagATag-Wort-ETag

SprachbeschreibungSprachbeschreibung

L = {tut | t {a,b}*; u {a,b,c}*}

L ist die Menge aller Wörter, die aus einem beliebigen Wort u über dem Alphabet {a,b,c} und identischem Anfangs- und Endtag t besteht, wobei t ein beliebiges (nicht-leeres) Wort über dem Alphabet {a,b} ist.

ba ccbaba

49

KB

Th

eori

e f

orm

ale

r S

pra

chen

Tag-KlammerspracheTag-Klammersprache

aab bcaab


Startsymbol: SA ::= aA | bA | E ::= aE | bE | W ::= aW | bW | cW | S ::= A W E [*][*] A und E müssen zusammenpassen

Grammatik – Version 1 (mit Zusatzbedingung)Grammatik – Version 1 (mit Zusatzbedingung)

50

KB

Th

eori

e f

orm

ale

r S

pra

chen

Tag-KlammerspracheTag-Klammersprache

aab bcaab


Startsymbol: SS ::= aTaX | bTbXT ::= aTaX | bTbX | UaXb ::= baXaXa ::= aaXbXa ::= abXbXb ::= bbXaX ::= abX ::= bU ::= aU | bU | cU |

Grammatik – Version 2 (ohne Zusatzbedingung)Grammatik – Version 2 (ohne Zusatzbedingung)

51

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÜbungÜbung


Testen Sie die Grammatik der Tag-Klammersprache mit Hilfe des Werkzeugs JFLAP. Erzeugen Sie hierbei auch Syntaxbäume und versuchen Sie, die „Idee“ der Grammatikregeln zu verstehen.

52

KB

Th

eori

e f

orm

ale

r S

pra

chen

Test der Tag-KlammerspracheTest der Tag-Klammersprache

aab|bc|aab

53

KB

Th

eori

e f

orm

ale

r S

pra

chen

Struktur der RegelnStruktur der Regeln

Auf der linken und rechten Seite können beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen stehen.

Strukturanalyse:Strukturanalyse:


54

KB

Th

eori

e f

orm

ale

r S

pra

chen

Kontextsensitive / allgemeine Kontextsensitive / allgemeine GrammatikenGrammatiken

Beispiele:

aX a kontextsensitive Regel

bXa abX allgemeine Regel

Eine Grammatik heißt allgemein genau dann, wenn jede Regel die Struktur u v hat, wobei u und v beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind.

Eine Grammatik heißt kontextsensitiv genau dann, wenn jede Regel die Struktur uAv uwv hat, wobei - A ein Nichtterminalsymbol ist und- u, v und w beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind.

Eine Sprache heißt kontextsensitiv / allgemein genau dann, wenn sie mit Hilfe einer kontextsensitiven / allgemeinen Grammatik beschrieben werden kann.

Eine Grammatik heißt allgemein genau dann, wenn jede Regel die Struktur u v hat, wobei u und v beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind.

Eine Grammatik heißt kontextsensitiv genau dann, wenn jede Regel die Struktur uAv uwv hat, wobei - A ein Nichtterminalsymbol ist und- u, v und w beliebige Wörter bestehend aus Terminal- und Nichtterminalsymbolen sind.

Eine Sprache heißt kontextsensitiv / allgemein genau dann, wenn sie mit Hilfe einer kontextsensitiven / allgemeinen Grammatik beschrieben werden kann.

55

KB

Th

eori

e f

orm

ale

r S

pra

chen

Einordnung der Tag-KlammerspracheEinordnung der Tag-Klammersprache

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*}

a) ist allgemein,

b) ist kontextsensitiv,

c) ist nicht kontextfrei.

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*}

a) ist allgemein,

b) ist kontextsensitiv,

c) ist nicht kontextfrei.

Der Nachweis von a) ist mit der bereits angegebenen Grammatik erbracht.Auf den Nachweis von b) und c) wird hier verzichtet.

56

KB

Th

eori

e f

orm

ale

r S

pra

chen

Spracherkennung durch ...Spracherkennung durch ...

Brute Force Parser

Erzeugung von Hilfknoten

57

KB

Th

eori

e f

orm

ale

r S

pra

chen

... Suche einer Ableitung... Suche einer Ableitung

Grammatik:S ::= aSaX | bSbX | UaXb ::= baX; aXa ::= aaX; bXa ::= abX; bXb ::= bbX aX ::= a; bX ::= bU ::= aU | bU | cU |

Ableitung:S aSaX a(aSaX)aX = aaSaXaX aa(bSbX)aXaX = aabSbXaXaX aab(bSbX)bXaXaX = aabbSbXbXaXaX aabb(U)bXbXaXaX = aabbUbXbXaXaX aabb(cU)bXbXaXaX = aabbcUbXbXaXaX aabbc()bXbXaXaX = aabbcbXbXaXaX aabbc(bbX)XaXaX = aabbcbbXXaXaX # aab(U)bXaXaX = aabUbXaXaX aab(cU)bXaXaX = aabcUbXaXaX...

Wort: aabbcaab

Backtracking

58

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erweiterung des AutomatenmodellsErweiterung des Automatenmodells

...< < < > > >

...

Turingmaschine

Ein-/Ausgabeband

Schreib-/Lesekopf

Zustandsbasierte

Verarbeitungseinheit

59

KB

Th

eori

e f

orm

ale

r S

pra

chen

Spracherkennung mit TuringmaschinenSpracherkennung mit Turingmaschinen

Turingmaschinenaktionen:Turingmaschinenaktionen:

R ein Feld nach rechts

L ein Feld nach links

S stopp


a ; b, R

Geschriebenes Zeichen

Aktion

Gelesenes Zeichen

60

KB

Th

eori

e f

orm

ale

r S

pra

chen

WorterkennungWorterkennung

Worterkennung mit leerem BandWorterkennung mit leerem Band

Das zu bearbeitende Wort wird auf das Band geschrieben. Der Schreib-Lese-Kopf wird auf das erste Zeichen des Wortes gesetzt.

Ein Wort wird akzeptiert, wenn die Turingmaschine nach der Bearbeitung des Wortes hält und ein leeres Band hinterlässt.Worterkennung mit EndzuständenWorterkennung mit Endzuständen

Das zu bearbeitende Wort wird auf das Band geschrieben. Der Schreib-Lese-Kopf wird auf das erste Zeichen des Wortes gesetzt.

Ein Wort wird akzeptiert, wenn sich die Turingmaschine nach der Bearbeitung des Wortes in einem Endzustand befindet.

61

KB

Th

eori

e f

orm

ale

r S

pra

chen

Spracherkennung mit Turingmaschinen Spracherkennung mit Turingmaschinen

Worterkennung mit leerem Band am Beispiel L = {anbn | n 0}Worterkennung mit leerem Band am Beispiel L = {anbn | n 0}

62

KB

Th

eori

e f

orm

ale

r S

pra

chen


Worterkennung mit Endzuständen am Beispiel L = {anbn | n 0}Worterkennung mit Endzuständen am Beispiel L = {anbn | n 0}

63

KB

Th

eori

e f

orm

ale

r S

pra

chen


Worterkennung mit Endzuständen am Beispiel L = {anbn | n 0}Worterkennung mit Endzuständen am Beispiel L = {anbn | n 0}

64

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erkennung der Tag-KlammerspracheErkennung der Tag-Klammersprache

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*} kann mit Hilfe einer Turingmaschine erkannt werden.

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*} kann mit Hilfe einer Turingmaschine erkannt werden.

Schritt 1: Führe Begrenzer ein: aabbcaab xaabbcaabx

Schritt 2: Lass die Begrenzer Schritt für Schritt nach innen wandern und überprüfe, ob die Teilworte links und rechts vom Begrenzer gleich sind:xaabbcaabx ... axabbxaaxb ... aaxbbcaxab ... aabxbcxaab

Ersetze hierzu Schritt für Schritt am linken Ende ein a durch ein y bzw. ein b durch ein z, wandere jeweils an das rechte Ende an die entsprechende Position. Wenn das passende Zeichen gefunden wird, dann ersetze es analog, ansonsten mach die Ersetzung rückgängig und verschiebe die Begrenzer eine Position weiter nach innen.

Idee – dargestellt am Beispiel aab|bc|aabIdee – dargestellt am Beispiel aab|bc|aab

65

KB

Th

eori

e f

orm

ale

r S

pra

chen

... mit dem MPG-Turing-Simulator... mit dem MPG-Turing-Simulator

66

KB

Th

eori

e f

orm

ale

r S

pra

chen

Erkennung der Tag-KlammerspracheErkennung der Tag-Klammersprache

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*} kann mit Hilfe einer linear beschränkten Turingmaschine erkannt werden.

Satz

Die Tag-Klammersprache L = {tut | t {a,b}*; u {a,b,c}*} kann mit Hilfe einer 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.

BemerkungBemerkung

67

KB

Th

eori

e f

orm

ale

r S

pra

chen


Satz

Eine Sprache ist allgemein genau dann, wenn sie von einer deterministischen (oder nichtdeterministischen) Turingmaschine erkannt wird.

Eine Sprache ist kontextsensitiv genau dann, wenn sie von einer linear beschränkten nichtdeterministischen Turingmaschine erkannt wird.

Satz

Eine Sprache ist allgemein genau dann, wenn sie von einer deterministischen (oder nichtdeterministischen) Turingmaschine erkannt wird.

Eine Sprache ist kontextsensitiv genau dann, wenn sie von einer linear beschränkten nichtdeterministischen Turingmaschine erkannt wird.

Deterministische und nichtdeterministische Turingmaschinen sind gleich mächtig.

BemerkungBemerkung

68

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÜbungenÜbungen

Aufgabe 1Entwerfen und testen Sie eine Turingmaschine, die die Sprache L = {anbn | n 0} akzeptiert.

Aufgabe 2Entwerfen und testen Sie eine Turingmaschine, die die Sprache der korrekt gebildeten Zahlen akzeptiert.

Aufgabe 3Entwerfen und testen Sie eine Turingmaschine, die die Sprache der korrekt geklammerten a-b-Ausdrücke akzeptiert. Zu dieser Sprache gehören alle Wörter über dem Alphabet {a, b}, die zu jeder öffnenden Klammer a eine schließende Klammer b haben. Z. B.: aabb, aababb, aaababbabb

Aufgabe 4Entwerfen und testen Sie eine Turingmaschine, die die Sprache L = {anbncn| n 0} akzeptiert.

69

KB

Th

eori

e f

orm

ale

r S

pra

chen

ÜbungenÜbungen

Aufgabe 5Welche der in Aufgabe 1, ..., Aufgabe 4 beschriebenen Sprachen ist regulär, kontextfrei, kontextsensitiv, allgemein?

70

KB

Th

eori

e f

orm

ale

r S

pra

chen

Teil 4 Teil 4

Exkurs: Natürliche Sprachen

71

KB

Th

eori

e f

orm

ale

r S

pra

chen

Chomsky-HierarchieChomsky-Hierarchie

Typ Grammatik äquivalenter Automat

0 allgemein (nicht)deterministische Turingmaschine

1 kontextsensitiv nichtdet. linear beschr. Turingmaschine

2 kontextfrei nichtdeterministischer Kellerautomat

3 regulär (nicht)deterministischer endl. Automat

Klassifikation von Sprachen (nach Chomsky / 1958)Klassifikation von Sprachen (nach Chomsky / 1958)

72

KB

Th

eori

e f

orm

ale

r S

pra

chen

Noam ChomskyNoam Chomsky

http://web.mit.edu/linguistics/www/chomsky.home.html

73

KB

Th

eori

e f

orm

ale

r S

pra

chen

(Natürliche) Sprachen(Natürliche) Sprachen

Sicht: zu Kommunikationszwecken verwendetes ZeichensystemSicht: zu Kommunikationszwecken verwendetes Zeichensystem

Problem: Beschreibung und Erkennung natürlicher SprachenProblem: Beschreibung und Erkennung natürlicher Sprachen

74

KB

Th

eori

e f

orm

ale

r S

pra

chen

SemiotikSemiotik

Semiotik: Lehre von den ZeichenSemiotik: Lehre von den Zeichen

Pragmatik: Lehre von der Verwendung sprachlicher Konstrukte in Handlungs-situationen

Beziehung zwischen Zeichen und Zeichenbenutzer

Pragmatik: Lehre von der Verwendung sprachlicher Konstrukte in Handlungs-situationen

Beziehung zwischen Zeichen und Zeichenbenutzer

Semantik: Bedeutungslehre

Beziehung zwischen Zeichen und Bezeichnetem

Semantik: Bedeutungslehre

Beziehung zwischen Zeichen und Bezeichnetem

Syntax: Lehre vom Satzbau

Anordnung der Zeichen

Syntax: Lehre vom Satzbau

Anordnung der Zeichen

75

KB

Th

eori

e f

orm

ale

r S

pra

chen

Syntax natürlicher SprachenSyntax natürlicher Sprachen

<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> ::= <NP>Eine Präpositionalphrase besteht aus einer Präposition und einer Nominalphrase.

<A> ::= der | die | das | dem | ein | einem | ... ::= mit | in | ...<N> ::= Anna | Kuh | Park | Fernglas | ...<V> ::= betrachtet | ...

(nach U. Schöning: Ideen der Informatik. Oldenbourg 2002)

76

KB

Th

eori

e f

orm

ale

r S

pra

chen

Ableitung eines SatzesAbleitung eines Satzes

<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 <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> ::= <NP><A> ::= der | die | das | einem | ... ::= mit | in | ...<N> ::= Anna | Kuh | Fernglas | ...<V> ::= betrachtet | ...

<S> ::= <NP> <VP><NP> ::= <N> | <A> <N> | <N> <PP><VP> ::= <V> | <V> <NP> | <VP> <PP><PP> ::= <NP><A> ::= der | die | das | einem | ... ::= mit | in | ...<N> ::= Anna | Kuh | Fernglas | ...<V> ::= betrachtet | ...

77

KB

Th

eori

e f

orm

ale

r S

pra

chen

Automatische ÜbersetzungAutomatische Übersetzung

Die Beschreibung, Erkennung und Übersetzung natürlicher Sprachen ist sehr schwierig. Der Beschreibungsansatz über Grammatiken hat bisher nicht zum Erfolg geführt.

BemerkungBemerkung

78

KB

Th

eori

e f

orm

ale

r S

pra

chen

Automatische Übersetzung heuteAutomatische Übersetzung heute

Idee: Statistische Übersetzung mit Paralleltexten http://www.uebersetzerportal.de/nachrichten/n-archiv/2003/2003-09/2003-09-17.htmIdee: Statistische Übersetzung mit Paralleltexten http://www.uebersetzerportal.de/nachrichten/n-archiv/2003/2003-09/2003-09-17.htm

79

KB

Th

eori

e f

orm

ale

r S

pra

chen

LiteraturhinweiseLiteraturhinweise

Gasper / Leiß / Spengler / Stimm: Technische und theoretische Informatik. Bsv 1992.

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.

Automaton Simulator: http://www.cburch.com/proj/autosim/

Jflap: http://www.cs.duke.edu/~rodger/tools/jflap/

Charon: http://www.spohrer.net/charon.htm

GoldParserBuilder: www.devincook.com/goldparser/

Documents

Theorie formaler Sprachen Klaus Becker 2004. KB Theorie formaler Sprachen 2 Formale Sprachen und Automaten Reguläre SprachenEndliche Automaten Kontextfreie