Transitionssysteme, endl. Automaten¶
Transitionssystem¶
Ein Transitionssystem hat die Form \(a = (Q, \varSigma,I , \Delta, F)\)
- Q ist die Zustandsmenge
- \(\varSigma\) ist ein endliches Alphabet
- \(I,F \subseteq Q\) ist die Menge der Anfangs- bzw. Endzustände
- \(\Delta \subset Q X \varSigma X Q\) ist die Transitionsrelation
a ist ein endliches Transitionssystem, wenn Q endlich ist.
nicht - deterministischer endlicher Automat¶
Ein endliches Transitionssystem heißt nicht - deterministischer endlicher Automat (NEA / \(I = \{ q_0 \} \text{ für } q_0 \in Q\))
Beispiel:
Notation bei NEA’s:
Pfad¶
Ein Pfad durch a ist eine Folge \(\Pi = P_0 a_1 P_1 a_2,..., a_n P_n\) mit \((P_i, a_{i+1}, P_{i+1}) \in \Delta\) für i =0,..., n-1.
Die Länge von \(\Pi\) sei N und die Beschriftung \(\beta (\Pi) \text{ sei } a_1, a_2, ..., a_n\).
\(a: p \rightarrow^w q \text{ für } w \in \varSigma^*\) besagt, dass es mindestens einen Pfad \(\Pi\) durch a von p nach q mit Beschriftung \(\beta (\Pi) = w\) gibt.
Beispiel:
Akzeptiert¶
a akzeptiert \(w \in \varSigma^* \Longleftrightarrow \exists p \in I, \exists q \in F \text{ mit } a: p \rightarrow^w q\)
Sprache¶
Für NEA sei \(L(a) = \{ w \in \varSigma^* \mid akzeptiert w \}\) die durch a erkannte Sprache.
Beispiel: a akzeptiert w = 0 1 0 0 (da der obrige Pfad: \(q_0 \in I, q_2 \in F\))
Frage: Welches Wort wird nicht akzeptiert? (z.B. w = 0)
Darstellung des NEA a durch Graphen:
- Zustände \(\equiv\) Knoten
- Transitionen \(\equiv\) Kanten
- Kantenbeschriftung durch Buchstaben aus \(\varSigma\)
Beispiel 1:
Beispiel 2:
Deterministisch¶
a ist deterministisch, wenn
In diesem Fall ist \(\Delta\) darstellbar durch eine Funktion \(\delta: Q X \varSigma \rightarrow Q\)
Beispiel
- L = \(\emptyset\) akzeptiert durch NEA:
- L = { \(\varsigma\) }
In dieser Reihenfolge:
Präfix¶
Sei \(u,w \in \varSigma^*\), so heißt u Präfix von w, wenn
Suffix¶
Sei \(u,w \in \varSigma^*\), so heißt u Suffix von w, wenn
Infix¶
Sei \(u,w \in \varSigma^*\), so heißt u Infix von w, wenn