/
-
- 1 / 80
-
Cartes-fiches
Was meint das Prinzip der Aussonderung?
Definition eines Alphabetes mithilfe einer Eigenschaft \(\xi\)(ai)
Sinnvoll, falls Elemente von \(\Sigma\) eine Teilmenge einer Obermenge A darstellen.
Wofür steht die Potenz eines Zeichens und was ist die 0-te Potenz eines Zeichens?
wiederholte Konkatenation des Zeichens mit sich selbst
0-te Potenz entspricht dem leeren Wort
rekursive Definition:
a1= a0 • a1 = a, a2 = a0 • a1 • a1
Was ist der Kleene-Abschluss?
Die Potenzbildung eines Zeichens lässt sich auch auf Zeichenmengen übertragen. Die Vereinigung aller Potenzen über \(\Sigma\) bildet den Kleene-Abschluss \(\Sigma\)*.
\(\Sigma^* \setminus \{\varepsilon\} = \Sigma^+\)
Die Elemente von \(\Sigma\)* unterliegen einer lexikographischen Ordnung. Was bedeutet das?
Sortierung gemäß der Länge der Wörter
Wörter gleicher Länge werden stellenwertig hinsichtlich der enthaltenen Alphabetzeichen sortiert.
Wann ist x echter Präfix eines Wortes w?
x ist Präfix von w und x ist ungleich w und ungleich dem leeren Wort
Wann heißt eine Sprache L \(\subseteq\) \(\Sigma\)* präfixfrei?
Eine Sprache ist präfixfrei, wenn eine Wort x aus Präfix, Infix und Suffix besteht und der Präfix nicht Teil der Sprache ist.
Die deutsche Sprache ist z.B. nicht präfixfrei: "ausmachen" ist ein Wort mit dem Präfix "aus", was ebenfalls ein Wort der deutschen Sprache ist.
Wie wird eine Teilmenge von \(\Sigma\)* bezeichnet?
als formale Sprache L über \(\Sigma\)
Wie erfolgt die Konkatenation von Sprachen?
über die Konkatenation der Elemente (jedes Element einer Sprache mit alle Elementen der anderen Sprache)
Auf welche Weise lassen sich formale Sprachen definieren?
akzeptierende Konzepte --> endliche Automaten
beschreibende Konzepte --> reguläre Ausdrücke
erzeugende Konzepte --> Grammatiken
Welche Automatentypen wurden in der Vorlesung behandelt?
Transduktoren: Moore Maschine, Mealy Maschine
Akzeptoren: nichtdeterministischer endlicher Automat NEA, deterministischer endlicher Automat DEA, \(\varepsilon\) - endlicher Automat
Wodurch wird ein DEA beschrieben?
Quintupel: (\(\Sigma\), S, \(\delta\), s0, F) --> (Eingabealphabet, Zustandsmenge, Zustandsübergangsfunktion, Anfangszustand, Endzustandsmenge)
Wie wird die Zustandübergangsfunktion \(\delta\) für einen DEA ausgedrückt?
\(\delta\) : S x \(\Sigma\) --> S
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\)
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.
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}\)
Womit wird die Klasse der von einem DEA akzeptierten Sprachen notiert?
DFA\(\Sigma\) (Deterministic Finite Automata) bzw. REG\(\Sigma\) (reguläre Sprachen)
Wann sind zwei Automaten äquivalent?
Wenn sie die gleiche Sprache erkennen.
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)
Womit wird die Klasse der von einem NEA akzeptierten Sprachen notiert?
NFA\(\Sigma\) Nondeterministic Finite Automata
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.
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^*\)
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)
Was ist ein Spontanübergang?
\(\varepsilon\)-Übergang bei einem \(\varepsilon\)-Automaten: Übergang in einen anderen Zustand ohne Eingabe eines Zeichens möglich
Wie ist ein \(\varepsilon\)-Automat formal definiert?
\(A_\varepsilon = (\Sigma \cup \{\varepsilon\}, S, \delta_\varepsilon, S_0, F)\)
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.
Auf welche drei gängigen Automatentopologien lässt sich die Worterzeugung herunterbrechen?
- Konkatenation, Verkettung von Zeichen (Sequenz)
- Selektion, Wahl eines Suffix (Fallunterscheidung)
- Wiederholung von Strings (Schleife)
Welche Operatoren gibt es bei regulären Ausdrücken?
• = Verkettungsoperator
| = Selektionsoperator
\(\otimes\) = Wiederholungsoperator
\(\Lambda\) = Nulloperator
E = Einsoperator
[] = Klammern
Wie sind reguläre Ausdrücke definiert?
Die Menge der regulären Ausdrücke \(REXP_\Sigma\) ist genau die Menge an Wörtern w, die über dem Alphabet \(\Sigma \cup \{\Lambda, E, \otimes, |, \circ, [, ] \}\) mit folgenden Regeln gebildet werden können:
1.) Der Nulloperator ist ein regulärer Ausdruck
2.) Der Einsoperator ist ein regulärer Ausdruck
3.) Alle Elemente des Alphabets sind reguläre Ausdrücke.
4.) Die Verknüpfungen regulärer Ausdrücke mittels der Operatoren sind ebenfalls reguläre Ausdrücke.
Hinweis: Selektionsoperator | wird als Vereinigung interpretiert.
Was lässt sich über die Äquivalenz von endlichen Automaten und regulären Ausdrücken sagen?
Zu jedem endlichen Automaten A über \(\Sigma\) existiert ein regulärer Ausdruck \(a \in REXP_\Sigma\),sodass L(A) = L(a) gilt.
Was sind Nonterminale und Terminale?
Nonterminale: Variablen, die in der Menge N zusammengefasst werden.
Terminale: nicht weiter ersetzbare Sprachbestandteile, die in der Menge \(\Sigma\) zusammengefasst werden.
Was ist das Semi-Thue-System STS?
- Umformungs-/Wortersetzungs-/Stringersetzungssystem
- Regelsystem zur Transformation von Wörtern
- keine Unterscheidung zwischen Terminal- und Nonterminalsymbolen
- kein Startsymbol
Wie funktioniert der Ableitungsprozess des Semi-Thue-Systems?
Ein Wort v lässt sich aus u erzeugen, falls eine Substitution \(x \to y\) existiert, wobei x Teil des Wortes u ist und y Teil des Wortes v.
Genutzt werden Produktionen aus P, die angeben, welche Substitutionen möglich sind.
Wie ist das Thue-System definiert?
\(\forall (x,y) \in P \ \exists(y,x) \in P\), d.h. die Ableitung ist symmetrisch.
