Endliche Automaten

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

ein abstrakter Automat ist ein mathematisches Modell für einfache Maschinen/Programme, die bestimmte Probleme lösen

• ein abstrakter Automat ist ein mathematisches Modell für einfache Maschinen/Programme, die bestimmte Probleme lösen

• beschreibt nicht einen bestimmten Automaten, sondern gemeinsame Grundprinzipien einer Klasse von Automaten

• Grundlegende Komponenten

• Zustände
• Eingabesymbole
• Zustandsübergänge: reagiert auf Eingaben durch Übergang in einen anderen Zustand

Seien X, Y, Z beliebige nichtleere Mengen, dann ist

• Seien X, Y, Z beliebige nichtleere Mengen, dann ist

• A = (X, Y, Z, γ)
• ein determinierter abstrakter Automat, wenn
• γ eine auf Z  X definierte Funktion ist, deren Werte in Y  Z liegen.
• B = (X, Y, Z, h)
• ein nicht-deterministischer Automat, wenn
• h eine eindeutige Abbildung von Z  X in *(Z  Y) ist.
• C = (X, Y, Z, H)
• ein stochastischer Automat, wenn
• H eine auf Z  X definierte Funktion ist, die diskrete Wahrscheinlichkeitsmaße über Y  Z als Werte H(z,x) hat

A = (X, Y, Z, γ)

• A = (X, Y, Z, γ)

• ein determinierter abstrakter Automat, wenn
• γ eine auf Z  X definierte Funktion ist, deren Werte in Y  Z liegen. (Starke 1969:22)

• Interpretation

• X Menge der Eingabesymbole

• Y Menge der Ausgabesymbole

• Z Menge der Zustände

endlicher determinierter Automat (Starke 1969: 25)

• endlicher determinierter Automat (Starke 1969: 25)

• Ein determinierter Automat A = [X,Y,Z,δ,λ] 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 ■

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

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

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

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

Akzeptoren

• 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

klassifiziert Algorithmen nach der Art des Speichers, der für die Implementierung zum Merken von Zwischergebnissen gebraucht wird

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

Mengen der Zustände, der Eingabesignale, der Ausgabesignale sind endlich

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

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

Reguläre Ausdrücke sind

• Reguläre Ausdrücke sind

• eine Notation zur Beschreibung der Sprachen, die mit endlichen Automaten erkannt werden können
• wie arithmetische Ausdrücke aus Konstanten und Operatoren aufgebaut

• zumeist bekannt aus ihrer Verwendung in

• Suchfunktionen in Betriebssystemen (grep)
• Texteditoren
• Textverarbeitungsprogrammen und Suchmaschinen
• Textmusterspezifikation in Programmiersprachen

Stephen Kleene (Mathematiker)

• Stephen Kleene (Mathematiker)

• untersuchte (1956), welche Mengen von Zeichenketten von endlichen Automaten akzeptiert werden können
• entwickelte für diese Mengen eine syntaktische Charakterisierung: Komposition der Zeichenketten
• aus Elementen und Teilmengen
• nach bestimmten Regeln
• führte für diese Mengen den Begriff reguläre Mengen ein

Symbol a

• Symbol a

• ein Symbol ist ein unzerlegbares Grundzeichen ■
• unzerlegbar bezüglich der Art der Betrachtung, um die es gerade geht
• Beispiele:
• a, b, c
• dete, adje, nomn

• Alphabet Σ

• ein Alphabet ist eine endliche nichtleere Menge von Symbolen ■

Wort w

• Wort w

• ein Wort ist eine endliche Folge von Symbolen aus einem Alphabet.
• Wir schließen das leere Wort (Wort, das kein Zeichen enthält) in die Definition ein und bezeichnen es mit ε. ■

Sprache L

• Sprache L

• Eine Sprache ist die Menge aller endlichen Folgen w von Symbolen aus Σ. ■
• es gilt
•  die leere Sprache ist eine Sprache
• {ε} die Menge, die nur ein leeres Wort enthält, ist eine Sprache
• Σ* die Universalsprache, die aus der Menge aller endlichen Folge von Symbolen aus einem Alphabet besteht, ist eine Sprache

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

Kleene-Theorem: Eine Sprache ist genau dann regulär, wenn sie durch einen endlichen Automaten erkannt werden kann

• Kleene-Theorem: Eine Sprache ist genau dann regulär, wenn sie durch einen endlichen Automaten erkannt werden kann

• Kleenes Formulierung (1956):

• Synthesetheorem (Kleene, 1956, Theorem 3): Jede reguläre Sprache kann in einem endlichen Automaten dargestellt werden
• Analysetheorem (Kleene, 1956, Theorem 5): Jede in einem endlichen Automaten darstellbare Sprache ist regulär

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

Klammern sparen beim Schreiben:

• Klammern sparen beim Schreiben:

• Wie für die algebraischen Operatoren ’+’ und ’∙’ gibt es auch für die Operatoren regulärer Ausdrücke eine festgelegte Auswertungsreihenfolge. Für den Ausdruck 4+5∙2 gilt, dass zuerst die Multiplikation und dann die Addition durchzuführen ist.

• Für die Operatoren für reguläre Ausdrücke gilt folgende Reihenfolge:

• Kleenesche Hülle (Symbol: *)
• Multiplikation bzw. Verkettung (Symbol ’∙’ oder ohne explizites Symbol).
• Addition bzw. Vereinigung (Symbol ’+’ oder ’|’).

einige Programmiersprachen (z.B. Perl) erlauben auch Muster, die über reguläre Ausdrücke hinausgehen

• einige Programmiersprachen (z.B. Perl) erlauben auch Muster, die über reguläre Ausdrücke hinausgehen

• Beispiel in Perl: (.*)\1

• beliebige Zeichenfolge, verkettet mit der Zeichenfolge, die durch die erste Klammer beschrieben wird
• Zusatzspeicher zum Merken von Klammerinhalten erforderlich (endliche Automaten haben aber kein Gedächtnis)

• Muster mit unbegrenzter Zahl von Rückverweisen beschreiben nicht einmal kontextfreie Sprachen, Erkennung NP-vollständig

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

Effizienz

• Effizienz

• in der Regel besonders effizientes Laufzeitverhalten: Traversion deterministischer endlicher Automaten: O(n)
• platzsparende Repräsentation

Grundlagen

• 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

direkte Anwendung

• 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

• 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

Endliche Automaten

• Endliche Automaten

• Abstrakte Automaten
• Abstrakte endliche Automaten
• Automatentheorie: endl. Automaten haben kein Gedächtnis

• Reguläre Ausdrücke

• Definition
• Äquivalenz: Reguläre Ausdrücke und endliche Automaten
• Operatoren für reguläre Ausdrücke in Programmiersprachen

• Attraktivität endlicher Automaten für die Sprachverarbeitung

• Adäquatheit endlicher Automaten für die Sprachverarbeitung

man muss unterscheiden zwischen

• man muss unterscheiden zwischen

• der Komplexität der Sprache (= Menge von Zeichenketten)
• der Komplexität der Maschine zur Erkennung bestimmter Konstruktionen

• eine reguläre Sprache kann auch eine kontextfreie oder kontextsensitive Teilmenge enthalten; Beispiel:

• L = {apbq : p, q ∈ ℕ } ist eine reguläre Sprache
• Ein Automat, der L erkennt, erkennt auch
• L1 = {anbn : n ∈ ℕ }
• L2 = {wwR: w ∈ Σ*} wR Spiegelbild der Sequenz w

Das Vorkommen der Teilmengen L1 und L2 sagt also nichts über die Komplexität von L

• Das Vorkommen der Teilmengen L1 und L2 sagt also nichts über die Komplexität von L

• aber: die Teilmengen L1 und L2 sind möglicherweise linguistisch motivierte Teilmengen, die man besonders auszeichnen möchte

Chomsky (1957): English is not a finite state language. (Korrekte Terminologie: regular language)

• Chomsky (1957): English is not a finite state language. (Korrekte Terminologie: regular language)

