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

Auf welche Weise lassen sich formale Sprachen definieren?

akzeptierende Konzepte --> endliche Automaten

beschreibende Konzepte --> reguläre Ausdrücke

erzeugende Konzepte --> Grammatiken

Fenster schliessen

Welche Automatentypen wurden in der Vorlesung behandelt?

Transduktoren: Moore Maschine, Mealy Maschine

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

Fenster schliessen

Wodurch wird ein DEA beschrieben?

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

 

Fenster schliessen

Wie wird die Zustandübergangsfunktion \(\delta\) für einen DEA ausgedrückt?

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

Fenster schliessen

Wann gilt eine Sprache L als eine vom Automaten akzeptierte Sprache?

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

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

Fenster schliessen

Was gilt allgemein für akzeptierte Sprachen?

\(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.

Fenster schliessen

Wann ist ein DEA vollständig und wie wird er formal abgebildet?

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

Atotal = (\(\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}\)

Fenster schliessen

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

DFA\(\Sigma\) (Deterministic Finite Automata) bzw. REG\(\Sigma\) (reguläre Sprachen)