Endliche Automaten in der Sprachtechnologie Einführung in den Themenbereich

Endliche Automaten in der Sprachtechnologie

• Einführung in den Themenbereich

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

Endliche Automaten: Beispiele

Endlicher Automat: Beispiel

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

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 mehrere mögliche Paare [o,q] zugeordnet sein

• stochastisch

• jedem Paar [p,i] ist für ein Paar [o,q] ein Wahrscheinlichkeitsmaß zugeordnet

Typen endlicher Automaten: Beispiele

Typen endlicher Automaten: Beispiele

Charakteristische Eigenschaften endlicher Automaten

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

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

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

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)

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?

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

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

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)

• Beispiel

Mengentheoretische Definition endlicher Automaten – Beispiel 1a

• 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

Mengentheoretische Definition endlicher Automaten – Beispiel 1b

Mengentheoretische Definition endlicher Automaten – Beispiel 2

• determinierter abstrakter Automat

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

• X, Y, Z beliebige nichtleere Mengen sind, und
• γ eine auf Z  X definierte Funktion ist, deren Werte in Y  Z liegen. ■ (Starke 1969: 22)

• determinierter Mealy-Automat

• Ein determinierter Automat A = (X, Y, Z, γ) heißt determinierter Mealy-Automat, falls für alle x X, zZ, γ(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 Automat

• A 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 Automat

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

• X, Y, Z nichtleere Mengen sind, und
• h eine eindeutige Abbildung von Z  X in P*(Z  X) ist. ■ (Starke 1969: 121)

• stochastischer Automat

• C = (X, Y, Z, H) heißt stochastischer Automat, wenn

• X, Y, Z beliebige nichtleere Mengen sind, und
• 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

Reguläre Sprachen in der Sprachentheorie

Formale Sprachen

• Formale 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. ■

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.

Formale Sprachen und endliche Automaten

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 Sprachen und Endliche Automaten

Spezifikationen regulärer Sprachen und Endliche Automaten

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.

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

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

Algorithmen und Systemarchitekturen

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

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

Ähnliche Modelle: HMM

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

• Historisches
• 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 (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.

• Sprachtheorie theoretische Frage:

• Sind natürliche Sprachen reguläre Sprachen?

• Sprachtechnologie praktische Frage:

• Welche Eignung haben endliche Automaten für die Sprachverarbeitung?

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.

„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

Anwendungsgebiete

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

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

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