Formale Sprachen und Automaten Klaus Becker 2004

Formale Sprachen und Formale Sprachen und AutomatenAutomaten

Klaus Becker2004

Formale SprachenFormale Sprachen

! Terminalsymbole

ATagZustand = '<' z '>' ETagZustand = '<' '/' z '>' ATagZustandsmenge = '<' z m '>' ETagZustandsmenge = '<' '/' z m '>' Bezeichner = {Alphanumeric}+

! Produktionen

"Start Symbol" = <Zustandsmenge>

<Zustand> ::= ATagZustand Bezeichner ETagZustand<Zustaende> ::= <Zustand> <Zustaende> ::= <Zustand> <Zustaende><Zustandsmenge> ::= ATagZustandsmenge <Zustaende>

ETagZustandsmenge

enTeil 1 Teil 1

Sprachbeschreibung und Spracherkennung

Exkurs: XMLExkurs: XML

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> <anfangszustand> <zustand>off</zustand> </anfangszustand> <ueberfuehrungsfunktion> <delta>off,Schalter,low</delta> <delta>low,Schalter,high</delta> <delta>high,Schalter,off</delta> </ueberfuehrungsfunktion> <ausgabefunktion> <lambda>off,Schalter,AnAus</lambda> <lambda>low,Schalter,AnAn</lambda> <lambda>high,Schalter,AusAus</lambda> </ausgabefunktion> </automat>

Was ist XML?Was ist XML?

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> ...</automat>

„XML (Abk. für extended markup language) ist eine Metasprache zur Beschreibung von Auszeichnungssprachen für allgemeine Dokumente.“ (Duden Informatik)

Mit Hilfe von XML kann man Informationen strukturiert darstellen. Des weiteren kann man die Struktur (und die Formatierung) von Dokumenten festlegen, d. h. man kann die Sprache festlegen, in der die Dokumente verfasst werden müssen.

Darstellung von XML-DokumentenDarstellung von XML-Dokumenten

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> <anfangszustand> <zustand>off</zustand> </anfangszustand> <ueberfuehrungsfunktion> <delta>off,Schalter,low</delta> <delta>low,Schalter,high</delta> <delta>high,Schalter,off</delta> </ueberfuehrungsfunktion> <ausgabefunktion> <lambda>off,Schalter,AnAus</lambda> <lambda>low,Schalter,AnAn</lambda> <lambda>high,Schalter,AusAus</lambda> </ausgabefunktion> </automat>

Browser-Ansicht

XML-Dokument

Ein fehlerhaftes DokumentEin fehlerhaftes Dokument

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high<zustand> </zustandsmenge> <anfangszustand> <zustand>off</zustand> </anfangszustand> ...</automat>

Der Browser erkennt, wenn ein allgemeiner Syntaxfehler vorliegt (hier: kein passendes Ende-Tag gefunden).

Noch ein fehlerhaftes DokumentNoch ein fehlerhaftes Dokument

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge>  <ueberfuehrungsfunktion> <delta>off,Schalter,low</delta> <delta>low,Schalter,high</delta> <delta>high,Schalter,off</delta> </ueberfuehrungsfunktion> ...</automat>

Der Browser erkennt aber nicht, wenn ein spezieller Syntaxfehler vorliegt (hier: betrifft die vom Benutzer vorgesehene Struktur des Dokuments).

Festlegung der DokumentenstrukturFestlegung der Dokumentenstruktur

