© Karin Haenelt, Endliche Automaten, Einführung, V 3.1 - 16.04.2008 ( 1 15.04.2006) 1 Endliche Automaten in der Sprachtechnologie Einführung in den Themenbereich

1© Karin Haenelt , Endliche Automaten, Einführung, V 3.1 - 16.04.2008 (115.04.2006)

Endliche Automaten in der Sprachtechnologie

Einführung in den Themenbereich

Karin Haenelt


Themen• Einführung: Was sind endliche Automaten?

– Namen und Abkürzungen– Beispiele– Komponenten der mengentheoretischen Definition– Typen von Automaten

• Akzeptoren / Transduktoren• deterministisch / nicht-deterministisch / stochastisch

– Charakteristische Eigenschaften endlicher Automaten• Grundlagen: historische und theoretische Einordnung endlicher Automaten

– Automatentheorie– abstrakte Automaten als mathematische Strukturen

• mengentheoretische Sicht• algebraische Sicht

– Theorie formaler Sprachen• Algorithmen und Systemarchitekturen• Ähnliche Modelle: Hidden Markov Models• Natürliche Sprache und Endliche Automaten

– Sprachtheorie– Sprachtechnologie (vielseitig, schnell, robust)


Namen und Abkürzungen

• Endlicher Automat – EA

• Finite State Automaton - FSA

Einführung: Namen und Abkürzungen


Endliche Automaten: Beispiele

anausStart

drücken

drücken

Schalter

drücken aus an an aus

q1q0 q2

Start0

0

1

1

0,1

DEA deterministischer endlicher Automat,

0 1 →q 0 q1 q0

q1 q1 q2 *q2 q2 q2

Hopcroft/Motwani/Ullmann 2001:27,48,49

der alle Ketten aus 0 und 1 mitTeilkette 01 akzeptiert

Einführung: Beispiele


Endlicher Automat: BeispielRegulärer Ausdruck

Endlicher AutomatGraph

Endlicher AutomatZustandsübergangstabelle

de([mnrs]|ssen)

d0 1

e2

m3

nr

5s

4s 7

e6 n

d e m n r s 0 1 1 2 2 3 3 3 4 3 f 4 f 5 5 6 6 7 7 f

Einführung: Beispiele


Komponenten der mengentheoretischen Definition

• endliche Menge von Zuständen (Q)– interne Konfigurationen, in denen sich ein System befinden kann

• zeitliche Ordnung (δ)– definiert die möglichen Sequenzen von Zuständen

• endliche Menge von Eingaben (Σ)– System zeigt abhängig vom aktuellen Zustand eine bestimmte

Reaktion– und geht in einen Folgezustand über

p,q Q

δ(p,i) = q

σ(p,i,q) = o

i Σo Δ

Zustände

Eingabesymbole

Ausgabesymbole

Zustandsübergangsfunktion

Ausgabefunktion

(Q,F,q0,Σ,Δ,,δ,σ,ρ)

p qi

o

Zustand FolgezustandEingabesymbol

Ausgabesymbol

w /

Gewicht

w Gewichte

ρ(p,i,o,q) = w Gewichtungsfunktion

Einführung: Komponenten der mengentheoretischen Definition


Typen endlicher Automaten

• Akzeptoren– Automaten ohne Ausgabe

• Transduktoren– Automaten mit Ausgabe

• deterministisch– jedem Paar [p,i] ist ein Paar [o,q]

eindeutig zugeordnet• nicht-deterministisch

– einem Paar [p,i] können mehreremögliche Paare [o,q] zugeordnet sein

• stochastisch– jedem Paar [p,i] ist für ein Paar [o,q]

ein Wahrscheinlichkeitsmaß zugeordnet

p qio

qi

p

qoi

p :

pq2

q1

io2/w2

io1/w1

pq2

q1

io2

io1

Einführung: Typen endlicher Automaten


Typen endlicher Automaten: Beispiele

Akzeptor Transduktordeterministisch

0 1[ʃ]S

q[t]t

2 3[a]a dt

4[t] tt

0 1S

qt

2 3a

6

d4

t 7

5t

t

stochastisch

0 1S/1

qt/1

2 3a/1

6

d/.654

t/.35 7

5t/1

t/1[t]

0 1[ʃ]S/1

q[t]t/1

2 3[a]a/1

6

[t]d/.65

4

t/.35 7

5t/1

t/1

