Lehrver­anstaltung

FSA - Formale Sprachen und Automatentheorie


PDF Lehrveranstaltungsverzeichnis English Version: FSA

Version: 1 | Letzte Änderung: 03.09.2019 11:28 | Entwurf: 0 | Status: vom verantwortlichen Dozent freigegeben

Langname Formale Sprachen und Automatentheorie
Anerkennende LModule FSA_BaTIN
Verantwortlich
Prof. Dr. Hans Nissen
Professor Fakultät IME
Niveau Bachelor
Semester im Jahr Sommersemester
Dauer Semester
Stunden im Selbststudium 78
ECTS 5
Dozenten
Prof. Dr. Hans Nissen
Professor Fakultät IME
Voraussetzungen keine
Unterrichtssprache deutsch
separate Abschlussprüfung Ja
Literatur
Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008
Rolf Socher: Theoretische Grundlagen der Informatik Carl Hanser Verlag, 2007
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik 4. Auflage, Vieweg Verlag, 2006
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie 3. Auflage, Pearson Studium, 2011
Abschlussprüfung
Details
Die schriftliche Klausur stellt sicher, dass jeder Studierende auch individuell die Ziele des Learning Outcomes erreicht hat,
durch Aufgaben der folgenden Typen:
Systeme aus abstrakter Perspektive formalisieren und analysieren,
gegebene formale Sprachen formalisieren,
Grammatik zu gegebener Sprache spezifizieren,
akzeptierende Automaten für gegebene Sprachen identifizieren,
eine Beschreibungsform einer formalen Sprachen in eine andere, äquivalente Beschreibungsform transformieren,
Beweisen oder Widerlegen, das eine Sprache zu einer bestimmten Sprachklasse gehört.
Mindeststandard
Mindestens 50% der möglichen Gesamtpunktzahl.
Prüfungstyp
Die schriftliche Klausur stellt sicher, dass jeder Studierende auch individuell die Ziele des Learning Outcomes erreicht hat,
durch Aufgaben der folgenden Typen:
Systeme aus abstrakter Perspektive formalisieren und analysieren,
gegebene formale Sprachen formalisieren,
Grammatik zu gegebener Sprache spezifizieren,
akzeptierende Automaten für gegebene Sprachen identifizieren,
eine Beschreibungsform einer formalen Sprachen in eine andere, äquivalente Beschreibungsform transformieren,
Beweisen oder Widerlegen, das eine Sprache zu einer bestimmten Sprachklasse gehört.

Lernziele

Kenntnisse
Formale Sprachen und Chomsky-Hierarchie

Formalisierung von Grammatiken

Formalisierung von abstrakten Rechnermodellen
verschiedene endliche Automaten
Kellerautomat
Turingmaschine

reguläre Ausdrücke

Eigenschaften unterschiedlicher Sprachklassen
Abgeschlossenheit
Entscheidbarkeit
Pumping Lemma

Fertigkeiten
Sprachklasse einer gegebenen Sprache bestimmen

formale Sprachen spezifizieren

Grammatik für gegebene Sprache erstellen

Automat für gegebene Sprache erstellen

Automat für gegebene Grammatik erstellen

Formalisierungen transformieren

formale Beweise zu formalen Sprachen, Grammatiken und Automaten durchführen

Probleme der realen Welt formalisieren

abstrakte Automaten für reale Probleme entwerfen
Aufwand Präsenzlehre
Typ Präsenzzeit (h/Wo.)
Vorlesung 2
Übungen (ganzer Kurs) 0
Übungen (geteilter Kurs) 2
Tutorium (freiwillig) 0
Besondere Literatur
keine/none
Besondere Voraussetzungen
keine
Begleitmaterial
elektronische Vortragsfolien zur Vorlesung

elektronische Übungsaufgabensammlung
Separate Prüfung
keine

© 2022 Technische Hochschule Köln