Lernkarten
Wie wird die Klasse der Sprachen notiert, die von einem \(\varepsilon-EA\) akzeptiert werden?
\(\varepsilon FA_\Sigma \)
Welche Schritte sind nötig, um einen Epsilon-EA in einen NEA zu transformieren?
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
Was sind verallgemeinerte endliche Automaten?
Verallgemeinerte Automaten akzeptieren ganze Wörter als Eingabe.
\(A_G = (\Sigma, S, \delta_*, s_0, F)\) mit \(\delta_* \subseteq S \times \Sigma^* \times S\)
Beschreiben Sie den Markierungsalgorithmus zur Automatenminimierung.
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.
Wie wird eine Mealy-Maschine formal beschrieben?
\(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)
Wodurch unterscheiden sich die Mealy- und Moore-Maschine?
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.
Wie wird eine Moore-Maschine formal beschrieben?
\(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)
Was lässt sich zur Äquivalenz von Mealy- und Moore-Maschinen sagen?
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.
