Worksheet: Unterschied zwischen den Versionen

Version vom 20. April 2013, 12:35 Uhr

Druckversion

Noch ein Einstiegsbeispiel: Tennis

Konstruiere einen endlichen Automaten, der die Gewinnfolge in einem Tennisspiel modelliert.

Begründe an diesem Beispiel, weshalb ein endlicher Automat kein Gedächtnis dafür hat, auf welchem Weg ein bestimmter Zustand erreicht wurde.

Definition

Definiere "Deterministischer Endlicher Automat" formal. Aus welchen Elementen besteht ein solcher Automat?

Was genau versteht man unter einer Übergangsfunktion (transition function)?

Beispiele

Gib den Graph eines endlichen Automaten an, der Wörter erkennt, die auf "ing" enden.

Teste mit verschiedenen englischen Wörtern, die auf "ing" enden, ob die Wörter tatsächlich von dem Automaten akzeptiert werden. Teste auch, was mit Wörtern passiert, die nicht auf "ing" enden.

Gib den Graph eines endlichen Automaten an, der Binärstrings erkennt, in denen nicht "11" vorkommt.

Teste wieder mit verschiedenen Wörtern.

Gib die Übergänge außerdem als Tabelle an.

Worin besteht der Unterschied zu der Tabellenschreibweise, die du bereits kennen gelernt hast?

Erweiterte Übergangsfunktion

Gib die rekursive Definition der erweiterten Übergangsfunktion an.

Gib für das Beispiel oben (Beispiel mit den Binärstrings) an, wie die erweiterte Übergangsfunktion die Strings "001", "10110" und "0001" auswertet.

Akzeptierte Sprache

Definiere die von einem deterministischen endlichen Automaten akzeptierte Sprache.

Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe oder in der nächsten Plenumssitzung klären kannst!