• Large classes of context-free languages such as some of those used in Chomsky’s argument have been proved to be representable by weighted finite automata (Cortes & Mohri 2000).

• Hobbs & al. (1997) Finite-state models are clearly not adequate for full natural language processing... . Every computational linguistics graduate student knows, from the first textbook that introduces the Chomsky hierarchy, that English has constructs, such as center embedding, that cannot be described by any finite-state grammar.

• (Arnold 2000). Natural Languages are not Finite State (‘regular’). There is no FSA (hence type 3 grammar) that can generate anbn. Natural Languages are infinite, and have constructions like anbn, i.e. ‘nested dependencies’...

Morphologie

• Morphologie

• Mittel der Wahl: Typ-3-Grammatiken, reguläre Sprachen
• einige Fälle können durch geringe spezielle Erweiterungen endlicher Automaten effizienter behandelt werden

• Syntax

• Für die endliche "Kernsprache" der tatsächlich vorkommenden akzeptablen Sätze des Deutschen (und anderer Sprachen) kann man annehmen, dass eine nicht-triviale Beschreibung als Typ-3-Sprache möglich ist
• Der menschliche Analysator bewältigt nur bestimmte Schachtelungstiefen (für begrenzte Schachtelungstiefen reicht Typ-3)

weitgehend regulär

• weitgehend regulär
• Ausnahmen im Deutschen:
• ge-mach-t (aber nicht: ge-mach-st; Gedächtnis für „ge“ erforderlich)
• um-zu-bau-en
• Kompositionsmorphologie komplexer
• einfache Ergänzungen endlicher Automaten zur zusätzlichen Handhabung von Einschränkungen

%s Klasse01 Klasse02 %% "lach" {printf("\n%s", yytext); BEGIN(Klasse01); } "mach" {printf("\n%s", yytext); BEGIN(Klasse01); } "sitz" {printf("\n%s", yytext); BEGIN(Klasse02); } "e" {printf("%s 1. Pers. Sg.", yytext); BEGIN(INITIAL); } "st" {printf("%s 2. Pers. Sg.", yytext); BEGIN(INITIAL);} "t" {printf("%s 3. Pers. Sg. | 2. Pers. Pl.", yytext); BEGIN(INITIAL); } "en" {printf("%s 1. Pers. Pl. | 3. Pers. Pl.", yytext); BEGIN(INITIAL); } "e" {printf("%s 1. Pers. Sg.", yytext); BEGIN(INITIAL); } "t" {printf("%s 2. Pers. Sg. | 3. Pers. Sg. | 2. Pers. Pl", yytext); BEGIN(INITIAL); } "en" {printf("%s 1. Pers. Pl. | 3. Pers. Pl.", yytext); BEGIN(INITIAL); } \n ; \t ; . ;

• %s Klasse01 Klasse02 %% "lach" {printf("\n%s", yytext); BEGIN(Klasse01); } "mach" {printf("\n%s", yytext); BEGIN(Klasse01); } "sitz" {printf("\n%s", yytext); BEGIN(Klasse02); } "e" {printf("%s 1. Pers. Sg.", yytext); BEGIN(INITIAL); } "st" {printf("%s 2. Pers. Sg.", yytext); BEGIN(INITIAL);} "t" {printf("%s 3. Pers. Sg. | 2. Pers. Pl.", yytext); BEGIN(INITIAL); } "en" {printf("%s 1. Pers. Pl. | 3. Pers. Pl.", yytext); BEGIN(INITIAL); } "e" {printf("%s 1. Pers. Sg.", yytext); BEGIN(INITIAL); } "t" {printf("%s 2. Pers. Sg. | 3. Pers. Sg. | 2. Pers. Pl", yytext); BEGIN(INITIAL); } "en" {printf("%s 1. Pers. Pl. | 3. Pers. Pl.", yytext); BEGIN(INITIAL); } \n ; \t ; . ;

Erweiterung endlicher Automaten für long distance dependencies:

• Erweiterung endlicher Automaten für long distance dependencies:

• einfaches Gedächtnis: flags
• prozedurale Interpretation mit Bitvektor-Operationen

