Humboldt-Universität zu Berlin, Institut für Informatik

Automaten und Sprachen

Vorlesender: Prof. P. H. Starke

Diese Vorlesung war Bestandteil des Grundstudiums der Lehrerausbildung und wurde im Wintersemester 1994 gehalten. Das Script zur Vorlesung wurde von Michael Weber erstellt.

• TeX-DVI (221 kB)
• TeX-DVI-GZIP (80 kB)

Aus dem Inhalt:

• Algebra der Wörter
• Automaten
• • Zustandsbegriff in der Systemtheorie
  • Automatenbegriff
  • Erweiterung von delta und lambda auf Wörter über X
  • Äquivalenz von Zuständen und Automaten
  • Berechnung der Äquivalenzklassen
  • Eingabe-/Ausgabeverhalten
• Regelsprachen und Automaten
• • Akzeptoren
  • Grammatiken
  • Kellerautomaten
• Berechenbarkeit
• • Einführung
  • mathematische Charakterisierung der Berechenbarkeit