Automatentheorie - 4. Semester

| Potenzmenge des Alphabetes | = 2 ^|Alphabet|

\(\Sigma \times \Sigma \to \Sigma ^*\)

Das leere Wort ^{\(\varepsilon\)} ist das Neutralelement. Jedes Wort lässt sich als Verkettung beliebiger Zeichen aus \(\Sigma\) mit dem leeren Wort in beliebiger Häufigkeit darstellen. Z.B. w = ab = \(a\varepsilon\varepsilon b \varepsilon\)

Definition eines Alphabetes mithilfe einer Eigenschaft ^\(\xi\)(a_i)

Sinnvoll, falls Elemente von \(\Sigma\) eine Teilmenge einer Obermenge A darstellen.

wiederholte Konkatenation des Zeichens mit sich selbst

0-te Potenz entspricht dem leeren Wort

rekursive Definition:

a¹= a⁰ • a¹ = a, a² = a⁰ • a¹ • a¹

Die Potenzbildung eines Zeichens lässt sich auch auf Zeichenmengen übertragen. Die Vereinigung aller Potenzen über \(\Sigma\) bildet den Kleene-Abschluss \(\Sigma\)*.
\(\Sigma^* \setminus \{\varepsilon\} = \Sigma^+\)

Sortierung gemäß der Länge der Wörter

Wörter gleicher Länge werden stellenwertig hinsichtlich der enthaltenen Alphabetzeichen sortiert.

x ist Präfix von w und x ist ungleich w und ungleich dem leeren Wort

Eine Sprache ist präfixfrei, wenn eine Wort x aus Präfix, Infix und Suffix besteht und der Präfix nicht Teil der Sprache ist.

Die deutsche Sprache ist z.B. nicht präfixfrei: "ausmachen" ist ein Wort mit dem Präfix "aus", was ebenfalls ein Wort der deutschen Sprache ist.

als formale Sprache L über \(\Sigma\)

über die Konkatenation der Elemente (jedes Element einer Sprache mit alle Elementen der anderen Sprache)

akzeptierende Konzepte --> endliche Automaten

beschreibende Konzepte --> reguläre Ausdrücke

erzeugende Konzepte --> Grammatiken

Transduktoren: Moore Maschine, Mealy Maschine

Akzeptoren: nichtdeterministischer endlicher Automat NEA, deterministischer endlicher Automat DEA, ^{\(\varepsilon\)} - endlicher Automat

Quintupel: (\(\Sigma\), S, \(\delta\), s₀, F) --> (Eingabealphabet, Zustandsmenge, Zustandsübergangsfunktion, Anfangszustand, Endzustandsmenge)

\(\delta\) : S x \(\Sigma\) --> S

Wenn die Elemente ^{\(w_i \in L \subseteq \Sigma^*\)} vom Startzustand s₀ zu einem Endzustand führen.

\(\delta^* (s_0, w) = s_i \in F\)

\(L(A) = \{w\in \Sigma^* | (s_0, w) \vdash ^* (s_i\in F, \varepsilon)\}\)

In Worten: Das Wort w ist Element der transitiv reflexiven Hülle und es gilt: Vom Startzustand kommt man über die komplette Abarbeitung des Wortes in einen Endzustand.

Der Automat ist vollständig, wenn alle möglichen Eingabezeichen von einem Zustand in einen Zustand führen (es kann auch der gleiche sein). Für alle nicht definierten Übergänge wird ein zusätzlicher Zustand eingebunden (sozusagen das Abstellgleis).

A^total = (\(\Sigma, S \cup \{s_{tot}, \delta_{total}, s_0, F\}, s_{tot} \notin S\))

mit \(\delta_{total} = \delta(s,a) gdw (s,a) \in Def(\delta), sonst s_{tot}\)

DFA_\(\Sigma\) (Deterministic Finite Automata) bzw. REG_\(\Sigma\) (reguläre Sprachen)

Wenn sie die gleiche Sprache erkennen.

\(A_{NEA} = (\Sigma, S, \delta, S_0, F)\)

Der Unterschied zu einem DEA ist, dass S₀ nun eine Menge von Startzuständen ist. Der Wertebereich der Zustandsübergangsfunktion wird auf Mengen erweitert. \(\delta: S \times \Sigma \to P(S)\) (Potenzmengenaxiom)