hier sind zu unterscheiden

• hier sind zu unterscheiden

• syntaktische Strukturen
• die regulär darstellbar sind
• die nicht regulär darstellbar sind
• syntaktische Strukturen und semantische Strukturen

Syntax

• Syntax

• erkennbar auf der Basis rein formaler Eigenschaften (Kasus, Folge von Wortarten, ..)
• teilweise: reguläre Konstrukte
• teilweise: nicht-reguläre Konstrukte (sofern unendlich)

• Interpretation

• alle Entscheidungen, die darüberhinaus auf der Basis der Erfahrung der Sprachverwendung beruhen

• Satzstrukturen

• sind Mischungen aus Syntax und Interpretation

viele beobachteten Konstrukte sind nur dann nicht-regulär, wenn die Folge der Wörter oder Sätze als unbegrenzt angenommen wird

• viele beobachteten Konstrukte sind nur dann nicht-regulär, wenn die Folge der Wörter oder Sätze als unbegrenzt angenommen wird

• keines der genannten Argumente ist interessant, wenn man die Länge der Sätze (oder Wörter) als begrenzt durch eine große Zahl N annimmt

• alle Beweise einer höheren Komplexität als regulärer Sprachen gelten nicht, wenn die Phänomene nicht als unbegrenzt angenommen werden können.

• so auch Chomsky 1957

• der endliche Automat zur Beschreibung der Sprache kann allerdings sehr groß werden

Bei Fortsetzung der „Kernsprache“ ins Unendliche tritt ein „Komplexitätsschub“ bei Zentraleinbettungen auf

• Bei Fortsetzung der „Kernsprache“ ins Unendliche tritt ein „Komplexitätsschub“ bei Zentraleinbettungen auf

• nicht mit Typ-3 Grammatik darstellbare Bedingungen:
• Anzahl der Nomina und Verben muss übereinstimmen
• gewisse Merkmale, die eine Kongruenz sichern, müssen übereinstimmen

• Unendliche Einbettungen kommen in der Praxis nicht vor

obligatorische paarweise Korrespondenzen

• obligatorische paarweise Korrespondenzen

• either ... or, if ... then
• können ineinander geschachtelt werden
• nicht regulär kontrollierbar: Anzahl der „öffnenden“ und „schließenden“ Klammern und ihre Korrespondenz

• Unendliche Einbettungen kommen in der Praxis nicht vor

überkreuzende Abhängigkeit (cross-serial dependency)

• überkreuzende Abhängigkeit (cross-serial dependency)

Überfrachtung der Syntax mit semantischer Interpretation führt zu kombinatorischer Explosion von Lesarten

• Überfrachtung der Syntax mit semantischer Interpretation führt zu kombinatorischer Explosion von Lesarten

• Erzeugung kostet unnötige Rechenzeit

• bringt keinen verwertbaren Informationsgewinn (455 Lesarten!)

exakte und vollständige Charakterisierung aller wohlgeformten Äußerungen nicht möglich

• exakte und vollständige Charakterisierung aller wohlgeformten Äußerungen nicht möglich

• Regeln nicht völlig unbegründet

• irgendwie müssen wir die Dinge lockerer handhaben, um der Kreativität der Sprache Rechnung zu tragen

finite-state approximation of sentence structures (Abney 1995)

• finite-state approximation of sentence structures (Abney 1995)

• finite-state cascades: sequences of levels of regular expressions
• recognition approximation: tail-recursion replaced by iteration
• interpretation approximation: embedding replaced by fixed levels

• finite-state approximation of phrase structure grammars (Pereira/Wright 1997)

• flattening of shift-reduce-recogniser
• no interpretation structure (acceptor only)
• used in speech recognition where syntactic parsing serves to rank hypotheses for acoustic sequences

• finite-state approximation (Sproat 2002)

• bounding of centre embedding
• reduction of recognition capacity
• flattening of interpretation structure

patterns: reliable indicators of bits of syntactic structure

• patterns: reliable indicators of bits of syntactic structure

• parsing

