Theorie formaler Sprachen Klaus Becker 2004. KB Theorie formaler Sprachen 2 Formale Sprachen und...

Theorie formaler SprachenTheorie formaler Sprachen

Klaus Becker2004

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

Teil 1 Teil 1

Reguläre Sprachen

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

Die Sprache der ZustandsbezeichnerDie Sprache der Zustandsbezeichner

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.

GrammatikGrammatik

S zAA 0A 1A 0AA 1A

z01101

z000000

(Vereinfachte) Zustandsbezeichner(Vereinfachte) Zustandsbezeichner

GrammatikregelnGrammatikregeln

Übersetzung: Grammatik Übersetzung: Grammatik Automat Automat

S zAA 0A 1A 0AA 1A

Übersetzung: Automat Übersetzung: Automat Grammatik Grammatik

B A 0BA 1BS zAA 1AA 0A

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

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.

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

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

nichtdeterministischer Automat (NFA)

deterministischer Automat (DFA)

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

BeweisideeBeweisidee

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

Zusammenhang: Grammatik – AutomatZusammenhang: Grammatik – Automat

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.

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

S zAA 0A 1A 0AA 1A

Grammatik NFA NFA Grammatik

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

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

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

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

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

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

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

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

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

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

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

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

Teil 2 Teil 2

Kontextfreie Sprachen

KlammersprachenKlammersprachen

Vereinfachte ZustandsmengenVereinfachte Zustandsmengen

Element

Elementliste

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

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

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

XML mit vereinfachten TagsXML mit vereinfachten Tags

Element

Elementliste

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

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

< < <> >>

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}

Erkennen von KlammersprachenErkennen von Klammersprachen

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

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

Fehler

<< <<<>>>>

Erkennen von KlammersprachenErkennen von Klammersprachen

Fehler

<< <<<>>>>

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.

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:

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

... ...

a a ...a

aa a b b

... ...

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.

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.

Erweiterung des AutomatenmodellsErweiterung des Automatenmodells

...< < < > > >

Kellerautomat

Eingabeband

Keller

LesekopfZustandsbasiert

e Verarbeitungseinh

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

Spracherkennung:Spracherkennung:

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

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

Nichtdeterministische KellerautomatenNichtdeterministische Kellerautomaten

Nichtdeterminismus

Eingabe , Pop-Aktion; Push-Aktion

Nichtdeterminismus

Nichtdeterministische KellerautomatenNichtdeterministische Kellerautomaten

ÜbungÜbung

Entwickeln Sie Kellerautomaten, die die folgenden Sprachen akzeptieren:

LösungsvorschlagLösungsvorschlag

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:

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.

Übersetzung: Grammatik Übersetzung: Grammatik KellerautomatKellerautomat

Nichtdeterministischer Zustandsübergang

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.

Teil 3 Teil 3

Kontextsensitive und allgemeine Sprachen

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.

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

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

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)

Tag-KlammerspracheTag-Klammersprache

aab bcaab

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

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

Test der Tag-KlammerspracheTest der Tag-Klammersprache

aab|bc|aab

Struktur der RegelnStruktur der Regeln

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

Strukturanalyse:Strukturanalyse:

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.

Einordnung der Tag-KlammerspracheEinordnung der Tag-Klammersprache

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

a) ist allgemein,

b) ist kontextsensitiv,

c) ist nicht kontextfrei.

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.

Spracherkennung durch ...Spracherkennung durch ...

Brute Force Parser

Erzeugung von Hilfknoten

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

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

Erweiterung des AutomatenmodellsErweiterung des Automatenmodells

...< < < > > >

Turingmaschine

Ein-/Ausgabeband

Schreib-/Lesekopf

Zustandsbasierte

Verarbeitungseinheit

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

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.

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}

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

Erkennung der Tag-KlammerspracheErkennung der Tag-Klammersprache

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

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

Erkennung der Tag-KlammerspracheErkennung der Tag-Klammersprache

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

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.

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

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