nicht-deterministisch

01

S

7

t2 3

a

9

d4

tS t a6 8 10

5t

t0 1[ʃ]S

q[t]t

2 3[a]a

6

[t]d

4

t 7

5t

t

[t]

Einführung: Typen endlicher Automaten: Beispiele


Typen endlicher Automaten: Beispiele

Akzeptor Transduktor

0 1S

qt

2 3a

5

dt4

tt tt0 1

[ʃ]S

q[t]t

2 3[a]a dt

4[t]

deterministisch

0 1[ʃ]S/1

q[t]t/1

2 3[a]a/1

5

[t]dt/.65

4

[t]tt/.35

0 1S/1

qt/1

2 3a/1

5

dt/.654

tt/.35

stochastisch

0 1[ʃ]S

q[t]t

2 3[a]a

5

[t]dt

4

[t]tt

01

S

6

t2 3

a

8

dt4

ttS t a5 7

nicht-deterministisch

alternative Modellierung des Anwendungsbeispielsmit direkter Graphem-Phonem-Entsprechungnur sinnvoll für Transduktoren, und nur, wenn sie nur in eine Richtungverwendet werden sollen

Einführung: Typen endlicher Automaten: Beispiele


Charakteristische Eigenschaften endlicher Automaten

B Bu Buc BuchStart B u c h

• Mengen der Zustände, der Eingabesignale, der Ausgabesignale sind endlich• kein Gedächtnis zur Speicherung durchlaufener Zustände:

– Übergang von Zustand zur Zeit t in Zustand zur Zeit t+1 nur abhängig von• Zustand zur Zeit t und • Eingabe im Zustand zur Zeit t

– Vorhergehende Zustände nur dadurch wirksam, dass• sie über eine bestimmte Eingabe in den aktuellen Zustand geführt

haben, und • dieser aktuelle Zustand ein bestimmtes Ergebnis repräsentiert.

Einführung: Charakteristische Eigenschaften endlicher Automaten






– Historisches– Automatentheorie– abstrakte Automaten als mathematische Strukturen





Historische Einordnung endlicher Automaten

• Turingmaschine (Turing, 1936)– Untersuchung der Berechenbarkeit von Funktionen– Entwicklung eines abstrakten Automaten (Turingmaschine): abstraktes

Modell eines Rechners, der mit nur drei Operationen (lesen, schreiben, Lesekopf bewegen) sämtliche berechenbare Probleme lösen kann

– Verwendung der Turingmaschine als Instrument zur Durchführung der Untersuchung und Notation der Ergebnisse

• einfachere Maschinen (endliche Automaten)– Neuronennetze (Modellierung von Netzwerken mit propositionaler Logik und

umgekehrt) (McCulloch/Pitts, 1943)– Schaltkreise und Beschreibung endlicher Automaten (Huffman, 1954),

(Mealy, 1955) und (Moore, 1956)– abstrakte Automaten als mathematische Strukturen eingeführt (Mealy,

1955) und (Moore, 1956)– Modellierung der Neuronennetze mit endlichen Automaten (Kleene, 1956)– Charakterisierung endlicher Automaten als eingeschränkte

Turingmaschinen (Kleene, 1956)

Grundlagen: Historische Einordnung


Automatentheorie• untersucht die theoretischen Grenzen der Berechenbarkeit

– Entscheidbarkeit: Was können Computer überhaupt berechnen?

– Handhabbarkeit und Komplexität: Was können Computer wie effizient berechnen?

Grundlagen: Theoretische Einordnung: Automatentheorie

Automat Speicher Turingmaschine unendlich großer Speicher linear beschränkter Automat endlich großer Speicher Kellerautomat (Push Down Automaton) Kellerspeicher (Stack) endlicher Automat kein zusätzlicher Speicher

Klasse Komplexität Aufwand Bedeutung P polynomial nj

(z.B. n, n log n, n3)

auf deterministischem Computer in polynomialer Zeit lösbar

NP exponentiell 2n auf nicht-deterministischem Computer in polynomialer Zeit lösbar

Speziali-sierungen

• klassifiziert Algorithmen nach der Art des Speichers, der für die Implementierung gebraucht wird


Abstrakter Automat

• ein abstrakter Automat ist ein mathematisches Modell für einfache Maschinen oder Programme, die bestimmte Probleme lösen– Zustände– Eingabesymbole– Zustandsübergänge

