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 [...]
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 in Chomsky-Normalform? → Antwort. Was macht der CYK-Algorithmus und wie funktioniert er? → siehe Beispiel ab Folie 15 Was [...]
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 [...]
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 in Chomsky-Normalform gebracht werden. Die Chomsky-Normalform Das Besondere an der Chomsky-Normalform ist, [...]
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: [...]
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 : V: Die Menge der Nicht-Terminale. Für sie benutze ich Großbuchstaben. : Die Menge der Terminale. Für sie benutze ich Kleinbuchstaben. P: Die Produktion, also die Regeln mit denen [...]
