4.5
Vertiefung
- Ein sehr interaktive Einführung in die Automatentheorie findet sich unter
http://www.jflap.org.
- Jede Einführung in die theoretische Informatik behandelt endliche Automaten und ihre
Sprachen. Meine Formalisierungen folgen [CARSTENSEN et al. 2004, Kapitel 2.2], welche
einfache linguistisch motivierte Beispiele beinhaltet.
- Die Formalisierung der Sprache der 𝜖-NEA in [KAPLAN und KAY 1994] und [ROCHE
und SCHABES 1996] (die Version mit δ∗) ist m. E. induktiv nicht besonders gut gelöst,
deshalb verwende ich dort den Klassiker [HOPCROFT et al. 2002]. Dieses Buch bietet u.a.
eine sorgfältig begründende Einführung in die Theorie und die wichtigen Algorithmen im
Umfeld von EA.
- Dass die Entstehung des Konzepts der endlichen Automaten erstaunlicherweise viel mit
dem Modell der Nervenzellen von McCulloch und Pitts zu tun hat, kann in [LAKOVIC
und MAI 1999] nachgelesen werden.
- Hinweise zur Definition der Operatoren: Im Aufsatz [COHEN-SYGAL und WINTNER
2005] werden xfst-Konstrukte in den Formalismus der freiverfügbaren Prolog-basierten
FSA-Tools von G. van Noord übersetzt.