Grundlagen: Theoretische Einordnung


Abstrakte Automaten als mathematische Strukturen

• mengentheoretische Definition:– definiert Automaten als Strukturen– gebräuchlichste Definition

• algebraische Automatentheorie– fasst Automaten als algebraische Strukturen auf– behandelt sie in Analogie zur Gruppen- oder

Ringtheorie– untersucht Beziehungen zwischen algebraischen

Strukturen wie Halbgruppen, Gruppen, Ringen und Klassen von Automaten

Grundlagen: Theoretische Einordnung: mathematische Strukturen


Mathematische Strukturen

• Eine Struktur ist eine Zusammenfassung einer– Menge und– ausgewählter interessanter Eigenschaften dieser Menge

• Relationen, Funktionen oder • ausgezeichnete Elemente

zu einem gemeinsamen Objekt

• die Eigenschaften definieren eine Struktur auf der Menge

• Darstellung als Tupel = (Menge, Relation1, …, Relationo,

ausgezeichnetes Element1, …, ausgezeichnetes Elementp)

• BeispielS=(N,+,*)



Mengentheoretische Definition endlicher Automaten – Beispiel 1a

p qi


p,q Q

δ(p,i) = q

i Σ

Zustände

Eingabesymbole


A = (Q, Σ, δ, q0, F)

• endliche Menge von Zuständen (Q)– interne Konfigurationen, in denen sich ein System befinden kann

• zeitliche Ordnung (δ)– definiert die möglichen Sequenzen von Zuständen

• endliche Menge von Eingaben (Σ)– System zeigt abhängig vom aktuellen Zustand eine bestimmte

Reaktion– und geht in einen Folgezustand über


F Q Endzustände

q0 Q Startzustand


Mengentheoretische Definition endlicher Automaten – Beispiel 1b

p,q Q

δ(p,i) = q

σ(p,i,q) = o

i Σ

o Δ

Zustände

Eingabesymbole

Ausgabesymbole


Ausgabefunktion

EA = (Q,q0,F,Σ,Δ,,δ,σ,ρ)

p qi

o


Ausgabesymbol

w /

Gewicht

w Gewichte

ρ(p,i,o,q) = w Gewichtungsfunktion

F Q Endzustände

q0 Q Startzustand



Mengentheoretische Definition endlicher Automaten – Beispiel 2

determinierter abstrakter AutomatA = (X, Y, Z, γ) heißt determinierter abstrakter Automat, falls

a) X, Y, Z beliebige nichtleere Mengen sind, undb) γ eine auf Z X definierte Funktion ist, deren Werte in Y Z liegen. ■

(Starke 1969: 22)

determinierter Mealy-AutomatEin determinierter Automat A = (X, Y, Z, γ) heißt determinierter Mealy-Automat, falls

für alle x X, zZ, γ(z,x) = [λ(z,x),δ(z,x)] ist,

wobei λ die Ergebnis und δ die Überführungsfunktion von A ist. ■ (Starke 1969: 22)

Folgerung: Jeder determinierte Automat ist ein determinierter Mealy-Automat.

endlicher determinierter AutomatA heißt X-endlich, Y-endlich bzw. Z-endlich bzw. (X,Y)-endlich usw., wenn die jeweils

angegebenen Mengen endlich sind. (X,Y,Z)-endliche Automaten bezeichnen wir schlechthin als endlich ■ (Starke 1969: 25)



Mengentheoretische Definition abstrakte Automaten – Beispiel 2

nichtdeterministischer AutomatB = (X, Y, Z, h) heißt nicht-deterministischer Automat, falls

a) X, Y, Z nichtleere Mengen sind, undb) h eine eindeutige Abbildung von Z X in P*(Z X) ist. ■ (Starke

1969: 121)stochastischer AutomatC = (X, Y, Z, H) heißt stochastischer Automat, wenn

a) X, Y, Z beliebige nichtleere Mengen sind, undb) H eine auf Z X definierte Funktion ist, die diskrete

Wahrscheinlichkeitsmaße über Y Z als Werte H(z,x) hat■ (Starke 1969: 211)

endliche nichtdeterministische Automaten … (X,Y,Z)-endlich

endliche stochastische Automaten … (X,Y,Z)-endlich

x X, zZ, γ(z,x) = [λ(z,x),δ(z,x)]



Reguläre Sprachen in der Sprachentheorie

