Theoretische Informatik

Theorie

  • endliche Automaten mit Ausgabe (Transduktoren) und ohne Ausgabe (Akzeptoren)

  • Akzeptoren als formale Sprachbeschreibungsmittel

  • deterministische (DFA) und nichtdeterministische (NFA) endliche Automaten

  • Konstruktion von DFA mit Hilfe von äquivalenten NFA

  • reguläre Ausdrücke; Klasse REG der regulären Sprachen

  • linkslineare Grammatiken

  • (Teil-) Beweise für die Äquivalenz der durch Akzeptoren, reguläre Ausdrücke bzw. linkslineare Grammatiken beschreibbaren Sprachenklassen

  • Sprachenhierarchie von Chomsky; Einordnung (von Teilsprachen) aktueller Programmiersprachen in die Chomskyhierarchie

  • Turingmaschinen

  • Wiederholung: naiver Algorithmenbegriff; These von Church

  • Berechenbarkeit; fleißige Biber; Sigma-Funktion von T. Rado

  • Grenzen von Computern: Die Unlösbarkeit des Halteproblems (mit Beweis für das sog. „spezielle Halteproblem“ für Programmiersprachen)

Ralf Dorn, Fachleiter Informatik