Theoretische Informatik

Semester: WI/4 
Umfang (SWS): 2 + 2 

Inhalt: 

1. Gebiete der theoretischen Informatik 

2. Formale Sprachen 
   2.1 Einführung des Begriffs der formalen Sprache 
   2.2 Abzählbarkeit, Aufzählbarkeit, Entscheidbarkeit 
   2.3 Grammatiken 
   2.4 Backus-Naur-Form, Syntaxdiagramme 
   2.5 Chomsky-Hierarchie 

3. Reguläre Sprachen - Endliche Automaten 
   3.1 endliche Automaten, Zustandsdiagramme 
   3.2 nichtdeterministische endliche Automaten 
   3.3 Zusammenhang nichtdeterministische - deterministische endliche Automaten 
   3.4 Scanner-Generatoren 
   3.5 reguläre Ausdrücke 

4. Kontextfreie Sprachen - Kellerautomaten 
   4.1 Syntaxbäume 
   4.2 Anwendungen bei der syntaktischen Analyse 
   4.3 Normalformen 
   4.4 Kellerautomaten 
   4.5 Simulation des Pflanzenwachstums mit Hilfe von Grammatiken 

5. Typ-0-Sprachen - Turingmaschinen 
   5.1 Turingmaschinen 
   5.2 Erkennen von Sprachen durch Turingmaschinen 
   5.3 Berechnung von Funktionen durch Turingmaschinen 
   5.4 Bedeutung von Turingmaschinen für die Informatik