Sprachklasse Hierarchie Grammatik Regelformat Automat rekursiv aufzählbare Sprachen

Typ 0 allgemeine Regelgrammatik

Turing-Maschine

kontext-sensitive Sprachen

Typ 1 kontextsensitive Grammatik

2121 A

linear beschränkter Automat

kontextfreie Sprachen

Typ 2 kontextfreie Grammatik

A Kellerautomat

reguläre Sprachen

Typ 3 reguläre Grammatik arrechtsline

wA

wBA

rlinkslineawA

BwA

Endlicher Automat

Sprachklassen nach struktureller Komplexität (Chomsky-Hierarchie)

le SymbolenonterminaBA ,Kettenterminale w TerminalenNon und Terminalen aus Ketten

Grundlagen: Theoretische Einordnung: Sprachentheorie


Formale SprachenFormale Sprachen sind

– mathematische Modelle– Sprachen, für die eine strikte Definition existiert

Formalen Sprache in der Informatik: Definitionen– Alphabet: nicht-leere Menge von Symbolen

• kann endlich sein (wie das deutsche Alphabet)• oder unendlich (wie die Menge der natürlichen

Zahlen).• Alphabete, die für die Spezifikation von

Sprachen verwendet werden, sind endlich. ■

– Zeichenreihe (Zeichenkette / Wort / String): eine endliche Folge von Symbolen eines bestimmten Alphabets. ■

– formale Sprache: Menge von Wörtern, die aus den Elementen eines Alphabets gebildet werden. ■

Beispiele

Σ = {A, B, ..., z},

abc, hallo, xy, …

L1 = {abc, def, ghi},L2 = {qua, qui, quo}, …



Formale Sprachen

• Um eine Sprache benutzen zu können, benötigt man eine Berechnungsvorschrift, die angibt, welche Wörter zu einer Sprache gehören und welche nicht.

• Bei endlichen Sprachen kann diese Berechnungsvorschrift darin bestehen, alle Elemente aufzuzählen.

• Für Sprachen mit unendlich vielen Elementen muß es endlich viele Regeln geben, mit denen sich die Ausdrücke dieser Sprache erzeugen lassen.

Hoeppner, 2004



Formale Sprachen und endliche Automaten

Spezifikation Grundlagengebiet Grundlagen ▪ reguläre Ausdrücke Mengen reguläre Mengen

Analysis Reihen, Potenzreihen, formale Potenzreihen

▪ formale Potenzreihen über beliebige Semiringe abstrakte Algebra Mengen, algebraische

Strukturen (Semiringe) ▪ links- oder rechts-

lineare Grammatiken

Grammatiktheorie Ersetzungssysteme, Chomsky-Hierarchie

•endliche Automaten erkennen bzw. generieren reguläre Sprachen

•reguläre Sprachen lassen sich spezifizieren durch



Spezifikation regulärer Sprachen • Spezifikationen durch

– reguläre Ausdrücke, oder

– formale Potenzreihen über beliebige Semiringe, oder

– links- oder rechtslineare Grammatiken

sind insofern äquivalent als sie dieselben Sprachen beschreiben

• theoretisch interessant

• praktisch interessant:

– Formalismen zur Spezifikation der Automaten

– Kriterien zur Bildung abstrakter Datentypen in der Programmierung der Automaten

– Kriterien zur Modularisierung der Modellierung



Reguläre Ausdrücke

Reguläre Ausdrücke, Reguläre Sprachen und Endliche Automaten

spezifizieren

akzeptieren

sind äquivalent

de([mnrs]|“ssen“)

{dem, den, der, des, dessen}

d0 1

e2

m3

nr

5s

4s

7e

6n

Endliche Automaten Reguläre Sprachen



Spezifikationen regulärer Sprachen und Endliche Automaten

EndlicheAutomaten

ReguläreSprachen

ReguläreAusdrücke

spezifizieren

akzeptieren

sind äquivalent

formale Potenzreihenüber beliebige Semiringe

links- oder rechtslineareGrammatiken

( Reguläre Ausdrücke + Modellierung von Gewichten)

( Reguläre Ausdrücke + Modellierung von Gewichten)



Sprachen und Automaten: Äquivalenzen

• Das Alphabet der Sprache ist die Menge der im System auftretenden verschiedenen Ereignisse, und die Sprache entsteht als die Menge der im System möglichen endlichen Ereignisabfolgen.












