[Informatik] Grammatik zu einer Sprache

[Lord of Alchemy]

Hallo,

ich habe da ein kleines Problem. Ich habe eine Sprache gegeben und soll dazu eine kontextsensitive Grammatik finden. Das Problem besteht nun darin die richtigen Produktionen zu finden. Meine Frage ist eigentlich ganz allgemein: Gibt es eine Vorgehensweise oder einen Trick, wie man die Produktionen einer Grammatik zu einer gegebenen Sprache bestimmen kann oder muss man das einfach "sehen"?
Ich habe da jetzt eine ganze Weile rumgerätselt, komme aber keinen Schritt weiter. Hat vielleicht jemand einen Tipp?

Danke schonmal im Voraus.

Mit freundlichen Grüßen,
Lord of Alchemy

[ojas]

Da stellt sich natürlich als erstes die Frage, wie du die Sprache gegeben hast, wenn nicht in Form einer Grammatik. Und kontextsensitiv ist sowieso ganz schlecht. Bist du sicher das nicht auch eine kontextfreie Grammatik ausreicht?

[Lord of Alchemy]

Also konkret geht es um die Sprache L = {ww|w € {0,1}*, w != epsilon} und dafür sollen wir eine kontextsensitive Grammatik gehen. Ich habe einfach keinen Plan wie man auf die Produktionen kommt bzw. wie man da ran geht. Ich habe im Internet was darüber gelesen, dass man Sprachen aufteilen kann und deren Grammatiken kombinieren kann. Für L1 = {w|w € {0,1}*, w != epsilon} hätte ich eine Grammatik. Kann ich die nun irgendwie mit sich selbst kombinieren?

[ojas]

Also konkret geht es um die Sprache L = {ww|w € {0,1}*, w != epsilon} ...

O.K., kontextfrei ist das nicht.


Für L1 = {w|w € {0,1}*, w != epsilon} hätte ich eine Grammatik.

Ist ja auch trivial: {S->0, S->1, S->SS}


Kann ich die nun irgendwie mit sich selbst kombinieren?

Es gibt wahrscheinlich Verfahren, wie man aus dem Grammatiken für zwei Sprachen einen Grammatik für die konkatenation der beiden Sprachen konstruieren kann. Die Konkatenation der beiden Sprachen ist aber {wv|w ∈ {0,1}*, w != ε, v ∈ {0,1}*, v != ε}. Insofern bringt dich das nicht zum Ziel. Ich schau mal ob ich eine Grammatik finde.

[Lord of Alchemy]

Es gibt wahrscheinlich Verfahren, wie man aus dem Grammatiken für zwei Sprachen einen Grammatik für die konkatenation der beiden Sprachen konstruieren kann. Die Konkatenation der beiden Sprachen ist aber {wv|w ∈ {0,1}*, w != ε, v ∈ {0,1}*, v != ε}. Insofern bringt dich das nicht zum Ziel. Ich schau mal ob ich eine Grammatik finde.

Wie würdest du denn da prinzipiell vorgehen, um eine Grammatik zu finden?

[ojas]

Als erstes würde ich prüfen ob eine einfachere Grammatik möglich ist. In deinem Fall ist das nicht möglich, weil kontextfrei Grammatiken zu Kellerautomaten äquivalent sind und dieser nach Abarbeitung des halben Wortes dieses in der falschen Reihenfolge im Keller stehen hat.

Dann würde ich wild herumprobieren. Habe ich gestern gemacht, hat nichts gebracht.

Dann würde ich im Intenet schauen.

[Lord of Alchemy]

Dann würde ich wild herumprobieren. Habe ich gestern gemacht, hat nichts gebracht.

Dann würde ich im Intenet schauen.

Ah ok, das beruhigt mich irgendwie^^

[ojas]

Eben im Internet gefunden (www.cs.tau.ac.il/~bchor/CM05/lecture13.pdf) (google: grammar ww (http://www.google.de/search?q=grammar+ww)):


S → S'Z
S' → aS'A
S' → bS'B
S' → ε
AZ → XZ
AX → XA
BX → XB
aX → aa
bX → ba
BZ → YZ
AY → YA
BY → YB
aY → ab
bY → bb

[Lord of Alchemy]

Super, dankeschön!
Mal gleich zu Gemüte führen :-)