Auf dem 10ten Blatt Aufgabe 10.3 ist bei dem DTM das wort w = a^2n…Bedeutet das nun, dass man eine gerade anzahl an a's in einem wort haben muss ?
soweit ich gesehen habe, lautet bei 10.3 für das Wort
w = a^2^n…sprich du hast 2^n und somit sind die a's bis auf den Sonderfall a^2^0=a^1 immer gerade
(kann mich auch irren FGI ist nicht gerade meine stärke)
Also die Anzahl der a's ist gerade aber weiterhin ist die Anzahl der a's auch noch eine Zweierpotenz!
Das bedeutet z.B. a^6 (also 6 a's) ist nicht zugelassen obwohl die Anzahl gerade ist, aber 6 ist keine 2er Potenz!
Es ist in der Mathematik Kovention, dass a^b^c als a^(b^c) interpretiert wird. Ist (a^b)^c gemeint, muss geklammert werden, was hier nicht der Fall ist.
Im Übrigen wäre die Aufgabe dann doch auch ein bisschen zu einfach, da würde ja ein endlicher Automat statt einer Turing-Maschine reichen. ;)
Dies ist übrigens wieder eine Aufgabe, für die es ganz toll viele verschiedene Lösungen gibt. :) Meine eigene Lösung operiert irgendwie an dem Eingabestring selbst rum und stell rekursiv fest, ob die Kette von as so lange immer wieder in der Mitte teilbar ist, bis nur noch einzelne a dastehen. Das ist recht aufwändig geworden… hab aber hinterher auch nochmal probiert, eine Turing-Maschine zu entwerfen, die die as Stück für Stück löscht und mittels einer binären Zahl mitzählt (für jedes a 1 addiert). Wenn dann zum Schluss die binäre Zahl genau eine 1 enthält, war's eine Zweierpotenz. Diese Lösung hab ich in 6 Zustände quetschen können. Wer unterbietet mich?
Wenn dann zum Schluss entweder überhaupt kein a vorhanden war
Ist das wirklich erlaubt? a^2^n kann doch nie das leere Wort sein, oder?
Du hast völlig Recht. Da habe ich etwas aus der Aufgabenstellung herausgelesen, das gar nicht da steht. Hab meinen Beitrag mal editiert um Verwirrung vorzubeugen.