Algorithmen und Systemarchitekturen

Lexika FSA

Regeln

ReguläreAusdrücke

FST

weight.FST

AutomatenKompilation

Transformation in Automaten

Operationen

-Zustands- übergang-Traversion-Summe-Produkt

Mengen, Zeichenketten, Graphen

Zusammenführung

-Konkatenation-Vereinigung-Durchschnitt-Komposition-Differenz

Optimierung

-Determinisierung-EpsilonEntfernung-Pushing-Minimalisierung

Architektur

-Sequenz-Kaskade

Algorithmen und Systemarchitekturen











Ähnliche Modelle: HMM

Hidden Markov Model

0.2 shallI

will

ich 1.0 werde 0.6 werde 0.7will 0.4 soll 0.3

0.5

Transduktor

0 1 3willich

werde

shallwerdeI

Akzeptor

0 1 2werdeich

werde

Markov Model

ich0.7

...werde

gewichteter Transduktor

0 1 3will /0.5ich

werde

shall /0.2werdeI / 1.0

...werde

...

gewichteter Akzeptor

0 1 30.5ich

werde

0.2soll1.0

...

...

4

2

4

2

4

2

Ähnliche Modelle: HMM









– Sprachtheorie (Linguistik)– Sprachtechnologie (vielseitig, schnell, robust)


Natürliche Sprache und endliche Automaten

• Die Automatentheorie– gibt keine Antwort auf die Frage, mit welchen Zuständen, Eingaben und

Zustandsübergängen ein konkretes Objekt zu modellieren ist,– kann aber dem Erkenntnisgewinn über Objekte dienen. Die Untersuchung,

ob und wieweit ein Objekt (z.B. menschliche Sprache) mit endlichen Automaten modelliert werden kann, führt zu nicht-trivialen Erkenntnissen über die Natur des Objekts.

• Sprachtheorietheoretische Frage:– Sind natürliche Sprachen reguläre Sprachen?

• Sprachtechnologiepraktische Frage:– Welche Eignung haben endliche Automaten für die

Sprachverarbeitung?

Natürliche Sprache und endliche Automaten


Sprachtheoretische Aufgabe

• Seien verschiedene Alphabete– Σ1 = {A, B, ..., z}– Σ2 = {lach, mach, sing, e, st, t, en, ...}– Σ3 = {adje, dete, nomn, verb, ...}– Σx = ...

• Seien die jeweiligen Mengen Σ1* , Σ2

* , Σ3

* , Σx

* , ... die Mengen der

endlichen Sequenzen über diesen Alphabeten• Eine interessante Teilmenge L dieser Sequenzen besteht aus

den Sequenzen, die Wörter, Phrasen, Sätze, ... der deutschen Sprache sind.

• Eine theoretisch und praktisch interessante linguistische Aufgabe ist es, zu untersuchen, welche Teilbereiche einer natürlichen Sprache als reguläre Sprachen beschrieben werden können.

Natürliche Sprache und endliche Automaten: Linguistik


„Typ 3 oder nicht?“

• Menschliche Sprachen– nicht alle Phänomene mit Grammatik vom Typ 3

beschreibbar– viele Phänomene sind mit Grammatik vom Typ 3

beschreibbar

• nicht für alle praktischen Aufgaben ist eine vollständige Sprachverarbeitung unabdingbar

• mit partiellen Lösungen können viele in der Praxis nützliche Werkzeuge entwickelt werden

• Für Massendaten werden effiziente und robuste Verarbeitungsverfahren benötigt

Kunze, 2001 S. 163

Natürliche Sprache und endliche Automaten: Linguistik


Anwendungsgebiete

flaches Parsing

head-modifier-Paare

Textzerlegung

SpracherkennungÜbersetzung

Rechtschreib-Korrektur

LexikaRegeln

AnalyseSyntheseTransfer

Phonologie

Morphologie

Fakten-extraktion

Text:Sprechen

Sprechen:Text

part-of-speechtagging

Natürliche Sprache und endliche Automaten: Sprachtechnologie


Endliche Automaten in der Sprachtechnologie

• direkte Anwendung– Spracherkennung, Sprechen:Text, Text:Sprechen– Übersetzung, Faktenextraktion, Rechtschreibkorrektur, SMS-Lexika

• direkte Anwendung für linguistische Teilaufgaben– Worterkennung, Textzerlegung– Phonologie, Morphologie– part-of-speech-tagging– flaches Parsing– head-modifier-Paare