<?xml version="1.0"?><!DOCTYPE automat [ <!ELEMENT automat (zustandsmenge?, anfangszustand, eingabemenge?, ausgabemenge?, ueberfuehrungsfunktion, ausgabefunktion)> <!ATTLIST automat name CDATA #REQUIRED> <!ELEMENT zustandsmenge (zustand)+> <!ELEMENT anfangszustand (zustand)> <!ELEMENT zustand (#PCDATA)> <!ELEMENT eingabemenge (eingabe)+> <!ELEMENT eingabe (#PCDATA)> <!ELEMENT ausgabemenge (ausgabe)+> <!ELEMENT ausgabe (#PCDATA)> <!ELEMENT ueberfuehrungsfunktion (delta)*> <!ELEMENT delta (#PCDATA)> <!ELEMENT ausgabefunktion (lambda)*> <!ELEMENT lambda (#PCDATA)> ]><automat name="Klimaanlage2">...</automat>

Dokument mit festgelegtem TypDokument mit festgelegtem Typ

<?xml version="1.0"?><!DOCTYPE automat [ <!ELEMENT automat (zustandsmenge?, anfangszustand, eingabemenge?, ausgabemenge?, ueberfuehrungsfunktion, ausgabefunktion)> <!ATTLIST automat name CDATA #REQUIRED> <!ELEMENT zustandsmenge (zustand)+> <!ELEMENT anfangszustand (zustand)> <!ELEMENT zustand (#PCDATA)> <!ELEMENT eingabemenge (eingabe)+> <!ELEMENT eingabe (#PCDATA)> <!ELEMENT ausgabemenge (ausgabe)+> <!ELEMENT ausgabe (#PCDATA)> <!ELEMENT ueberfuehrungsfunktion (delta)*> <!ELEMENT delta (#PCDATA)> <!ELEMENT ausgabefunktion (lambda)*> <!ELEMENT lambda (#PCDATA)> ]><automat name="Klimaanlage2">...</automat>

Aktivierung des ParserAktivierung des Parser

<HTML>

<HEAD> <TITLE>Automatenbeschreibungstest</TITLE> <SCRIPT LANGUAGE="JavaScript" FOR="window" EVENT="ONLOAD"> Document = Test.XMLDocument; message = "parseError.errorCode: „ + Document.parseError.errorCode + "\nl„ + "parseError.filepos: „ + Document.parseError.filepos + "\nl„ + "parseError.line: „ + Document.parseError.line + "\nl„ + "parseError.linepos: „ + Document.parseError.linepos + "\nl„ + "parseError.reason: „ + Document.parseError.reason + "\nl„ + "parseError.srcText: „ + Document.parseError.srcText; alert (message); </SCRIPT></HEAD>

<BODY><XML ID="Test" SRC="Klimaanlage2.XML"></XML><H2>DTD Automatentest</H2></BODY>

</HTML>

nach J. Müller: XML, Teil 4. In: LOG IN 122/123 (2003)

<HTML>

</HTML>

<HTML>

</HTML>

Korrekte AutomatenbeschreibungKorrekte Automatenbeschreibung<?xml version="1.0"?><!DOCTYPE automat [ ... ]><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> <anfangszustand> <zustand>off</zustand> </anfangszustand> ...</automat>

<?xml version="1.0"?><!DOCTYPE automat [ ... ]><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> <anfangszustand> <zustand>off</zustand> </anfangszustand> ...</automat>

Der Parser überprüft die Dokumentenstruktur.

<HTML>

</HTML>

<HTML>

</HTML>

Fehlerhafte AutomatenbeschreibungFehlerhafte Automatenbeschreibung<?xml version="1.0"?><!DOCTYPE automat [ ... ]><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge>  ...</automat>

<?xml version="1.0"?><!DOCTYPE automat [ ... ]><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge>  ...</automat>

Der Parser erkennt einen Syntaxfehler.

ÜbersichtÜbersicht

Aus: M. Näf: Einführung in XML, DTD und XSL. www.internet-kompetenz.ch/xml/

ZielsetzungZielsetzung

Ziel ist es, Verfahren zur präzisen Festlegung von Sprachen (wie der Automatenbeschreibungssprache) zu entwickeln.

<?xml version="1.0"?><!DOCTYPE automat [ <!ELEMENT automat (zustandsmenge?, anfangszustand, eingabemenge?, ausgabemenge?, ueberfuehrungsfunktion, ausgabefunktion)> <!ATTLIST automat name CDATA #REQUIRED> <!ELEMENT zustandsmenge (zustand)+> <!ELEMENT anfangszustand (zustand)> <!ELEMENT zustand (#PCDATA)> <!ELEMENT eingabemenge (eingabe)+> ... ]><automat name="Klimaanlage2">...</automat>

Ziel ist es, Systeme zu entwickeln, mit deren Hilfe man entscheiden kann, ob eine „sprachliche Beschreibung“ (wie eine Automatenbeschreibung) korrekt oder fehlerhaft ist.

<?xml version="1.0"?><!DOCTYPE automat [ ... ]><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge>  ...</automat>

enTeil 2 Teil 2

Sprachbeschreibung mit Grammatiken

Die Sprache der ZustandsmengenDie Sprache der Zustandsmengen

Das präzise Festlegen einer Sprache soll zunächst anhand einer übersichtlichen, vereinfachten Teilsprache der XML-Automatenbeschreibungssprache entwickelt werden. Wir betrachten hierzu die Beschreibung von Zustandsmengen, die in verkürzter Form dargestellt werden.

Informelle BeschreibungInformelle Beschreibung

Regeln:Regeln:

/1/ Eine Zustandsmengenbeschreibung wird durch die Tags <zm> und </zm> eingeschlossen.

/2/ Sie enthält beliebig viele, aber mindestens einen Zustand.

/3/ Jeder Zustand wird durch die Tags <z> und </z> eingeschlossen.

Das Alphabet einer SpracheDas Alphabet einer Sprache

= {<, >, /, a, ..., z, A, ..., Z, 0, ..., 9}

Das Alphabet der Zustandsmengen-Sprache:Das Alphabet der Zustandsmengen-Sprache:

Jede Sprache benutzt bestimmte Zeichen, um Wörter bzw. Sätze zu bilden. Die Menge der zulässigen Zeichen wird Alphabet genannt. Ein Alphabet ist somit eine endliche (geordnete) Menge von Zeichen.

Zustandsmengenbeschreibung:Zustandsmengenbeschreibung:

Wörter über einem AlphabetWörter über einem Alphabet

= {<, >, /, a, ..., z, A, ..., Z, 0, ..., 9}

Durch Hintereinanderreihung endlich vieler Zeichen aus dem vorgegebenen Alphabet erhält man Wörter (über dem Alphabet). Die Menge aller möglichen Wörter über einem Alphabet wird mit * bezeichnet. Zu dieser Menge gehört auch das sogenannte leere Wort , das keine Zeichen enthält.

Das Alphabet der Zustandsmengen-Sprache:Das Alphabet der Zustandsmengen-Sprache:

Wörter über diesem Alphabet:Wörter über diesem Alphabet:

<zm><z>rotgelb</z></zm>

<a><z3

Formale SprachenFormale Sprachen

Eine (formale) Sprache über einem Alphabet ist eine Teilmenge von *. Eine (formale) Sprache über einem Alphabet ist eine Teilmenge von *.

Wörter, die zur Zustandsmengen-Sprache gehören:Wörter, die zur Zustandsmengen-Sprache gehören:

<zm><z>rotgelb</z></zm>

<a><z3

<zm><z>rotgelb<z><zm>

Wörter, die nicht zur Zustandsmengen-Sprache gehören:Wörter, die nicht zur Zustandsmengen-Sprache gehören:

Problem: Festlegung aller Wörter, die zur Sprache gehörenProblem: Festlegung aller Wörter, die zur Sprache gehören

SyntaxdiagrammeSyntaxdiagramme

ATagZustand

ETagZustand

< / z >

ATagZustandsmenge

ETagZustandsmenge

< / z m

SyntaxdiagrammeSyntaxdiagramme

AlphanumerischesZeichen

a b ... A B ... 0 1 ...

Bezeichner

Zustand

Bezeichner

ATagZustand

ETagZustand

Bestandteile von SyntaxdiagrammeBestandteile von Syntaxdiagramme

Terminalsymbole gehören zum Alphabet der Sprache.

Nichtterminalsymbole sind Variablen, die als Platzhalter für syntaktische Einheiten fungieren.

Terminalsymbole gehören zum Alphabet der Sprache.

Nichtterminalsymbole sind Variablen, die als Platzhalter für syntaktische Einheiten fungieren.

a b ... A B ... 0 1 ...

Bezeichner

Terminalsymbol

Nichtterminalsymbol

enÜbungÜbung

Ergänzen Sie die Sprachbeschreibung um Syntaxdiagramme für Zustandsmengen. Beachten Sie, dass eine Zustandsmenge beliebig viele, aber mindestens einen Zustand hat.

ATagZustandsmenge

LösungLösung

Zustand

Zustandsmenge

ETagZustandsmenge

Übersetzung in ProduktionsregelnÜbersetzung in Produktionsregeln

<ATagZustand> '<' 'z' '>'

ATagZustand

<AlphanumerischesZeichen> 'a'

a b ... A B ... 0 1 ...

<AlphanumerischesZeichen> 'b'

Bezeichner

enÜbungÜbung

Ergänzen Sie die fehlenden Produktionsregeln. Ergänzen Sie die fehlenden Produktionsregeln.

enLösungLösung

GrammatikGrammatik

Eine Grammatik ist ein Tupel G = (T, N, P, S) bestehend aus - einer endlichen nichtleeren Menge T von Terminalzeichen,- einer endlichen nichtleeren Menge N von Nichtterminalzeichen,- einer endlichen Menge P von Produktionen (Regeln) und- einem Startsymbol S N.

Eine Produktion (Regel) hat die Gestalt u v. Die linke Seite u und die rechte Seite v sind dabei Wörter über dem Alphabet V = T N.

Backus-Naur-FormBackus-Naur-Form

<AlphanumerischesZeichen> ::= 'a' | 'b' | .. | 'A' | 'B' | .. | '0' | ..

Die Backus-Naur-Form ist eine Kurzschreibweise für Produktionen.Die Backus-Naur-Form ist eine Kurzschreibweise für Produktionen.

<AlphanumerischesZeichen> 'a'

<AlphanumerischesZeichen> 'b'

enÜbungÜbung

Beschreiben Sie die gesamte Grammatik der Zustandsmengen-sprache in Backus-Naur-Form.Beschreiben Sie die gesamte Grammatik der Zustandsmengen-sprache in Backus-Naur-Form.

WortproblemWortproblem

Beispiel: <zm><z>z0</z></zm>

Ableitung durch Wortersetzung:

Eine Produktion u v wird so interpretiert, dass u überall, wo es als Teil eines Wortes auftritt, durch v ersetzt werden darf.

Gegeben: Wort über dem Alphabet T Gegeben: Wort über dem Alphabet T

Gesucht: Ableitung des Wortes mit Hilfe der Produktionen der Grammatik ausgehend vom StartzustandGesucht: Ableitung des Wortes mit Hilfe der Produktionen der Grammatik ausgehend vom Startzustand

WorterzeugungWorterzeugung

<Zustandsmenge> <ATagZustandsmenge> <Zustaende> <ETagZustandsmenge> '<' 'zm' '>' <Zustaende> <ETagZustandsmenge> '<' 'zm' '>' <Zustaende> '<' '/' 'zm' '>' '<' 'zm' '>' <Zustand> '<' '/' 'zm' '>' '<' 'zm' '>' <ATagZustand> <Bezeichner> <ETagZustand> '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' <Bezeichner> <ETagZustand> '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' <Alphan.Zeichen> <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' 'z' <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' 'z' <AlphanumerischesZeichen> '<' '/' 'z' '>' '<' '/' 'zm' '>' '<' 'zm' '>' '<' 'z' '>' 'z' '0' '<' '/' 'z' '>' '<' '/' 'zm' '>'

Gegeben: <zm><z>z0</z></zm>Gegeben: <zm><z>z0</z></zm>

Gesucht: Ableitung des Wortes mit Hilfe der ProduktionenGesucht: Ableitung des Wortes mit Hilfe der Produktionen

Startsymbol

Wort aus Terminalsymbolen

enÜbungÜbung

Kommentieren Sie die Ableitung, indem Sie für jeden Ersetzungs-schritt die benutzte Grammatikregel (Produktion) angeben.

'<' 'zm' '>' <Zustaende> <ETagZustandsmenge>

'<' 'zm' '>' <Zustaende> '<' '/' 'zm' '>'

'<' 'zm' '>' <Zustand> '<' '/' 'zm' '>'

'<' 'zm' '>' <ATagZustand> <Bezeichner> <ETagZustand> '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' <Bezeichner> <ETagZustand> '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' <Alphan.Zeichen> <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' 'z' <Bezeichner> '<' '/' 'z' '>' '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' 'z' <AlphanumerischesZeichen> '<' '/' 'z' '>' '<' '/' 'zm' '>'

'<' 'zm' '>' '<' 'z' '>' 'z' '0' '<' '/' 'z' '>' '<' '/' 'zm' '>'

enTeil 3 Teil 3

Ein Werkzeug zur Sprachbeschreibung

Spracherkennung mit WerkzeugenSpracherkennung mit Werkzeugen

Siehe: www.devincook.com/goldparser/

Zwei-Stufen-BeschreibungZwei-Stufen-Beschreibung

Oft ist eine zweistufige Beschreibung der Sprache zweckmäßig:Oft ist eine zweistufige Beschreibung der Sprache zweckmäßig:

Zeichen:Zeichen:

<zm>, <z>, rotgelb, gruen, ...

<zm><z>rotgelb</z></zm>, <zm></z>, ...

Sätze / Tokenfolgen:Sätze / Tokenfolgen:

Wörter / Token:Wörter / Token:

<, >, /, a, ..., z, A, ..., Z, 0, ..., 9

Festlegung der korrekten Token (Wörter)

Festlegung der korrekten Tokenfolgen (Sätze)

Sprache der TokenSprache der Token

Alphabet:Alphabet:

= {<, >, /, a, ..., z, A, ..., Z, 0, ..., 9}

<ATagZustand> ::= '<' 'z' '>'

<AlphanumerischesZeichen> ::= 'a' | 'b' | .. | 'A' | 'B' | .. | '0' | ..

<ETagZustand> ::= '<' '/' 'z' '>'

<ATagZustandsmenge> ::= '<' 'z' 'm' '>'

<ETagZustandsmenge> ::= '<' '/' 'z' 'm' '>'

Grammatik:Grammatik:

Sprache der TokenfolgenSprache der Tokenfolgen

Alphabet:Alphabet:

= {<z>, </z>, <zm>, </zm>, ..., rotgelb, ..., gruen, ...}

<Bezeichner> ::= ... | rotgelb | ... | gruen | ...

<Zustand> ::= '<z>' <Bezeichner> '</z>'

<Zustandsmenge> ::= '<zm>' <Zustaende> '</zm>'

Darstellung einer GrammatikDarstellung einer Grammatik

! Terminalsymbole

ATagZustand = '<' z '>' ETagZustand = '<' '/' z '>' ATagZustandsmenge = '<' z m '>' ETagZustandsmenge = '<' '/' z m '>' Bezeichner = {Alphanumeric}+

! Produktionen

"Start Symbol" = <Zustandsmenge>

<Zustand> ::= ATagZustand Bezeichner ETagZustand<Zustaende> ::= <Zustand> <Zustaende> ::= <Zustand> <Zustaende><Zustandsmenge> ::= ATagZustandsmenge <Zustaende>

ETagZustandsmenge

Zwei-stufige Darstellung beim Werkzeug „GOLD Parser Builder“ Zwei-stufige Darstellung beim Werkzeug „GOLD Parser Builder“

Produktionen in BNF

Reguläre Ausdrücke

AbleitungsbaumAbleitungsbaum

ZustandsautomatZustandsautomat

Zur Analyse der Terminalsymbole benutzt das Werkzeug „GOLD Parser Builder“ einen Automaten.

enÜbungÜbung

Aufgabe 1Testen Sie das Werkzeug am Beispiel der Zustandsmengensprache.

Aufgabe 2Erstellen Sie eine vollständige Grammatik zur Automaten-beschreibungssprache mit Hilfe des Werkzeugs.

Exkurs: Verknüpfung von SprachenExkurs: Verknüpfung von SprachenX und Y seien Sprachen über dem Alphabet .

XY = {xy | xX, yY} ist die Menge aller Worte, die sich ergeben, wenn man an ein beliebiges Wort aus X ein beliebiges Wort aus Y hängt.

X0 = {}; X1 = X; X2 = XX; X3 = X2X = XXX; ...

X* = X0 X1 X2 X3 … ist die Menge aller Worte, die sich ergeben, wenn man beliebig viele (auch keine) Worte aus X aneinanderhängt.

X+ = X1 X2 X3 X4 … ist die Menge aller Worte, die sich ergeben, wenn man beliebig viele Worte, aber mindestens ein Wort, aus X aneinanderhängt.

X und Y seien Sprachen über dem Alphabet .

XY = {xy | xX, yY} ist die Menge aller Worte, die sich ergeben, wenn man an ein beliebiges Wort aus X ein beliebiges Wort aus Y hängt.

X0 = {}; X1 = X; X2 = XX; X3 = X2X = XXX; ...

X* = X0 X1 X2 X3 … ist die Menge aller Worte, die sich ergeben, wenn man beliebig viele (auch keine) Worte aus X aneinanderhängt.

X+ = X1 X2 X3 X4 … ist die Menge aller Worte, die sich ergeben, wenn man beliebig viele Worte, aber mindestens ein Wort, aus X aneinanderhängt.Beispiele:

Sei X = {a, b}; Y = {c}.

XY = {ac, bc}

X0 = {}; X1 = X = {a, b}; X2 = XX = {aa, ab, ba, bb}

X* = X0 X1 X2 X3 … = {, a, b, aa, ab, ba, bb, ...}

X+ = X1 X2 X3 X4 … = {a, b, aa, ab, ba, bb, ...}

Exkurs: Reguläre AusdrückeExkurs: Reguläre Ausdrücke

Gebeben sei das Alphabet . ist ein regulärer Ausdruck, der die leere Menge {} bezeichnet. ist ein regulärer Ausdruck, der die Menge {} mit dem leeren Wort bezeichnet.Für jedes a ist a ein regulärer Ausdruck, der die Menge {a} bezeichnet.Sind x und y reguläre Ausdrücke, die die Mengen X und Y bezeichnen, so ist auch- (x+y) ein regulärer Ausdruck, der die Menge XY bezeichnet,- xy ein regulärer Ausdruck, der die Menge XY bezeichnet,- (x)* ein regulärer Ausdruck, der die Menge X* bezeichnet,- (x)+ ein regulärer Ausdruck, der die Menge X+ bezeichnet,

Beispiele: Sei = {a, b, c}.

(a+b)* = ({a}{b})0 ({a}{b})1 ({a}{b})2 …

= {, a, b, aa, ab, ba, ...}

a+b*c = ({a}1 {a}2 {a}3 …) ({b}0 {b}1 {b}2 …)({c})

= {ac, aac, aaac, …, abc, aabc, aaabc, …, abbc, aabbc, aaabbc, …}

= {aibjc | i >0; j 0}

Darstellung und Test regulärer Darstellung und Test regulärer AusdrückeAusdrücke

! Regulärer AusdruckL = a[a|b]*c

"Start Symbol" = <S><S> ::= L

a(a+b)*c

Beispiel 1: Beispiel 1:

! Regulärer AusdruckL = b[a]*|[b]+

ba*+b+

! Regulärer AusdruckL = A{Letter}*n

A(a+b+...+Z)*n

enÜbungÜbung

Erstellen Sie reguläre Ausdrücke zur Beschreibung folgender Mengen:

(a) Die Menge aller Zeichenketten über dem Alphabet {0, 1}, die mit 00 enden.

(b) Die Menge aller Zeichenketten über dem Alphabet {a, b}, die mit a beginnen oder mit b enden.

(c) Die Menge aller Zeichenketten über dem Alphabet {a, b}, die nach jedem a genau zwei b´s haben.

(d) Alle Namen über dem Standardalphabet, die mit A anfangen.

(e) Die Menge folgender Klassen: {5a, 5b, 5c, ..., 10a, 10b, 10c}.

(f) Die Menge zulässiger Zeitangaben; z. B. 12:00.

enÜbungÜbung

Wir betrachten Adressen nach dem http-Protokoll mit folgendem Aufbau:

http://www.hostname.subdomain.....domain.topleveldomain

Beispiel:

http://www.google.de

Der Einfachheit halber sollen alle Domainnamen nur aus Buchstaben bestehen.

Entwickeln Sie eine Grammatik zur Beschreibung solcher Adressen. Testen Sie die Grammatik.

enÜbungÜbung

HTTP-date = rfc1123-date | rfc850-date | asctime-date

rfc1123-date = wkday "," SP date1 SP time SP "GMT"

rfc850-date = weekday "," SP date2 SP time SP "GMT"

asctime-date = wkday SP date3 SP time SP 4DIGIT

date1 = 2DIGIT SP month SP 4DIGIT

date2 = 2DIGIT "-" month "-" 2DIGIT

date3 = month SP ( 2DIGIT | ( SP 1DIGIT ))

time = 2DIGIT ":" 2DIGIT ":" 2DIGIT

wkday = "Mon" | "Tue" | "Wed" | "Thu" | "Fri" | "Sat" | "Sun"

month = "Jan" | "Feb" | "Mar" | "Apr" | "May" | "Jun" | "Jul" | "Aug" | "Sep" | "Oct" | "Nov" | "Dec"

Im Internet-Standarddokument (Request for Comment) RCF1945 für das HTTP-Protokoll findet man die folgende Grammatik für erlaubte Datum-Uhrzeit-Formate.

Ergänzen Sie geeignete Grammatikregeln für SP, 1DIGIT, 2DIGIT, 4DIGIT. Erzeugen Sie verschiedene korrekte Datum-Uhrzeit-Angaben.

enTeil 4 Teil 4

Spracherkennung mit Automaten

Ziel ist es, Spracherkennungssysteme zu entwickeln.

Ein Spracherkennungssystem soll bei Eingabe eines beliebigen Wortes entscheiden, ob dieses Wort zur vorgegebenen Sprache gehört oder nicht.

Ziel ist es, Spracherkennungssysteme zu entwickeln.

Ein Spracherkennungssystem soll bei Eingabe eines beliebigen Wortes entscheiden, ob dieses Wort zur vorgegebenen Sprache gehört oder nicht.

Wort ja / nein

Vereinfachte BezeichnerVereinfachte Bezeichner

Beispiel: Das System soll vereinfachte Bezeichner erkennen:Beispiel: Das System soll vereinfachte Bezeichner erkennen:

Regeln zur Bildung vereinfachter Bezeichner

/1/ Der Bezeichner beginnt mit einem z.

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

Beispiele für korrekte vereinfachte Bezeichner:

z0, z10, z01101, z000000

Beispiele für nicht-korrekte vereinfachte Bezeichner:

0z, z10z, z01a, z

Erzeugende SystemeErzeugende Systeme

Spracherkennungsansatz: Erzeugung von AbleitungenSpracherkennungsansatz: Erzeugung von Ableitungen

Alphabet:Alphabet:

= {z, 0, 1, a}

B zNN 0 N 1N 0N N 1N

B zN z1 # z1N z10 # z10N...

Erzeugung von Ableitungen:Erzeugung von Ableitungen:

Wort:Wort:

Erzeuge systematisch Ableitungen mit Hilfe von Grammatikregeln und überprüfe, ob das gegebene Wort auf diese Weise erzeugt werden kann.

Analysierende SystemeAnalysierende Systeme

Spracherkennungsansatz: Zustandsbasierte WortanalyseSpracherkennungsansatz: Zustandsbasierte Wortanalyse

Verarbeite das Wort mit Hilfe eines erkennenden Automaten: Überprüfe, ob das gegebene Wort den Automaten vom Anfangszustand in einen Endzustand überführt.

Endzustand

Anfangszustand

Erkennende AutomatenErkennende Automaten

Zustandsmenge: Z = {Z0, Z1, Z2, Z3}

Anfangszustand: za = Z0

Endzustände: Ze = {Z2}

Eingabemenge: E = {z, a, 0, 1}

Überführungsfunktion: : (Z0, z) Z1; (Z0, a) Z3; ...

Ein erkennender Automat / Akzeptor ist ein Tupel A = (Z, za, Ze, E, ) bestehend aus - einer endlichen Menge Z von Zuständen,- einem Anfangszustand za Z,- einer Menge Ze Z von Endzuständen,- einer endlichen Menge E von Eingabezeichen und- einer Überführungsfunktion : Z x E Z.

Die Sprache eines AkzeptorsDie Sprache eines Akzeptors

Sei A = (Z, za, Ze, E, A, ) ein Akzeptor. Unter der Sprache L(A) dieses Akzeptors versteht man die Menge aller Wörter über dem Alphabet E, die den Automaten vom Anfangszustand za in einen Endzustand aus Ze überführen.

L(A) = {z0, z1, z00, z01, z10, z11, ...}

enÜbungÜbung

Ein Akzeptor soll Zustandsbeschreibungen der folgenden Form akzeptieren:

<z><z>AAA<z>AA</z>BB<z>BB<z>BBBAAAB<z>BBABB</z>

Bem.: A steht für ein beliebiges alphanumerisches Zeichen; B steht für ein Leerzeichen (blank).

Werkzeuge: Automaton Simulator, Charon

enÜbungÜbung

Ein Akzeptor soll Zahlen mit folgendem Format akzeptieren:

3.0E-12

0.24E3

Präzisieren Sie zunächst die Grammatik dieser Zahldarstellung. Entwickeln Sie anschließend einen geeigneten Akzeptor.

Werkzeuge: GOLD Parser Builder, Automaton Simulator, Charon

enTeil 5 Teil 5

Scanner und Parser

AutomatenbeschreibungsübersetzerAutomatenbeschreibungsübersetzer

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high</zustand> </zustandsmenge> ...</automat>

<?xml version="1.0"?><automat name="Klimaanlage"><zustandsmenge><zustand>off</zustand><zustand>low</zustand><zustand>high</zustand></zustandsmenge>...</automat>

Fehler

Übersetzer

<?xml version="1.0"?><automat name="Klimaanlage"> <zustandsmenge> <zustand>off</zustand> <zustand>low</zustand> <zustand>high<zustand> </zustandsmenge> ...</automat>

Vereinfachung: Vereinfachung: ZustandsmengenübersetzerZustandsmengenübersetzer

Fehler

Übersetzer

enScannerScanner

Scanner

<zm><z>off<z>!

Führt die lexikalische

Analyse durch

Erzeugt lexikal.

Einheiten (Token)

enParserParser

Parser

<zm><z>off</z>!

Führt eine syntaktische

Analyse durch

Erzeugt „Verarbeitungs-programm“ in Normalform

Scanner als AkzeptorScanner als Akzeptor

Verarbeite jedes Zeichen des Quelltextes.Wenn ein Endzustand verlassen wird,dann mache aus den verarbeiteten Zeichen ein neues Token.

Parser als AkzeptorParser als Akzeptor

Verarbeite jedes Token der Tokenfolge.Wenn ein Endzustand verlassen wird,dann mache aus den verarbeiteten Token eine neue Verarbeitungseinheit.

enAuftragAuftrag

Es sollen Programme entwickelt werden, mit deren Hilfe man Automatenbeschreibungen (vereinfachte Zustandsmengen) scannen bzw. parsen kann.

Scanner-PrototypScanner-Prototyp

Scan-Automat

Quelltext

Tokenfolge

KlassendiagrammKlassendiagramm

Scan-AlgorithmusScan-Algorithmus

beginautomat.anfangszustand;Token := '';for i := 0 to Quelltext.Count-1 do begin zeile := Quelltext[i]; for j := 1 to length(zeile) do begin e := zeile[j]; aZ := automat.getZustand; if automat.endzustand then eZ := true else eZ := false; automat.neuerZustand(e); nZ := automat.getZustand; if (eZ and (nZ <> aZ)) then begin Tokenfolge.Add(Token); Token := ''; end; if e <> ' ' then Token := Token + e; end; end;if automat.endzustand then Tokenfolge.Add(Token);end;

enÜbungÜbung

Testen Sie den Scanner. Geben Sie hierzu zunächst den entwickelten Scan-Automaten für Zustandsmengen ein. Testen Sie dann verschiedene korrekte und fehlerhafte Zustandsmengenbeschreibungen.

Parser-PrototypParser-Prototyp

Parse-Automat

Tokenfolge

Generierter Code

KlassendiagrammKlassendiagramm

Parse-AlgorithmusParse-Algorithmus

beginautomat.anfangszustand;Code := '';for i := 0 to Quelltext.Count-1 do begin Token := Quelltext[i]; aZ := automat.getZustand; if automat.endzustand then eZ := true else eZ := false; automat.neuerZustand(Token); nZ := automat.getZustand; if (eZ and (nZ <> aZ)) then begin Tokenfolge.Add(Code); Code := ''; end; Code := Code + Token; end;if automat.endzustand then Tokenfolge.Add(Token);end;

enÜbungÜbung

Testen Sie den Parser. Geben Sie hierzu zunächst den entwickelten Parse-Automaten für Zustandsmengen ein. Testen Sie dann verschiedene korrekte und fehlerhafte Zustandsmengenbeschreibungen.

LiteraturhinweiseLiteraturhinweise

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

Jürgen Müller: XML. Teil 1 - 4. LOG IN 5-6 (2001), Nr. 120 (2002), Nr. 121 (2002), Nr. 122/123 (2002).

Selfhtml von Stefan Münz: http://selfhtml.teamone.de/xml/

Linksammlung von Klaus Merkert: http://hsg.region-kaiserslautern.de/faecher/inf/material/xml/index.php

Formale Sprachen und Automaten Klaus Becker 2004

Documents

17. Theorietag Automaten und Formale Sprachentheo.cs.ovgu.de/autofosp/tt-baende/2007-Theorietag17-Leipzig.pdf · jectured that Word Equations is NP-complete. This is a dramatic change

KONTEXTFREIE GRAMMATIK Theoretische Informatik: Formale Sprachen/Automaten

Zweck - Sascha · PDF fileEndliche Automaten — 1 Endliche Automaten ƒbersicht Einf hrung Beispiel: Der Lachautomat Deterministische vs. Nicht-Deterministische Endliche Automaten

Formale Sprachen und Automaten

Theoretische Informatik Sommersemester 2015 · BAI-4 Fr 12:00 { 14:00 LK052 Deutsch Barbara K onig Automaten und Formale Sprachen 5. OrganisatorischesEinf uhrung Chomsky-HierarchieRegul

Automaten und Formale Sprachen Skript zur Vorlesung WS ... · Text oder eine endliche Struktur zu beschreiben. Als Beispiel fur eine solche endliche¨ Beschreibung sei die bekannte

1 Formale Grundlagen der Faktenextraktion mit endlichen Automaten Karin Haenelt 27.11.2011

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

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

Automaten und Formale Sprachen Sommersemester 2018 · sobald man einen Drachen damit get otet hat. Auˇerdem werden Drachen sofort wieder \ersetzt". Es gibt jedoch immer noch die

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

Theoretische Informatik mit AtoCC: Formale Sprachen, abstrakte Automaten und Compiler. Einsatz der Software AtoCC (Kurs: 07F305201) Fortbildungsveranstaltung

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

Formale Sprachen Teil 1 Klaus Becker 2006. 2 Sprachbeschreibung und -erkennung Sprachbeschreibung mit Grammatiken, Syntaxdiagrammen, regulären Ausdrücken

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

Spracherkennung mit Automaten Klaus Becker 2013. 2 Spracherkennung mit Automaten 0 11 0

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

FORMALE SPRACHEN UND AUTOMATEN Fachdidaktik Informatik SS09 von Benjamin Seiler

7.1 Deterministische endliche Automaten 7.2 ... 07 endliche automaten 1.pdf · Automat Eingabe Ausgabe Prof. Dr. H. Koch FH Köln / Campus Gummersbach / Fb Informatik Endliche Automaten

Formale Sprachen und Automaten - DHBW Stuttgarthladik/FLA/Turing-handout.pdf · FormaleSprachenundAutomaten JanHladik DHBW Stuttgart Sommersemester2019 Jan Hladik (DHBW Stuttgart)