Seite 1 von 1

Übungsblatt 12, Aufgabe 6

BeitragVerfasst: 26 Jan 2014, 13:59
von tegi
Hallo zusammen,

wie genau sieht die (markierte) Wiederholungssprache aus? Ich verstehe die Definition nicht ganz. Was unterscheidet die Sprache rein anschaulich von der "normalen" Wiederholungssprache?
Insbesondere: Wie ist das Symbol # in unserem Zusammenhang definiert? Vielleicht ergibt sich dann die Antwort zu Frage 1.

Danke und Grüße,
Tobias

Re: Übungsblatt 12, Aufgabe 6

BeitragVerfasst: 26 Jan 2014, 18:35
von Dominik.Kirst
Hallo Tobias,

im Unterschied zur "normalen" Wiederholungssprache sitzt in der Mitte der Wörter aus der markierten Wiederholungssprache das besondere Zeichen #. So ist zum Beispiel das Wort ab#ab in W' enthalten. Beachte, dass die beiden wiederholten Teilworte "ab" nur aus {a,b}* stammen, das Zeichen # also tatsächlich eine eindeutige Markierung der Mitte des Gesamtwortes leistet.
Damit wird die Maschine zur Entscheidung von W' deutlich vereinfacht, da diese nicht zunächst die Mitte des Wortes erkennen muss. Für den Ablauf der restlichen Transitionen kannst du dich dann wie angegeben an der Maschine des letzten Übungsblattes orientieren!

Liebe Grüße,
Dominik