Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in TUR-AG

Antwort ausgewählt: Wann muss man das Wort wiederherstellen, wann darf man es löschen.

Sat, 23 Apr 2016 06:00:33 +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--

Antwort erneut angezeigt: Falsche Ansichtsweise?

Tue, 09 Feb 2016 12:08:54 +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)

Kommentar erneut angezeigt: Alternativer Lösungsvorschlag für TM

Mon, 01 Dec 2014 19:26:12 +0000

Jepp, der andere war auch von mir! Tut mir leid, wenn ich dass Forum so überbeanspruche ;-) Man ist sich halt seiner Lösung dann doch nicht immer so sicher. Wo finde ich im Netz den so ein Prolog-Tool?

Antwort ausgewählt: Verwenden von "*" statt "#" möglich ?

Fri, 28 Nov 2014 23:16:17 +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)

Kommentiert: Prolog-Tool zur Simulationen zu Turingmaschinen

Wed, 26 Nov 2014 13:03:13 +0000

Hab ich vergessen: testen kann man das Programm, indem man es im Interpreter lädt (consult('TM_Prolog.pl'). ) und dann die TM mit starten(Bandinschrift rechs vom lesekopf als liste). startet, z. B bekommt man dann die Ausgabe:
?- starten([1,1,1,1,1]).
[*,*,1,0,0,0,0,0,*,*,*]
true

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)

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

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

Hallo,

ja, das passt so, denn wenn man die Umbenennung A -> S ersetzt kommt man wieder auf die Musterlösung.

Viele Grüße

Philippe

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