Unärdarstellung - Turingmaschine

21.11.2016, 17:36	whatismath_01	Auf diesen Beitrag antworten »
Unärdarstellung - Turingmaschine Meine Frage: Ich habe folgende Aufgabe: Die Unärdarstellung der Zahl vier lautet also IIII = I^4. Konstruieren Sie eine Turingma- schine mit möglichst wenig Zuständen, die genau die Wörter I^n#I^m#I^(n+m) erkennt. Beweisen Sie die Korrektheit Ihrer Konstruktion. Ich weiss leider nicht, was dieses Zeichen "#" in diesem Kontext bedeuten soll sowie wie ich mit dieser Aufgabe umgehen soll... Meine Ideen: Ich weiss ja, dass die Unärdarstellung einer Zahl n die n-fache Wiederholung des Symbols I ist. Sonst habe ich leider keine Idee zu dieser Aufgabe.
24.11.2016, 20:58	xvzwx	Auf diesen Beitrag antworten »
Die Raute (#) ist in diesem Fall ein Symbol des Bandalphabets der TM und dient der Trennung der Sequenzen $\begin{eqnarray} I^{n}, I^{m} \end{eqnarray}$ und $\begin{eqnarray} I^{n+m} \end{eqnarray}$ . Bsp.: wähle n=2, m=3 $\begin{eqnarray} \Rightarrow \end{eqnarray}$ II#III#IIIII ohne die Raute könntest du nicht sagen wo die erste Sequenz mit $\begin{eqnarray} I^{n} \end{eqnarray}$ endet und $\begin{eqnarray} I^{m} \end{eqnarray}$ beginnt usw.. Nun musst du die partiellen Überführungsfunktionen der TM so wählen, dass die TM für alle endlichen Eingaben mit $\begin{eqnarray} n, m \in \mathbb N \end{eqnarray}$ in einem Endzustand landet. Ein Bsp.: lese das erste Zeichen, in diesem Fall ein I und gehe bis an die am weit rechts liegenste Stelle, an der kein "Blank/leeres Feld" ist. Falls dort ebenfalls ein I steht, entferne dieses und laufe wieder nach ganz links usw... da musst du dir jetzt "geschickt" deine Übergangsfunktionen so wählen, das die Anzahl der Zustände/Überführungsfunktionen minimal ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »