-
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, Pumping-Lemma
-
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
