Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in TUR-AG

Beantwortet: Wann muss man das Wort wiederherstellen, wann darf man es löschen.

Fri, 12 Feb 2016 20:01:59 +0000

Trommelwirbel und hgier ist das Skript:

turing:
(s0, a) => (s1, d, R);
(s0, b) => (s2, e, R);
(s0, c) => (s3, f, R);

(s1, a) => (s1, a, R);
(s1, b) => (s1, b, R);
(s1, c) => (s1, c, R);
(s1, d) => (s9, a, L);
(s1, e) => (s9, b, L);
(s1, f) => (s9, c, L);
(s1, *) => (s4, *, R);

(s2, a) => (s2, a, R);
(s2, b) => (s2, b, R);
(s2, c) => (s2, c, R);
(s2, d) => (s10, a, L);
(s2, e) => (s10, b, L);
(s2, f) => (s10, c, L);

(s3, a) => (s3, a, R);
(s3, b) => (s3, b, R);
(s3, c) => (s3, c, R);
(s3, d) => (s11, a, L);
(s3, e) => (s11, b, L);
(s3, f) => (s11, c, L);

(s4, a) => (s5, d, L);
(s4, b) => (s6, e, L);
(s4, c) => (s7, f, L);
(s4, d) => (see, a, N);
(s4, e) => (see, b, N);
(s4, f) => (see, c, N);

(s5, a) => (s5, a, L);
(s5, b) => (s5, b, L);
(s5, c) => (s5, c, L);
(s5, d) => (s8, a, R);
(s5, e) => (s8, b, R);
(s5, f) => (s8, c, R);

(s6, a) => (s6, a, L);
(s6, b) => (s6, b, L);
(s6, c) => (s6, c, L);
(s6, d) => (s8, a, R);
(s6, e) => (s8, b, R);
(s6, f) => (s8, c, R);

(s7, a) => (s7, a, L);
(s7, b) => (s7, b, L);
(s7, c) => (s7, c, L);
(s7, d) => (s8, a, R);
(s7, e) => (s8, b, R);
(s7, f) => (s8, c, R);

(s8, a) => (s1, d, R);
(s8, b) => (s2, e, R);
(s8, c) => (s3, f, R);
(s8, d) => (see, a, L);
(s8, e) => (see, b, L);
(s8, f) => (see, c, L);

(s9, a) => (s5, d, L);
(s9, d) => (see, a, N);

(s10, b) => (s6, e, L);
(s10, e) => (see, a, N);

(s11, c) => (s7, f, L);
(s11, f) => (see, c, N);

--declarations--
e=#n#;
s0=s0;
F=see,;
blank=*;
inputs=abbbab;
runStepsScript=100;
shortTrace=false;
displayMode=2
--declarations-end--

Beantwortet: Falsche Ansichtsweise?

Tue, 09 Feb 2016 11:47:58 +0000

Hallo,

Palindrome sind Wörter die von vorne nach hinten gelesen das gleiche ergeben wie von hinten nach vorne. Entscheidend ist also, dass das Wort symetrisch zur Mitte ist. Dies ist aber auch z.B. bei dem von dir abgeleiteten Wort aabaa der Fall, wobei hier das b die Mitte darstellt, um das das Wort symetrisch aufgebaut ist.

Palindrome können also sowohl eine gerade als auch eine ungerade Anzahl von Zeichen haben.

Viele Grüße

Tim (Tutor)

Beantwortet: Fehler in der Lösung? Kontextfreie Grammatik

Tue, 19 Jan 2016 10:04:06 +0000

Hallo uagll,

