Abstrakte Maschinen & deterministische endliche Automaten Flashcards
1
Q
Wie lässt sich das Wortproblem, Spezifikationsproblem und die Äquivalenz lösen?
A
2 Maschinen basierte Ansätze
1 Sprach basierter Ansatz
2
Q
Was ist der Sprach basierte Ansatz?
A
Eine Menge von Zeichen (Reguläre Ausdrücke) die ein Wort definieren, um damit eine Sprache zu spezifizieren.
3
Q
Definition abstrakte Maschine
A
- Ist ein Modell zur Berechnung des Wortproblems einer formalen Sprache
- Ist eine mathematische Funktion, die ein Eingabewort auf ein Ausgabebit abbildet.
4
Q
Wie viele Komponenten hat eine abstrakte Maschine?
A
3
- Ein-/Ausschalter
- Ein-/Ausgabegerät
- mindestens 2 Statuslampen (Ja nein)
5
Q
Woraus besteht ein deterministischer endlicher Automat (DFA)?
A
- begrenzte Anzahl an Zuständen
- Akzeptanzzustand:ja
- Ablehnungszustand: nein
- Menge an Transitionen
- Leseeinheit
6
Q
Wann akzeptiert die Maschine ein Wort?
A
Sobald die Ja Lampe leuchtet.
7
Q
Ein DFA ist spezifiziert durch Q, E, d, q0, F
A
Q: Zustandsmeneg, endlich E: Alphabet, endlich d: Übergnagsfunktion q0: Nullzustand, element Q F: Finalzustände
8
Q
Eigenschaften DFA?
A
Ein DFA zeichnet aus das für jeden Zustand und jedes Zeichen genau ein Folgezustand bestimmt ist.
