Recent Posts

Semantische Sicherheit In der Vorlesung vom 25.04.2013 hat Prof. Hofheinz gesagt, dass man semantische Sicherheit praktisch nicht beweisen kann, da man zuerst $\mathcal{P} \neq \mathcal{NP}$ beweisen müsste. Warum das so ist, versuche ich nun zu erläutern. Einwegfunktionen und $\mathcal{P} \neq \mathcal{NP}$ Sei $f:X \rightarrow Y … Read More »

Definitionen aus GBI Formale Sprachen A heißt Alphabet $:\Leftrightarrow$ A ist eine endliche, nicht leere Menge aus Zeichen. w heißt Wort aus $A^ : \Leftrightarrow$ w ist eine endliche Aneinanderreihung von Zeichen aus A L heißt formale Sprache $: \Leftrightarrow L \subseteq A^$ G heißt formale Grammatik $: \Leftrightarrow G = (N, T, S, P)$ wobei: N … Read More »

Kellerautomat Ein Kellerautomat ist ein endlicher Automat mit einem Stack („Kellerspeicher"). Er wird mit PDA (pushdown automaton) bzw. NPDA (nondeterministic pushdown automaton) abgekürzt. Laut Wikipedia verwendet die Gleitkommaeinheit einen PDA. Dazu habe ich allerdings keine Quelle gefunden, das ist also mit Vorsicht zu genießen. Ein weiterer Einsatzzweck ist die Syntaxanalyse einer … Read More »

Komplexitätsklassen in der Informatik: Ein Überblick Komplexitätsklassen werden in der Theoretischen Informatik verwendet um den Ressourcenbedarf von Algorithmen bzw. Problemen einzuordnen. Meist betrachtet man die Laufzeit- und die Speicherplatzkomplexität, aber es wäre prinzipiell auf Vorstellbar, dass man andere Kriterien nutzt. Ich werde in diesem Artikel mal kurz die in der Vorlesung behandelten Klassen vorstellen. Da es … Read More »

Konstruktion der Chomsky-Normalform Dieser Artikel könnte inhaltliche Fehler beinhalten. Bitte lest euch die Kommentare durch. Die Chomsky-Normalform ist eine bestimmte Art, eine kontextfreie Grammatik zu formulieren. Dabei haben nur die Produktionsregeln eine festgelegte Form, alles andere ist wie immer. Die Chomsky-Normalform kommt bei dem CYK-Algorithmus, der das Wortproblem für kontextfreie Grammatiken löst, zum … Read More »

Minimierung eines Automaten mittels Äquivalenzklassenkonstruktion Wenn ein Endlicher Automat gegeben ist, kann durch die Konstruktion von Äquivalenzklassen sehr einfach ein Automat mit gleichem Akzeptanzverhalten und minimaler Anzahl an Zuständen gefunden werden. Dafür benötigt man im Wesentlichen sogar nur drei Schritte. Der Algorithmus Überflüssige Zustände streichen: Manche Zustände sind nicht erreichbar. Diese können offensichtlich gestrichen werden … Read More »

Sprachen, Automaten und Grammatiken: Ein Überblick Die folgende Tabelle gibt einen Überblick über formale Sprachen, die Automaten die sie akzeptieren und die Grammatiken, die sie erzeugen. Dabei haben die Grammatiken die Form $G = (V, \Sigma, P, S)$: V: Die Menge der Nicht-Terminale. Für sie benutze ich Großbuchstaben. $\Sigma$: Die Menge der Terminale. Für sie benutze ich … Read More »

Eine Sprache ist nicht regulär - Beweis mit dem Pumping-Lemma Reguläre Sprachen können von endlichen Automaten erkannt werden. Das bedeutet, dass eine endliche Anzahl an Zuständen ausreicht, um ein Wort der Sprache zu akzeptieren. Wenn also eine Sprache $L = {a^i b^{2i} | i \in \mathbb{N}}$ beschrieben wird, müsste gezählt werden, wie oft a vorkommt. a kann aber beliebig … Read More »

Konstruktion eines deterministischen endlichen Automaten aus einem nicht-deterministischem Der nicht-deterministische endliche Automat zu dem regulärem Ausdruck $(a \cup (ab(b)^\text{}ba))^\text{}$ ist folgender: $Q = {S, q_1, q_2}$ $\Sigma = {a, b}$ $\delta = \text{siehe Grafik}$ $F = {S}$ $NEA = \left( Q, \Sigma, \delta, S, F \right)$ Nondeterministic finite-state machine Will man daraus nun den endlichen Automaten konstruieren, läuft … Read More »