Turing Maschine

    Hallo

    Habe ein Problem mit folgender Übungsaufgabe
    Erstellen Sie ein Turingprogramm, welches alle Zeichenfolgen anbn mit n > 0 erkennt
    (Beispiel fuer n=3:"aaabbb"). Es ist davon auszugehen, dass zu Beginn der Taetigkeit
    der Turingmaschine der Schreib- Lesekopf auf dem ersten Bit der Eingabe steht und das
    Band außer der Zeichenfolge nur Leerzeichen ("B") enthaelt. Die Eingabe muss danach
    nicht mehr am Band sein. Die Eingaben am Band duerfen durch Ihr Programm zerstoert
    (z.B. durch Leerzeichen ersetzt) werden.

    Kann mir jemand weiterhelfen?

    Lg Noobie93

    Mein Problem liegt darin das ich nicht weiß, wie ich diese Turingmaschine aufzeichnen soll. Denn diese Turingmaschine ersetzt zuerst ein a durch ein B dann fährt sie ans andere Ende des Bandes und ersetzt dort ein b durch ein B. Das macht sie solange bis alles B auf dem Band sind. So hab ich es halt verstanden.

    Meinst du wirklich "zeichnen" oder die formale Definition hinschreiben?

    Wenns zeichnen ist kannst du dir nur mit einem Beispiel helfen wie z.B. dem aaabbb. Dann würd ich pro Step die 2 Bänder skizzieren.

    Solltest du die Turing Maschine nur formal beschreiben müssen dann bräuchtest du:
    Zustandsmenge, Eingabealphabet, Bandalphabet, Übergangsfunktionen, Anfangszustand, Leerzeichen, Endzustand
    http://de.wikipedia.org/wiki/Turingmaschine#Beispiel

    Ein paar der Dinge wie z.b. Alphabet und Leerzeichen werden schon in der Angabe vorkommen.

    Zitat von Noobie93

    Der Inhalt kann nicht angezeigt werden, da er nicht mehr verfügbar ist.

    Sowas meine ich.

    Sieht so aus als wären die States die Knoten und die Übergangsfunktionen die Kanten. Schau da beim Wikipedia Beispiel die Tabelle an.

    Eine Kante heißt zB.
    Wechsele von State q0 in State q1 wenn ein a gelesen wird, gib ein x aufs schreibband und beweg kopf nach rechts.

    Ja das ist mir schon klar, aber ich weiß nicht wie ich die Knoten(Zustande) nennen soll bzw. wie viele ich brauche. Dasselbe gilt ja für die Kanten.
    Was ist dann mein Endzustand

    Die Zustände definierst du selber. Und nennen kannst du sie wie du willst.
    Du hast dir da oben schon einen Algorithmus überlegt. Wieviele Zustände würdest du brauchen um den umzusetzen, wie zB q1 ....Eingabe am ersten a, q2 Eingabe am letzten b,.

    Am besten schreibst dir deinen Algorithmus als Übergangsfunktionen in so einer Tabellen Form mal runter.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden