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.