• easy-first parsing (easy calls first)
• proceeds by growing islands of certainty into larger and larger phrases
• no systematic parse tree from bottom to top
• recognition of recognizable structures
• containment of ambiguity
• prepositional phrases and the like are left unattached
• noun-noun modifications not resolved
• no unification of features: additional bit vector operations possible

Sproat, 2002:

• Sproat, 2002:

• observation: unbounded centre embedding

• does not occur in language use
• seems to be too complex for human mental capacities

• finite state modelling of bounded centre embedding

Dokumentindex als endlicher Automat

• Dokumentindex als endlicher Automat

• kompakt, schnell traversierbar

• Faktenextraktion mit endlichen Automaten

• schnelle Durchsuchung sehr großer Textmengen
• linguistisch adäquat für
• schablonenartige Information
• teilstrukturierte Information (HTML)
• abstrakte Sprache für die Anwendung: spezifizierbar mit regulären Ausdrücken

• Dokumentanalyse/Sprachverarbeitung

• Traversion eines deterministischen endlichen Automaten: O(n)
• linguistisch adäquat für Morphologie und Syntax

Abney, Steven (1995). Partial Parsing via Finite-State Cascades. In: Journal of Natural Language Engineering, 2(4): 337-344. http://www.vinartus.net/spa/97a.pdf

• Abney, Steven (1995). Partial Parsing via Finite-State Cascades. In: Journal of Natural Language Engineering, 2(4): 337-344. http://www.vinartus.net/spa/97a.pdf

• Beesley Kenneth R. und Lauri Karttunen (2003). Finite-State Morphology. Distributed for the Center for the Study of Language and Information. (CSLI- Studies in Computational Linguistics)

• Bod, Rens (1998). Beyond Grammar. An Experienced-Based Theory of Language. CSLI Lecture Notes, 88, Standford, California: Center for the Study of Information and Language

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

• Hopcroft, John E., Rajeev Motwani und Jeffrey D. Ullman (2002). Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium engl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley. www-db.stanford.edu/~ullman/ialc.html

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

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

• Kunze, Jürgen (2001). Computerlinguistik. Voraussetzungen, Grundlagen, Werkzeuge. Vorlesungsskript. Humboldt-Universität zu Berlin.

• Jurafsky, Daniel und James H. Martin (2000): Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition. New Jersey: Prentice Hall.

• Manning, Christopher D.; Schütze, Hinrich (1999). Foundations of Statistical Natural Language Processing. Cambridge, Mass., London: The MIT Press. http://www.sultry.arts.usyd.edu.au/fsnlp

Mehryar Mohri und Richard Sproat (2006). On a Common Fallacy in Computational Linguistics. In: Mickael Suominen, Antti Arppe, Anu Airola, Orvokki Heinämäki, Matti Miestamo, Urho Määttä, Jussi Niemi, Kari K. Pitkänen and Kaius Sinnemäki (Hrsg.). A Man of Measure: Festschrift in Honour of Fred Karlsson on this 60th Birthday. pages 432-439. SKY Journal of Linguistics, Volume 19, 2006.

• Mehryar Mohri und Richard Sproat (2006). On a Common Fallacy in Computational Linguistics. In: Mickael Suominen, Antti Arppe, Anu Airola, Orvokki Heinämäki, Matti Miestamo, Urho Määttä, Jussi Niemi, Kari K. Pitkänen and Kaius Sinnemäki (Hrsg.). A Man of Measure: Festschrift in Honour of Fred Karlsson on this 60th Birthday. pages 432-439. SKY Journal of Linguistics, Volume 19, 2006.

• Pereira, Fernando C. N. and Rebecca N. Wright (1997). Finite-State Approximation of Phrase-Structure Grammars. In: Roche/Schabes 1997.

• Shieber, Stuart. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy 8: 333–343.

• Sproat, Richard (2002). The Linguistic Significance of Finite-State Techniques. February 18, 2002. http://www.research.att.com/~rws

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

1.1 (1.12.2013)

• 1.1 (1.12.2013)

• 1.0 (6.12.2012)