ÜbungenÜbungen

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

Teil 4 Teil 4

Exkurs: Natürliche Sprachen

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)

Noam ChomskyNoam Chomsky

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

(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

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

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)

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

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

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

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/

Theorie formaler Sprachen Klaus Becker 2004. KB Theorie formaler Sprachen 2 Formale Sprachen und...

Documents

1. Formale Sprachen 1.2 Grammatiken formaler Sprachen · Informatik 12 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen

Formale Grundlagen der Informatik - informatik.uni … · Formale Grundlagen der Informatik Automaten, Grammatiken und Formale Sprachen sowie Berechenbarkeit und Komplexität Sommersemester

Endliche Automaten Klaus Becker 2010. 2 Endliche Automaten

Kombinatorik und chemische Metrik formaler Reaktions- und

Einfluss der masseerhaltenden Kavitation auf ... · Welle und Rotor wurden in einem FE-System mit 36 Timoshenko-Balkenelementen abgebildet. Nach formaler Nach formaler Substrukturierung

Theoretische Grundlagen der Informatik Vorlesung am 19 ... · Endliche Automaten und Reguläre Sprachen 1 19.10.2017 Torsten Ueckerdt - Theoretische Grundlagen der Informatik Vorlesung

185.263 Automaten und Formale Sprachen VO 2.0 + UE 1 Rudolf Freund, Marion Oswald

Informatik und Angewandte Kognitionswissenschaft · 2018. 6. 4. · Vorlesung "Automaten und formale Sprachen" aus dem Sommer- semester 2009 die Vorlesung "Informatik B2" Hülsbusch

Automaten und Formale Sprachen Skript zur Vorlesung WS ...€¦ · dass kontextfreie Grammatiken das Beschreibungsmittel sind, mit dem die Syntax aller Programmiersprachen deﬁniert

Methoden und Techniken der Anforderungsanalysefiedler/teaching/ss2004/prak/... · Anforderungen durch Einsatz informaler, semi-formaler sowie formaler Spezifikationsmethoden erfassen

Formale Sprachen und Automaten Klaus Becker 2004

Modulhandbuch Master-Studiengang Embedded Systemseitidaten.fh-pforzheim.de/daten/es/studium/...• verstehen die Bedeutung formaler Sprachen in der Mo-dellierung ... Voraussetzungen:

Formale Sprachen und Automaten

Modulhandbuch - informatik.uni-halle.de · - Berechenbarkeitstheorie, unentscheidbare Probleme Effiziente Algorithmen, P-NP-Problem Chomsky-Hierarchie formaler Sprachen Verantwortlichkeiten

Automaten und Formale Sprachen Sommersemester 2019 · OrganisatorischesEinf uhrung Chomsky-HierarchieRegul are Sprachen Kontextfreie Sprachen Adventure-Problem Adventures bestehen

F2 – Automaten und Formale Sprachen · FormaleGrundlagenderInformatik,F2–AutomatenundKalkule –I–¨ Inhaltsverzeichnis 0 Einleitung 1 1 Notationen und Grundbegriﬀe 10 2 Regul¨are

Sprachen und Automaten Einsatz der Software AtoCC (Kurs: 07C404101) Fortbildungsveranstaltung des Staatlichen Schulamts Cottbus Christian Wagenknecht,

Automaten und Formale Sprachen - tu-ilmenau.de€¦ · Grundbegriffe Definition Eine Grammatik G ist ein 4-Tupel G =(V , Σ, P, S), das folgende Bedingungen erfüllt: • V ist

Automaten, Formale Sprachen und Berechenbarkeit Iwind.in.tum.de/lehre/fospr/WS0102/Skript/SkriptIII.pdf · Automaten, Formale Sprachen und Berechenbarkeit I Skript zur Vorlesung im

Automaten und Formale Sprachen Epilog Ralf Möller Hamburg Univ. of Technology