Formale Sprachen / Automatentheorie

INFB Formale Sprachen / Automatentheorie		SG	INF
Dozent :	Prof. Dr. rer. nat. Friedhelm Mündemann eMail \| Homepage Prof. Dr. rer. nat. habil. Jörg Richard Weimar eMail \| Homepage	Semester	2
Einordnung :	Informatik Bachelor	SWS	4
Sprache :	Deutsch	Art	V Ü
Prüfungsart :	PL	Credits	4
Prüfungsform :	Klausur 120 min
Voraussetzungen :	Informatik und Logik Mathematik I
Querverweise :
Vorkenntnisse :
Hilfsmittel und Besonderheiten :	Studien- und Prüfungsleistungen: Erfolgreiche Bearbeitung der Übungsaufgaben. Die Note entspricht der Note der Abschlussklausur.
Lehrziele :	Sich in formalen Systemen zurechtfinden, Grenzen des Einsatzes von Algorithmen und Re-chentechnik kennen, Definitionsmöglichkeiten von Sprachen kennen, Automaten kennen, konstruieren, analysieren und einsetzen können
Lehrinhalte :	Mathem. Grundbegriffe (Mengen, Relationen, Funktionen), Algorithmus-Begriff, Berechenbarkeitstheorie, Grenzen der Berechenbarkeit Theorie der Formalen Sprachen (Sprachschätze, Grammatiken, Ableitungen, Chomsky-Hierarchie) Automatentheorie (endliche Automaten, Kellerautomaten, Linear beschränkte Automaten, Turingmaschinen)
Literatur :	Kaiser, Mlitz, Zeilinger: Algebra für Informati-ker Schmidt, Ströhlein: Relations and Graphs, Stetter: Grundbegriffe der Theoretischen Informa-tik Cap: Theoretische Grundlagen der Informatik