• Kompakte Repräsentation– Wörterbücher– Systemlexika und lexikalische Regeln

• Morphologie, Phonologie• partielle syntaktische Strukturen (chunks)

– Indexierung von Texten• Grundlage vieler Parsing-Mechanismen

– anwendbar zum Parsing kontextfreier Sprachen (RTN, Woods, 1970)– erweiterbar für Kontext-Abhängigkeiten

• grundlegende Implementierungstechniken



Eigenschaften

• sehr effiziente Verarbeitung– sehr schnell– platzsparend

• mächtige und flexible Werkzeuge– zur Repräsentation

sprachlicher Phänomene undlinguistischer Beschreibungen

– Modellierungsmittel erlauben ein Nebeneinander von• Aufzählungen (Irregularitäten / Lexikon) und• regelhaften Beschreibungen (Regeln) der modellierten Zeichenreihen

– schwache Struktur der Spezifikationen favorisiert Aufzählung gegenüber Erfassung von Regelhaftigkeiten

• massendatentauglich



Attraktivität endlicher Automaten

• Grundlagen– mathematisch wohl-fundiert– daher systematisch und kontrolliert handhabbar

• Softwaretechnik – direkte Umsetzungen in Computerprogramme für

• Datenstrukturen und• Operationen auf den Datenstrukturen

– abstrakte Spezifikation mit regulären Ausdrücken– modulare und inkrementelle Entwicklung durch Komponierbarkeit

von Automaten

• Effizienz– in der Regel besonders effizientes Laufzeit- und

Speicherplatzverhalten.

Attraktivität endlicher Automaten


Anhang: Historisches


Untersuchung der Entscheidbarkeit und Erfindung der Turing-Maschine

• David Hilbert (um 1900). sucht einen Algorithmus, der die Wahrheit bzw. Falschheit jeder mathematischen Aussage bestimmt

• Kurt Gödel (1931). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme“ (Unvollständigkeitssatz)

• Alan Mathison Turing (1936). „On Computable Numbers, With an Application to the Entscheidungsproblem“

– untersucht die Grenzen zwischen dem, was berechenbar ist und was nicht– erfand die Turingmaschine als abstraktes Modell der Berechenbarkeit eines

Problems• abstraktes Modell eines Rechners, der mit nur drei Operationen (lesen,

schreiben, Lesekopf bewegen) sämtliche berechenbare Probleme lösen kann• ein Problem (eine Zahl, eine Funktion, ein Prädikat etc.) heißt berechenbar, wenn

die Lösung von einer Maschine hingeschrieben werden kann.• d.h., wenn es einen Algorithmus gibt, der das Problem in endlich vielen Schritten

berechnet– Neuformulierung der Ergebnisse von Kurt Gödel von 1931

• Verwendung der Notation der Turingmaschine an Stelle Gödels universeller, arithmetisch-basierter formaler Sprache


Neuronennetze und endliche Systeme

• Warren S. McCulloch und Walter Pitts (1943). – allgemein als Beginn des formalen Studiums von Systemen

mit endlichen Zuständen erachtet– Untersuchung des Modells der „neuronalen Netze“– Modellierung von Netzwerken mit propositionaler Logik

und umgekehrt

Abbildung:Hopcroft/Ullman,1979: S. 48)


Schaltkreise, abstrakte Automaten und mathematische Strukturen

• Huffman (1954), George H. Mealy (1955) und Edward F. Moore (1956)– Untersuchung von Schaltkreisen– beschreiben voneinander unabhängig den konventionellen

deterministischen endlichen Automaten in ähnlichen Varianten– Huffman: Entwicklung des Begriffs des abstrakten Automaten– Mealy und Moore: abstrakte Automaten als mathematische

Strukturen eingeführt• Stephen Cole Kleene (1956)

– Modellierung der neuronalen Netze von McCulloch und Pitts durch endliche Automaten

– endliche Automaten als eingeschränkte Turing-Maschine charakterisiert

– Entwicklung regulärer Ausdrücke


Vielen Dank

• Für das Aufspüren von Fehlern in früheren Versionen und für Verbesserungsvorschläge danke ich


Literatur• Einführung und Übersicht

– Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001). Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium engl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley.

– Hopcroft, John E. und Jeffrey D. Ullman (1988). Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a.: Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation). [Anm.: Diese Fassung enthält die Beweise]

