Satz 0^k1^k ist L

Einfache Sprache

Def. Satz 0^k1^k ist L

Die Sprache 0^k1^k ist in L.

Beweis: Wir können nicht die Eingabe verändern, da das Rechenmodel (2 Band TM mit read-only Eingabeband) von L das nicht erlaubt. Wir können aber erst sicherstellen das auf dem Band nur Nullen gefolgt von Einsen stehen. Dann können wir die Anzahl der der Einsen und Nullen zählen. Dazu brauchen wir zwei Zähler die wir pro Sichtung beim von “links nach rechts gehen” jeweils inkrementieren. Die Zähler sind in binärere Darstellung und verbrauchen daher nur logarithmischen Platz im Relation zur Eingabelänge. Damit ist gezeigt wie eine DTM mit $O(\log n)$ Speicherplatzbedarf die Sprache entscheidet.