André Vratislavsky

Übungsgruppe Einführung in die Theoretische Informatik

Termine:

• Mo, 10-12 im 037
• Di, 14-16 in der Villa

Stichworte:

• Einführung: Rechnermodelle, Berechenbarkeit
• Reguläre Ausdrücke
• Deterministische und Nichtdeterministische Endliche Automaten
• Zusammenhang: Endliche Automaten-reguläre Ausdrücke
• Grammatiken und Kontextfreie Sprachen
• Kontextfreie Grammatiken und Syntaxbäume
• Pumping-Lemma für Reguläre und Kontextfreie Sprachen
• Chomsky-Normalform, Younger-Algorithmus, Abschlußeigenschaften Kontextfreier Sprachen
• Informationen zum 8. Zettel von Enno Brehm
• Testeingaben für die Programmieraufgabe vom 8. Übungszettel
• FALSCHE Aussagen über Kontextfreie Sprachen
• Berechenbarkeit

Zum Nachblättern und Ausprobieren:

Applet für die Konstruktion eines endlichen deterministischen Automaten

Turing Machines

Der fleißige Biber, ein Applet

Ein Turing-Simulator von Keneth's Team (Buena Vista University)

Turing-Simulator
 
 

Die offizielle Seite der Vorlesung im WS 98/99

Meine Homepage