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

Wann sind zwei Automaten äquivalent?

Wenn sie die gleiche Sprache erkennen.

Fenster schliessen

Wie wird ein Nichtdeterministischer Automat NEA formal beschrieben?

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

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

Fenster schliessen

Womit wird die Klasse der von einem NEA akzeptierten Sprachen notiert?

NFA\(\Sigma\) Nondeterministic Finite Automata

Fenster schliessen

Wozu dient das Trellis-Schema?

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.

Fenster schliessen

Wie erfolgt bei einem NEA die Berechnung von \(\delta\)* unter Berücksichtigung der Zustandsmenge S' \(\subseteq\)S?

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

Fenster schliessen

Welche Fragestellungen ergeben sich bei der Analyse von formalen Sprachen?

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)

Fenster schliessen

Was ist ein Spontanübergang?

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

Fenster schliessen

Wie ist ein \(\varepsilon\)-Automat formal definiert?

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