Java Programmierung einer Turing-Maschine

Question

Habe folgende Informationen bezüglich der Aufgabe

k = m mod n

Zahlen sollen als Binär mit dem MSB zuerst übermittelt werden.

Bei der Eingabe von n = 5 soll ich folgende Ausgaben erhalten.

Die erste Zeile soll $$q_i-1$$ die zweite Zeile die Übergangsfunktion von $$(q_i-1, 0)$$ und die dritte die Übergangsfunktion von $$(q_i-1, 1)$$ sein.

0 0 1
1 2 3
2 4 0
3 1 2
4 3 4

Mein Problem ist gerade, dass ich die Relationen nicht ganz nachvollziehen kann.

Was ich verstehe ist, dass bis n-1 gezählt wird und die Relationen die Zähler sind die im Gedächtnis bleiben.

Verstehe das nun in binär nicht so wirklich damit ich die Relationen programmieren kann.

Habe das aktuell in Integer Variante so programmiert, dass ich in der 1. Zeile i und dies bis n-1 läuft.

Und den Rest als unnötige Zähler die sich wiederholen bis i = n-1 ist

Comments

Eingabe Die Eingabe für Ihr Programm ist eine einzige Zeile mit der Zahl n ∈ N, die Anzahl der zu beliefernden Kinder.
Sie sollen einen deterministischen endlichen Automaten mit exakt n Zuständen q0,...,qn−1 konstruieren, der bei Eingabe
bin(m) am Ende der Berechnung in Zustand qm mod n endet. Die Werte m bzw. bin(m) sind nicht Teil der Eingabe, der
Automat soll diese Eigenschaft für beliebige m ∈ N erfüllen.
Ausgabe Ihre Ausgabe soll exakt aus n Zeilen bestehen, wobei die ite Zeile das Verhalten des Automaten in Zustand
qi−1 beschreibt: Zeile i enthält die Zustände qi−1 δ(qi−1,0) δ(qi−1,1).

Answer 1

dass ich die Relationen nicht ganz nachvollziehen kann.

Ist der bis jetzt berechnete Rest q und wird eine 0 gelesen, dann ist der neue Rest 2q mod n.

Ist der bis jetzt berechnete Rest q und wird eine 1 gelesen, dann ist der neue Rest (2q+1) mod n.

Comments

Danke, komme jetzt damit auf die dritte Zeile habe das vorher ohne eine Turing ähnliche Methode gemacht.

Was passiert nach der 3. Zeile?

Soll ja annehmen, dass der Kopf nicht weiß welche Nummer das Band beinhaltet.

Habe das jetzt so gemacht, dass jede Position innerhalb einer for Schleife gelesen wird.

Und habe die gelesenen mit # ersetzt, da diese gelesen wurden, würde ich nun diese -1 setzen würde ich ja den Lesevorgang davor verfälschen.

Einen Counter mit n-i in einen Substring setzen? Und somit die Dekrementierung vollziehen?

---

Was passiert nach der 3. Zeile?

2·3 mod 5 = 1

(2·3+1) mod 5 = 2

Daher die Zeile 3 1 2.

Ebenso 2·4 mod 5 = 3 und (2·4+1) mod 5 = 4. Daher die Zeile 4 3 4.

Und habe die gelesenen mit # ersetzt,

Du sollst einen deterministischen endlichen Automaten konstruieren. Der kann auf das Band nicht schreiben. Es ist auch überhaupt nich notwendig, auf das Band zu schreiben, weil der Automat die Leserichtung nicht ändern kann und nach jedem Lesevorgang zum nächsten Zeichen geht und der Automat deshalb an der geschriebenen Position sowieso nie wieder lesen kann.

Einen Counter mit n-i in einen Substring setzen?

Ich weiß nicht, was du damit meinst.

Und somit die Dekrementierung vollziehen?

Ich weiß nicht, was du wo warum dekrementieren möchtest.

---

Moment, 5 hat ja 3 Bits 101

Es finden also 3 Lesevorgänge statt.

Meine Frage ist, wie ich nach diesen 3 Lesevorgängen vorgehen kann.

---

Dein Java-Programm bekommt als Eingabe ein int n.

Als Ausgabe soll dein Java-Programm eine Tabelle liefern, die die Übergangsfunktion beschreibt.

Die Tabelle soll so gestalltet sein, das in der ersten Spalte der aktuelle Zustand steht, in der zweiten Spalte der Folgezustand falls eine 0 gelesen wird und in der dritten Spalte der Folgezustand falls eine 1 gelesen wird.

