Kursthemen

  • Allgemeines

    • Abschnitt 1

      In der Theoretischen Informatik werden zwei Modellklassen unterschieden:

      Automaten
      		Grammatiken
      Automaten beschreiben das Verhalten von Systemen, die auf Eingaben unterschiedlich reagieren können, je nachdem, in welchem Zustand sie sich gerade befinden. Grammatiken beschreiben die Struktur von formalen Sprachen, die von den Automaten akzeptiert werden.
      Alan Turing Noam Chomsky


      Während Grammatiken Worte einer Sprache produzieren, werden Automaten verwendet, um Sprachen zu akzeptieren, das heisst, zu entscheiden, ob ein Wort zu einer Grammatik passt.

    • Abschnitt 2

      I. Transduktoren

      Endliche Automaten, die bei jedem Übergang eine Ausgabe erzeugen

    • Abschnitt 3

      Anwendung unserer Kenntnisse

      Wir wollen das Grundmodell unseres Kaffeeautomaten Pott, den Pott-1 zu Pott-2 erweitern:

      Pott-2 akzeptiert wie Pott-1 nur 50Cent- und 1€-Münzen, der Benutzer kann aber für 1,50€ zwischen Kaffee und Latte wählen. Dazu gibt es zwei Taster, die man drücken kann. Sie reagieren aber erst, wenn ein Mindestbetrag von 1,50€ erreicht ist.

    • Abschnitt 4

      II. Akzeptoren

      Endliche (erkennende) Automaten ohne Ausgabe, deren Endzustand den Wert TRUE liefern.
      Erkennende Automaten sind "Maschinen", die Zeichenketten lesen und dabei auf syntaktische Korrektheit überprüfen. Diese EA produzieren keine Ausgaben, sondern zeigen ein Ergebnis über ihren Zustand an. Befindet sich der Akzeptor nach Abarbeitung aller Eingabezeichen im richtigen Zustand, dann war die Zeichenkette korrekt, anderenfalls trat ein Syntaxerror auf.
      Die Menge aller akzeptierten Worte bezeichnet man als Sprache des Automaten.
      Einführungsbeispiel:
      Wir nehmen an, dass für die Eingabe einer korrekten Email-Adresse der Form       name@provider.de folgende Regeln gelten:
      • Jeder name besteht aus mindestens 1 Buchstaben
      • jeder provider ist mindestens 2 Buchstaben lang
      • Erlaubt sind nur Kleinbuchstaben
      Worte dieser Sprache sollen mit einem erkennenden Automaten überprüft werden.