– Klabunde, Ralf (2001). Automatentheorie und formale Sprachen. In: Kai-Uwe Carstensen, Christian Ebert, Cornelia Endriss, Susanne Jekat, Ralf Klabunde und Hagen Langer (eds.): Computerlinguistik und Sprachtechnologie. Heidelberg/Berlin: Spektrum Akademischer Verlag, 2001. S. 59-86.

– Mohri, Mehryar (1997). Finite State Transducers in Language and Speech Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. citeseer.ist.psu.edu/mohri97finitestate.html

– Lawson, Mark V. (2005). Finite automata. In: Hritsu-Varsakelis, D. und W.S.Levine (Hg).: Handbook of networked and embedded Control Systems.

– Lawson, Mark V. (2004). Finite Automata. In: D. Hristu-Varsakelis and W. S. Levine (eds.): Handbook of networked and embedded control systems

– Starke, Peter H. (1969). Abstrakte Automaten. VEB Deutscher Verlag der Wissenschaften: Berlin (ältere, aber sehr gute mathematische Darstellung)


Literatur

• Anwendungen: Sprachtechnologie– Kornai, András (Ed.) (1999). Extended Finite State Models of

Language. (Studies in Natural Language Processing). Cambridge: Cambridge University Press.

– Roche, Emmanuel und Yves Schabes (Eds.) (1997). Finite-State Language Processing. Cambridge (Mass.) und London: MIT Press.

• weitere zitierte Kursliteratur– Hoeppner, Wolfgang (2004). Unterlagen zur Vorlesung Algorithmen

und formale Sprachen http://cl.informatik.uni-duisburg.de/AlgFS/AlgFS-2002-01.pdf

– Kunze, Jürgen (2001). Computerlinguistik. Voraussetzungen, Grundlagen, Werkzeuge. Vorlesungsskript. Humboldt Universität zu Berlin. http://www2.rz.hu-berlin.de/compling/Lehrstuhl/Skripte/Computerlinguistik_1/index.html


Literatur

• Einzeluntersuchungen– Huffman, D. A. (1954). The synthesis of sequential switching circuits. J.

Franklin Inst. 257: 3-4, S. 161-190 und 275-303 – McCulloch, Warren S. und Walter Pitts (1943). A logical calculus of the

ideas immanent in nervous activity. In: Bulletin of Mathematical Biophysics 5, 115 -133.

– Kleene, Stephen Cole (1956). Representations of Events in Nerve Sets and Finite Automata, In: C. E. Shannon and J. McCarthy, Hrsg., Automata Studies, S. 3-42, Princeton, NJ, 1956. Princeton University Press.

– Mealy, George H. (1955). A method for synthesizing sequential circuits. Bell System Technical Journal 34:5, 1045-1079

– Moore, Edward F. (1956). Gedanken experiments on sequential machines. In: Automata Studies, S. 129-153, Princeton: Princeton University Press

– Turing, Alan (1936). On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Ser. 2, Vol 42, 1937.


Copyright• © 2008 Karin Haenelt.

All rights reserved. The German Urheberrecht shall be applied to these slides. In accordance with these laws these slides are a publication which may be quoted and used for non-commercial purposes, if the bibliographic data is included as described below.

• Please quote correctly. If you use the presentation or parts of it for educational and scientific purposes, please observe the laws (copyright, Urheberrecht, etc.). Please include the bibliographic data (author, title, date, page, URL) in your publication (book, paper, course slides, etc.).

• Deletion or omission of the footer (with name, data and copyright sign) is not permitted

• Bibliographic data. Karin Haenelt (2008). Endliche Automaten. Einführung in den Themenbereich. Kursfolien 12.04.2008. http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA-IntroV3.pdf

• Any further use requires the prior permission in writing from the author.• For commercial use: No commercial use is allowed without written permission

from the author. In case you are interested in commercial use please contact the author.

• Court of Jurisdiction is Darmstadt.


Versionen

• V03.01 – 16.04.2008• V03.00 – 12.04.2008• V02.03 - 14.04.2007• V02.02 - 11.04.2007• V02.01 - 15.04.2006

Documents

© Karin Haenelt, Endliche Automaten, Einführung, V 3.1 - 16.04.2008 ( 1 15.04.2006) 1 Endliche Automaten in der Sprachtechnologie Einführung in den Themenbereich