Aufgabe 3.5

[thoreon]

Hallo,

Hat schon jemand einen Ansatz für die Produktionen der Aufgabe 3.5?
Die gerade Wortlänge ist nicht das Problem, eher die Sache mit 1. Hälfte anders, als 2. Hälfte.

Ich grüble schon eine Weile, aber weder mit sequentiellem Abarbeiten (also z.B. aaC, abD, baE etc.) noch mit Verschachtelungen (z.B. aCa, aDb etc.) komme ich irgendwie weiter.

Jemand eine Idee/einen Ansatz?

Danke und lg
Thomas

[hagstrombatman]

ich hab das gefühl, dass das eine FAngfrage ist, da die Aufgabenstellung eine kontextsensitive Grammatik erfordert.

[Lynx]

Fangfrage ist es definitiv keine. Trotzdem eindeutig das schwierigste Beispiel des Übungsblatts, ich empfehle, lieber die anderen Beispiele zuerst zu machen, bevor man dieses hier anfängt.

[hagstrombatman]

nope, es war keine, das stimmt, war ja nur ein Verdacht. haben das in der heutigen Übungsstunde durchgenommen.(habs mir nicht aufgeschrieben, alle angaben ohne Gewähr)
Die Lösung bedarf aber eines Tricks:
Ein Wort besteht aus zwei gleich langen Teilworten w1 und w2, die sich an einer stelle x unterscheiden(hinreichend). Vor x befinden sich m beliiebige Stellen, nach x n beliebige Stellen.
w1 w2
m x n | m x n
a b
m+n=|w1|-1=|w2|-1 =>m und n in der mitte kann man vertauschen, weil es ja beliebige Stellen sind, woraus sich dann Folgende Konstellation für ein Wort aus L ergibt:

m x m | n x n

d.heisst ein wort w aus L besteht aus zwei Teilworten, die sich an der Stelle x, genau in der Mitte quasi, unterscheiden.
Die Grammatik sieht dann ungefähr so aus:
G=<{S,A,B}, {a,b},{s=>AB, A=>aAa|aAb|bAa|bAb|a, B=>aBa|aBb|bBa|bBb|b},S>

Wie gesagt ich kann dafür nicht garantieren, wenns jemand mitgeschrieben hat, kann er evtl. nachbessern/besser Formulieren.

[etienne]

danke erst mal für die Erklärung, glaub allein wär ich da nie drauf kommen, nur eines fällt mir noch auf S geht über in
S=>AB|BA
dann sollten wirklich alle Kombinationen abgedeckt sein

grüße etienne

[Auron]

Also ich war heute zwar nicht in der Übung (bin in einer Mittwochübungsgruppe) aber bin auch auf eine gültige Lösung gekommen und zwar so:

Ich bin mit der Überlegung herangegangen, dass die erste Hälfte sich von der zweiten Hälfte an (mindestens) einer Stelle unterscheidet.

Ausgehend von der Annahme, dass sich diese an der ersten Stelle unterscheiden und dahinter komme was wolle und versucht dafür mal Produktionen zu finden:
a _ _ _ b _ _ _
A _ _ _ B _ _ _

Also A-> a, B-> b

Für die Stellen an denen egal ist welches Symbol steht definieren wir:
C -> a | b
d.h. Produktionen für:
AC..CBC..C

Da kommt also noch B-> CBC | b und A-> CAC | a (wenn man das ganze analog mit a und b vertauscht).

Gut nur gilt das auch wenn "die Stelle der Unterscheidung" nicht an der 1. Stelle ist?
Also
_ a _ _ _ b _ _ (A-> a, B-> b)
_ A _ _ _ B _ _ (A-> CAC, B-> CBC)
C A C _ C B C _ (B-> CBC)
C A C C C B C C

Also ja es gilt, da es mehr oder weniger das selbe Problem wie bei der 1. Stelle ist nur um eine Stelle nach rechts verschoben.

Warum funktioniert das mit dem "C-Auffüllen"?

Weil durch mehrfaches Ableiten von B über CBC werden die Mir-egal-Stellen hinter und vor der einen unterscheidbaren Stelle der zweiten Worthälfte aufgefüllt. Nur "stößt man in der ersten Worthälfte schon links an", dann kann es sein, dass nicht alle Mir-egal-Stellen hinter der unterscheidbaren Stelle (bis zum Beginn der zweiten Hälfte) schon mit Cs aufgefüllt ist.

Also in dem Fall (bei Parallelableitung sieht man das besonders gut) fehlen in der zweiten Hälfte hinter der unterscheidbaren Stelle genauso viele Cs wie in der ersten Hälfte und da die zweite Hälfte zum selben Zeitpunkt wie die erste Hälfte "an ihre linke Grenze (zur ersten Hälfte) stößt" rutschen genauso viele Cs in die erste Hälfte und füllen diese von rechts mit genau der Anzahl der fehlenden Cs.

So war mein Gedankengang dahin und meine Lösung daher:

P= {
S=> AB | BA
A=> CAC | a
B=> CBC | b
C=> a | b }

[DonCBA]

Hut ab! Hervorragend überlegt.

[Henry78]

So war mein Gedankengang dahin und meine Lösung daher:

P= {
S=> AB | BA
A=> CAC | a
B=> CBC | b
C=> a | b }

Wie stellst du denn sicher, dass |v|=2n? Bei den obigen Produktionen ist das nicht gesichert!

[edit:] blödsinn, passt scho!

[Henry78]

Aber für n=2 kannst du kein Wort generieren!

[Auron]

Aber für n=2 kannst du kein Wort generieren!

Du meinst ich kann kein Wort der Länge 4 produzieren?

S
AB
aCBC
aCbC
aaba oder abba oder bbba usw.

Die Lösung stimmt auch da.

[Henry78]

stimmt, irgendwie hab ich bei diesem beispiel gar nichts überrissen...