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)