Lernkarten

Karten 80 Karten
Lernende 4 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 29.03.2016 / 02.10.2018
Lizenzierung Keine Angabe
Weblink
Einbinden
0 Exakte Antworten 80 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

Wie wird die Klasse der Sprachen notiert, die von einem \(\varepsilon-EA\) akzeptiert werden?

\(\varepsilon FA_\Sigma \)

Fenster schliessen

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

Fenster schliessen

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\)

Fenster schliessen

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.

Fenster schliessen

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)

Fenster schliessen

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.

Fenster schliessen

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)

Fenster schliessen

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.