Moment, 5 hat ja 3 Bits 101

Die 5 ist eine Eingabe für das Java-Programms, nicht für den Automaten.

Nemen wir als Beispiel n=5. Dann soll die Ausgabe ja

        0 0 1
        1 2 3
        2 4 0
        3 1 2
        4 3 4

sein. Diese Ausgabe ist wie folgt zu verstehen:

Ich suche mir eine Zahl aus:

        34.

Ich wandle sie in Binärdarstellung um:

        100010

Ich füttere sie in den Automaten:

1. Anfangszustand ist 0. Es wird eine 1 gelesen. Folgezustand ist also 1.
   
2. Aktueller Zustand ist 1. Es wird eine 0 gelesen. Folgezustand ist also 2.
   
3. Aktueller Zustand ist 2. Es wird eine 0 gelesen. Folgezustand ist also 4.
4. Aktueller Zustand ist 4. Es wird eine 0 gelesen. Folgezustand ist also 3.
5. Aktueller Zustand ist 3. Es wird eine 1 gelesen. Folgezustand ist also 2.
6. Aktueller Zustand ist 2. Es wird eine 0 gelesen. Folgezustand ist also 4.
   

Diese Berechnung durchzuführen ist aber nicht Aufgabe deines Java-Programms.

---

Verstehe das nicht so ganz, ich soll die Zustände angeben, dafür benötige ich doch genau die Binäre Darstellung um den Folgezustand zu wählen.

Deswegen bin ich verwirrt bei der Binärdarstellung 101.

Da ich nach dem letzten Bit keine weiteren Bits habe.

(habe mich auch mit der Aufgabe vertan es wird DFA gefordert)

Nun ist mein Wort jedoch am Ende angelangt und ich komme nicht zu der Tabelle.

(Habe die Aufgabe in einem Programm gelöst bekommen mithilfe einer For Schleife die n mal läuft, jedoch gibt der Text meiner Aufgabe an, dass nicht von Beginn an, alle Bits überblickt werden, sondern nur eines zur Zeit)

---

ich soll die Zustände angeben

Nein. In der Aufgabenstellung steht bereits, welche Zustände der automat haben soll, nämlich: "Sie sollen einen deterministischen endlichen Automaten mit exakt n Zuständen q₀,...,q_n−1 konstruieren, ..."

Da wäre es sinnlos, die Zustände anzugeben.

Du sollst die Übergangsfunktion angeben.

dafür benötige ich doch genau die Binäre Darstellung

Die brauchst du nur, wenn du den Automaten ausführen möchtest. Du sollst den Automaten aber nicht ausführen, sondern nur dessen Übergangsfunktion ausgeben.

---

Also

Ich soll das Java Programm soll ja die Tabelle ausgeben.

So Eingabe ist n im Beispiel ja 5

Diese muss ich für die Tabelle (Die ja Zustände und Übergänge bei 0 oder 1 im aktuellen Bit beinhaltet) in Binär umwandeln.

Ansonsten kann mein Programm ja schlecht entscheiden was die erste Spalte in der nächsten Zeile ist. Also der ausgewählte Übergang.

So mein Programm muss somit erstmal 5 in Binär umwandeln.

Mein Programm speichert die Bitdarstellung dann zwischen und benutzt diese für die Tabelle

Nun

101

Erste 3 Zeilen wären

0 0 1 Wählt 1 aus
1 2 3 Wählt 2 aus
2 4 0 Wäht 0 aus

Genau da liegt gerade mein Verständnisproblem. Dies ist ja nicht das Beispiel

Also bei einem Ende der Bitfolge weiter korrekt vorzugehen.

---

So Eingabe ist n im Beispiel ja 5

Diese muss ich für die Tabelle ... in Binär umwandeln.

Nein.

Ansonsten kann mein Programm ja schlecht entscheiden was die erste Spalte in der nächsten Zeile ist. Also der ausgewählte Übergang.

Was die nächsten Zeile ist, steht in der Aufgabenstellung:

        "Zeile i enthält die Zustände q_i−1 δ(q_i−1,0) δ(q_i−1,1)."

---

$$q_{i-1}$$ ist doch der Zustand der letzten Zeile

