Lernkarten
Welche 4 Typen von Grammatiken gibt es?
Typ 3: Reguläre Sprachen
Typ 2: Kontextfreie Sprachen, umfasst Typ 3
Typ 1: Kontextsensitive Sprachen. umfasst Typ 2
Typ 0: Phrasenstruktursprachen, umfasst Typ 1
Was ist ein Alphabet?
endliche, abgeschlossene Menge vereinbarter, eindeutiger, unterscheidbarer, unzerlegbarer Einzelzeichen / Symbole
Was ist eine Zeichenreihe?
Reihe aus Elementen eines Alphabets
Was ist eine Sprache?
Menge von Zeichenreihen aus Eingabezeichen
- Menge der Zeichenreihen einer natürlichen Sprache
- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen
Alphabete sind abgeschlossen gegenüber Mengenoperationen. Was bedeutet das?
Wenn zwei Alphabete durch eine Operation (z.B. Differenz, Vereinigung, Schnittmenge) verbunden werden, ist das Ergebnis ebenfalls ein Alphabet.
Bsp.: Wenn A und B reguläre Sprachen sind, dann ist auch A vereinigt B eine reguläre Sprache.
Für welchen Fall kann auf folgendem Wege die Anzahl der Elemente einer Vereinigungsmenge berechnet werden?
| Alphabet A vereinigt Alphabet B | = | Alphabet A | + | Alphabet B |
Diese Rechnung kann genutzt werden, wenn die Schnittmenge der beiden Alphabete die leere Menge ist, sie also keine gemeinsamen Elemente haben. Andernfalls würden diese doppelt gezählt werden.
Wie ergibt sich die Anzahl aller möglichen Teilmengen eines Alphabetes?
| Potenzmenge des Alphabetes | = 2 |Alphabet|
Wie wird die Konkatenation • einzelner Zeichen aus dem Alphabet \(\Sigma\) formal beschrieben?
\(\Sigma \times \Sigma \to \Sigma ^*\)
Das leere Wort \(\varepsilon\) ist das Neutralelement. Jedes Wort lässt sich als Verkettung beliebiger Zeichen aus \(\Sigma\) mit dem leeren Wort in beliebiger Häufigkeit darstellen. Z.B. w = ab = \(a\varepsilon\varepsilon b \varepsilon\)
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)
