# Dots Podcast 2

## Auflösung Rätsel

## Einleitung

* Operationellle Modelle / Logik zwei ganz großen Bereiche der Theoretischen Informatik. 

## Endliche Automaten

* Definition
* Deterministische und Nicht deterministische Automaten
* Lexer / Verbindung zu reguläre Ausdrücken


## Kellerautomaten

* Problem mit Endlichen Automaten Klammerausdrücke
* Erweiterung um Kellerspeicher
* Parser
* Probleme deterministies und nichtdeterministische nicht Äquivalent

## Turingmaschinen

* Können immer noch nicht alles z.B. Mehrfache Wiederholung
* Erweiterung durch z.B. zweiten Keller
* Können dann alles was man auch intuitiv kann 
* Sind Modell für computer

## Überleitung zu DOTS3
* Alterantive Modelle für Berechenbarkeit z.B. Lambda-Kalkül

## Rätsel

Weihnachtsmann und Rudolf spielen Schere-Stein-Papier-Brunnen um die Weihnachtsplätzchen.
ABER Rudolf ist ein Paarhufer und kann deshalb Brunnen nicht zeigen. 
Der Weihnachtsmann will aber nicht auf Brunnen verzichten, deshalb einigen
sich Rudolf und der Weihnachtsmann, falls das unfair ist gleichen sie das aus
indem Rudolf sich alle x Runden zum ausgleich einen Weihnachtsplätzchen nehmen darf.
Jetzt ist nur die Frage, ist das unfair? Und wenn ja, alle wieviel Runden darf sich Rudolf 
einnen Keks nehmen?