δ(qi−1,0) oder δ(qi−1,1) je nachdem ob jetzt eine 0 oder eine 1 vorkam?! (Und ob nun eine 0 oder 1 vorkam kann man doch nur auswählen durch binäre Darstellung?

---

In der Aufgabenstellung kommen drei Variablen vor: n, i und m. Mir scheint, als ob noch nicht ganz klar ist, was sie bedeuten.

• n ist die Zahl, durch die ganzzahlig geteilt wird. Der Automat, deren Übergangsfunktion du ausgeben sollst, hängt nur von n ab, nicht von i und m. Die Binärdarstellung von n wird nicht benötigt.
  
• i wird verwendet, um allgemein zu formulieren, wie die Zeilen deiner Ausgabe aussehen sollen. i kann jeden Wert von 1 bis n annehmen. Für jeden möglichen Wert von i sollst du eine Zeile Ausgabe erzeugen.
• m ist die Zahl, deren Binärdarstellung an den Automaten übergeben wird um einen Lauf des Automaten zu erzeugen. Du sollst keinen Lauf des Automaten erzeugen.

---

Die Binärdarstellung von n wird nicht benötigt.

Sagen wir ich habe

q2 δ(q2,0) δ(q2−1,1)

q3 δ(q3,0) δ(q3−1,1)

Dann ist q3 doch δ(q2,0) || δ(q2−1,1) da liegt gerade mein Problem

---

Dann ist q3 doch δ(q2,0) || δ(q2−1,1)

Nein.

δ(q₂,0) ist q₄ und δ(q₂,1) ist q₀.

---

Gut okay was ist die Logik dahinter?

---

Angenommen der Automat hat eine Folge von Nullen und Einsen gelesen, so dass er im Zustand q₂ ist.

Eine solche Folge wäre zum Beispiel 1,0. Fasst man diese Folge als Binärdarstellung einer Zahl auf, dann lautet diese Zahl 2. Dividiert man 2 mit Rest durch 5, dann erhält man den Rest 2. Deshalb soll sich der Automat nach Lesen obiger Folge im Zustand q₂ befinden.

Wird jetzt eine Null gelesen, dann wurde insgesamt die Folge 1,0,0 gelesen, was der Zahl 4 entspricht. Dividiert man 4 mit Rest durch 5, dann erhält man den Rest 4. Deshalb soll sich der Automat nach Lesen von 1,0,0 im Zustand q₄ befinden. Er muss also vom Zustand q₂ durch Lesen einer Null in den Zustand q₄ übergehen. Anders ausgedrückt δ(q₂,0) = q₄.

Wird stattdessen eine Eins gelesen, dann wurde insgesamt die Folge 1,0,1 gelesen, was der Zahl 5 entspricht. Dividiert man 5 mit Rest durch 5, dann erhält man den Rest 0. Deshalb soll sich der Automat nach Lesen von 1,0,1 im Zustand q₀ befinden. Er muss also vom Zustand q₂ durch Lesen einer Eins in den Zustand q₀ übergehen. Anders ausgedrückt δ(q₂,1) = q₀.

---

Also sind alle Zustände qi-1 die Zahlen 0 bis (n-1), richtig?

Und je nachdem was eingelesen erfolgen andere Übergänge?

---

Habe das jetzt wie folgt programmiert

import java.util.Scanner;

public class test2 {
 private static int x = 0;
 private static int n;
 private static int y = 1;
 
 public static void main(String[] args) {
 
 

Scanner news = new Scanner(System.in);
if (news.hasNextInt()){
n= news.nextInt();
if (n>0){
 for (int i=0; i <= n-1;i++) {
 if (y>n) {
 y= -1*(n-y);
 }
 if (x>n) {
 x=-1*(n-y);
 }
 if (x==n ) {
 x =0;
 }
 if (y==n ) {
 y =0;
 }
 System.out.println(i+" "+x+" "+y);
 x=y+1;
 y=x+1;

 }}
 } else {System.out.println("Error");} 
}}

---

Habe das jetzt wie folgt programmiert

Das Programm scheint das zu tun, was es tun soll.

Ich habe mich auch mal dran versucht:

import java.util.Scanner;

class Automat {
    public static void main(String[] args) {
        Scanner news = new Scanner(System.in);
        
        if (news.hasNextInt()) {
            int n = news.nextInt();
            if (n>0) {
                for (int i = 0; i < n; ++i) {
                    System.out.printf("%d %d %d\n",
                        i, (2*i) % n, (2*i+1) % n);
                }
                return;
            }
        } 
        
        System.out.println("Error");
    }
}