In der Vorlesung vom 25.04.2013 hat Prof. Hofheinz gesagt, dass man semantische Sicherheit praktisch nicht beweisen kann, da man zuerst beweisen müsste. Warum das so ist, versuche ich nun zu erläutern. Einwegfunktionen und Sei eine Funktion. heißt eine Einwegfunktion, genau dann wenn für alle gilt: kann in Polynomialzeit berechnet werden Für die Berechnung eines Urbildes [...]
Formale Sprachen A heißt Alphabet A ist eine endliche, nicht leere Menge aus Zeichen. w heißt Wort aus w ist eine endliche Aneinanderreihung von Zeichen aus A L heißt formale Sprache G heißt formale Grammatik wobei: N die endliche Menge der Nichtterminalsymbole bezeichne, T die endliche Menge der Terminalsymbole mit bezeichne, das Startsymbol, die endliche [...]
Ich habe im WS 2011/2012 bei Frau Prof. Dr. Wagner die TGI-Klausur am KIT geschrieben. Hierfür entstand dieser Artikel. Für die Klausur in den Theoretischen Grundlagen der Informatik sollte man Folgendes auf jeden Fall wissen: Wie konstruiert man mittels Potenzmengen einen äquivalenten deterministischen endlichen Automaten zu einem Nichtdeterministischen? → Antwort Wie bringt man eine Grammatik [...]
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, das ist also mit Vorsicht zu genießen. Ein weiterer Einsatzzweck ist die Syntaxanalyse einer Tokenfolge. Das kann für Compiler oder [...]
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 umständlich ist, werde ich im [...]
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 Einsatz. Jede kontextfreie Grammatik kann [...]
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. Akzeptierende von nichtakzeptierenden Zuständen trennen: [...]