NFA_\(\Sigma\) Nondeterministic Finite Automata

Visualisierung einer Eingabesequenz w in einen NEA: Vertikal werden die möglichen Zustände aufgelistet, horizontal die Eingabesequenz. Es werden alle möglichen "Wege" eingetragen, sodass man nachvollziehen kann, welcher Weg in einer Sackgasse mündet und welcher zu einem Endzustand führt.

\(\delta\)* (S', aw) = \(\delta\)*\((\cup \delta(s,a), w), a \in \Sigma, w \in \Sigma^*\)

1.) Akzeptieren beide Varianten die gleiche Klasse von Sprachen L?

2.) Ist ein Automatentyp mächtiger als der andere? D.h., ist die Klasse der von dem einen Automatentyp akzeptierten Sprachen eine Unterklasse der von dem anderen Automaten akzeptierten Sprachen?

3.) Sind die Klassen verschieden, enthalten aber Sprachen, die beide akzeptieren? (Schnittmenge nicht leer, aber Klassen sind ungleich)

4.) Sind die Klassen verschieden und disjunkt? (Schnittmenge leer)

^{\(\varepsilon\)}-Übergang bei einem ^{\(\varepsilon\)}-Automaten: Übergang in einen anderen Zustand ohne Eingabe eines Zeichens möglich

\(A_\varepsilon = (\Sigma \cup \{\varepsilon\}, S, \delta_\varepsilon, S_0, F)\)

\(\varepsilon FA_\Sigma \)

1.) Einfügen genau eines Anfangszustandes und eines Endzustandes, sodass es keine Menge von Anfangszuständen mehr gibt. (zusätzliche Übergänge von/zu diesen beiden neuen Zuständes)

2.) Elimination von Epsilon-Zykel (alle aufeinanderfolgenden Epsilon-Übergänge, die am Ende der Sequenz auf sich selbst führen, werden in einem einzelnen Epsilon-Übergang zusammengefasst)

3.) Entfernen von Epsilon-Übergängen, die auf sich selbst führen.

4.) Austausch der noch enthaltenen Epsilon-Übergänge durch echte Übergänge.

5.) Bestimmung der Endzustandsmenge

Verallgemeinerte Automaten akzeptieren ganze Wörter als Eingabe.

\(A_G = (\Sigma, S, \delta_*, s_0, F)\) mit \(\delta_* \subseteq S \times \Sigma^* \times S\)

1.) Tabelle für alle Zustandspaare bilden

2.) Markierung aller Paare {s,t} mit s ^\(\notin\) F und t ^\(\in\) F (ein Endzustand und ein Nicht-Endzustand)

3.) Testen von jedem noch nicht markierten Paar {s,t} und jedem a \(\in \Sigma\), ob das Paar \(\{\delta(s,a), \delta(t,a)\}\) schon markiert ist. Falls ja, dann Paar {s,t} markieren.

4.) Wiederholung von 3.), bis sich die Markierungen nicht mehr ändern

5.) Zusammenfassen von Zustand s mit allen Zuständen t zu einem Zustand, für die {s,t} nicht markiert ist.

\(M = (\Sigma, \Delta, S, \delta, \lambda, s_0)\), es gibt also keine Endzustände

\(\Delta\) ist das Ausgabealphabet und

\(\lambda\) ist die Ausgabefunktion \(S \times \Sigma \to \Delta\)

Konfiguration k = (Zustand s, restliches Eingabewort v, Ausgabewert w)

Mealy: Ausgabe an den Übergängen, damit vom Eingabezeichen abhängig

Moore: Ausgabe in den Zuständen, damit unabhängig vom Eingabezeichen

Sie haben also unterschiedliche Ausgabefunktionen.

\(M = (\Sigma, \Delta, S, \delta, \lambda, s_0)\), es gibt also keine Endzustände

\(\Delta\) ist das Ausgabealphabet und

\(\lambda\) ist die Ausgabefunktion \(S \to \Delta\)

Konfiguration k = (Zustand s, restliches Eingabewort v, Ausgabewert w)

Die Klasse der mit Mealy-Maschinen berechenbaren Funktionen ist identisch mit der Klasse der mit Moore-Maschinen berechenbaren Funktionen. Zu jeder Mealy-Maschine lässt sich also eine äquivalente Moore-Maschine konstruieren und umgekehrt.