schoen, wenn sich die Frage erledigt hat, nochmal fuer alle: Palindrom bedeutet, dass das Wort von hinten nach vorne gelesen das gleiche ergibt wie anders herum. Also gibt es eine Art Mittelpunkt. Dieser faellt bei Woertern mit ungerader Laenge auf den Mittlersten Buchstaben (vgl. racEcar , hier ist E der Mittelpunkt/Spiegelpunkt) und bei Woertern mit gerader Laenge (vgl. aNNa, hier ist der Spiegelpunkt zwischen den beiden N's) zwischen die beiden mittleren Buchstaben.

Viel Erfolg,

Marvin (Tutor)

Beantwortet: Prolog-Tool zur Simulationen zu Turingmaschinen

Wed, 26 Nov 2014 13:02:36 +0000

Gib einfach mal "Turingmachine Simulation" oder ähnliches in eine Suchmaschine ein. Ich habe z.B. dieses java-Applet gefunden: http://ironphoenix.org/tril/tm/

Das oben erwähnte Prolog-Programm habe ich angehängt. Die TM wird im oberen Bereich des Quelltextes definiert. Ich hoffe, die Kommentare sind selbst erklärend. Die derzeit definierte TM ist die Additions-TM aus der Anwesenheitsübung. Falls du Fragen hast, dann schicke sie mir bitte an tobias.stengel@student.kit.edu

Tobias (Tutor)

Beantwortet: Alternativer Lösungsvorschlag für TM

Wed, 26 Nov 2014 12:58:23 +0000

Wenn ich mich nicht täusche, habe ich bereits heute mittag eine TM von jemandem mit der gleichen Art, die Aufgabennummer zu markieren, korrigiert. Ich nehme an, dass warst du. Es ist sehr zeitaufwendig, eine komplizierter TM zu korrigieren, da ich sie Schritt für Schritt nachvollziehen muss, was zusätzlich fehleranfällig ist. Im Internet sind verschiedene Simulationen zu Turingmaschinen frei zugänglich. Wenn du willst, kann ich dir auch ein Prolog-Programm schicken/hochladen, dass für eine gegebene TM entscheidet, ob sie in einem Endzustand hält und wenn ja, mit welchem Bandinhalt. Da letztes Semester in Info I Prolog behandelt wurde und die Prolog-Syntax sehr einfach ist, könntest du deine TM leicht eintragen und testen (falls du den Interpreter noch installiert hast). Für die Korrektheit des Programms kann ich jedoch nicht garantieren.

Alternativ kannst du auch warten, bis ein Tutor/eine Tutorin Zeit hat, deine Lösung anzuschauen. Wenn ich dich recht verstanden habe, weißt du bereits, dass deine TM unnötigerweise die Bandinschrift am Ende wieder herstellt.

Gruß,

Tobias (Tutor)

Beantwortet: Verwenden von "*" statt "#" möglich ?

Wed, 26 Nov 2014 12:55:18 +0000

Hallo Lars,

deine Turingmaschine sieht soweit ganz gut aus. Es gibt nur ein Problem, wenn du ein Palindrom mit einer geraden Anzahl an Zeichen (z.B. aa) erkennen willst. In diesem Fall wechselt dein Automat nicht in den Endzustand über. Du müsstest hier noch im Zustand s0 einen Übergang in den Endzustand bei Eingabe einer Raute hinzufügen. Dann müsste es passen.

Viele Grüße

Lukas (Tutor)

Beantwortet: Wann erkennt Turingmaschine ein Wort ?

Wed, 26 Nov 2014 12:49:43 +0000

Hallo,

Eine Turingmaschine hält akzeptierend, falls sie in einem Endzustand ist und kein weiterer Übergang möglich ist. Sie ist also in einer akzeptierenden Endkonfiguration (v, s, w) mit v ist Bandinschrift links und w ist Bandinschrift rechts vom Schreib-Lese-Kopf und "s ist Element der Menge der Endzustände" und für (v, s, w) existiert keine Folgekonfiguration.

Viele Grüße

Christiane (Tutorin)

Beantwortet: Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum: a)

Wed, 26 Nov 2014 12:46:32 +0000

Wäre es auch so möglich?

S -> aAa | bAb | cAc | a | b | c

A -> S | lambda

Beantwortet: Zustand Sn überflüssig ?

Wed, 26 Nov 2014 12:37:32 +0000

Sie haben recht, der Zustand sN ist nicht notwendig (wenn es nicht so in der Aufgabenstellung gefordert ist). Es kann aber bei komplizierteren Aufgaben einfacher sein, so den Überblick zu behalten.

Viele Grüße
Friederike Pfeiffer

Beantwortet: Teil a) Vereinfachung der Grammatik möglich ?

Wed, 26 Nov 2014 12:35:14 +0000

so könnten nur Wörter ungerader Länge erzeugt werden, was nicht ausreichend ist, deshalb der zusätzl. Übergang

Beantwortet: Was ist Zustand s00 ?

Wed, 26 Nov 2014 12:33:38 +0000

Auf s00 wird erst aus sL zugegriffen und wird benötigt, da ich, wenn ich hier auf * stoße, in einen Endzustand wechsel.
Wenn ich das von s0 aus machen würde, dann würden Sie das leere Wort auch erkennen, was aber laut Aufgabenbeschreibung nicht in der Sprache ist.

Freundliche Grüße
Friederike Pfeiffer

Beantwortet: Definition von Lambda

Wed, 26 Nov 2014 12:31:28 +0000

Ja, das stimmt.

(Ausgenommen bestimmte Normalformen wie die Chomsky-Normalform, wo genau dasselbe gilt wie bei kontextsensitiven Grammatiken.)

Grüße

Lukas König