André Vratislavsky

Übungsgruppe Einführung in die Theoretische Informatik

Termine:

• Di, 12-14 c.t. im Raum 039
• Di, 14-16 c.t. im Raum 039

Stichworte:

• Einführung (Rechnermodelle, Berechenbarkeit)
• dfa's, reguläre Ausdrücke
• nfa's, Äquivalenz von dfa und nfa

Musterlösungen zum 2. Übungszettel
• reguläre Ausdrücke zu dfa's, Zustandsminimierung eines dfa
• Pumping Lemma für reguläre Sprachen
• Berechenbarkeit, Turing-Maschinen
• Unentscheidbare Sprachen, Reduktionsschema
• Effizient entscheidbare Sprachen, polynomielle Reduktion
• Grammatiken
• Kontextfreie Sprachen, CNF, Younger-Algorithmus, Pumping Lemma für kontextfreie Sprachen

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 99/00