Automatentheorie und Formale Sprachen - Mitschrift - Katoen/26.04.2007

Wichtige Themen:

Definition: $ε$ -erweiterte NEA: Automaten mit Übergängen, auf denen kein Buchstabe aus dem Alphabet steht. Diese Übergänge können vom Automaten spontan genommen werden.
Satz: $ε$ -erweiterte NEA sind gleich mächtig wie NEA (und damit wie DEA und wie reguläre Sprachen).
Konstruktionen durch Hinzufügen von ε-Übergängen zu NEA:
- Konkatenation von zwei (evtl. $ε$ -erweiterten) NEA mit disjunkter Zustandsmenge
- Kleene-Abschluss eines (evtl. $ε$ -erweiterten) NEA
Theorem: reguläre Sprachen sind abgeschlossen unter Schnitt, Vereinigung, Komplement, Konkatenation und Kleene-Abschluss.

Ein Versuch zwei Mengen mit GraphViz hinzubekommen. Naja.

An diesem Artikel muss noch gearbeitet werden.