Beispiel 3.5

[willi.m]

Mein Vorschlag

[Fresh Prince]

Also ich hab das so angefangen : 13328

[DanyToss]

Meiner Meinung nach ist die Sprache von Fresh Prince falsch erkannt.

L = (a) (a , b)*

Wobei ich mir da noch keine 100% sicher bin. (Sehe im moment nur, dass man damit das Leerwort nicht erzeugen könnte)

[Bianconeri]

Irgendwie schaff ich es mit Willi.m's Grammatik nicht das Wort aaaabab zu bilden, was mit der ursprünglichen Grammatik aber schon geht. Also entweder ich bin einfach zu blöd eine Ableitung dafür zu finden oder die Grammatik stimmt nicht.

[willi.m]

S -> A -> aS -> aA -> aaS -> aaA -> aaaS -> aaaB -> aaaaBbB -> aaaa eps b B -> aaaab aBbB -> aaaaba eps bB -> aaaabab eps -> aaaabab

[Bianconeri]

Das gibts ja nicht ich versuch das schon zum 10. Mal glaub ich und bin nie darauf gekommen. Ich red mich mal darauf aus, dass ich schon zu müd bin ;)
Danke jedenfalls.

Kannst du mir vielleicht kurz schreiben, wie du auf die Grammatik gekommen bist. Ich find da nirgends was wie man von einer mehrdeutigen Grammatik auf eine eindeutige kommt. Mehrdeutige hab ich schon mehrere zusammengebracht zu der Sprache.

[schrankk]

Wie beschriftet man eigentlich Knoten? Geht man einfach von links nach rechts jede Stufe durch, oder abhängig von Ableitungsvorgang (Links-, Rechts-, Parallelableitung)?
/*edit: ist genau Ableitungsvorgang wichtig, aber ganze Beschriftungen allgemein sind irrelevant (kaum in welchem Buch findet man so was)*/

Und dritte Frage: wie bildet man eine eindeutige Grammatik aus einer mehrdeutigen?
/*edit: so wie ich es nun verstanden habe, gibt es keinen Algorithmus für alle Fälle*/

Wie sieht die durch in unserem Beispiel gegebene Grammatik erzeugte Sprache aus? Oder ist es irrelevant?

[schrankk]

meiner Meinung nach ist die erzeugte Sprache:
L(G) = \lbrace a^n b^m a^k | ( 0 \leq m \leq n ) \wedge ( k\geq 0 ) \rbrace

edit: und dann in diesem Zusammenhang die Menge von Produktionen P einer eindeutigen Grammatik sieht folgendermaßen aus:
\lbrace S \to ABA|\epsilon; A \to \underline{a}A|\epsilon; B \to \underline{a}B\underline{b}|\epsilon \rbrace

Was sagt ihr?

Ja, und gab es bereits bei irgendeinem Forum-Teilnehmer die Übung?? Könnte mir jemand mit diesem Beispiel weiterhelfen? :o

[Octavius]

@schrankk: ich denke du liegst falsch, denn wenn ich das richtig sehe wären auch andere wörter möglich
z.b.
S -> aSbS -> (erstes S wird eps. zweites S aSbS): abaSbs -> (beide S werden eps.): -> abab

wäre aber schon interessant welche Sprache eigentlich erzeugt wird, um dann von der Sprache vlt. auf die eindeutige Grammatik schließen zu können....ich probiers mal......(zu der Lösung ganz oben...ich verstehs noch nicht ^^...)

[schrankk]

so ein mist! du hast natürlich recht, danke!! :thumb:

trotzdem ich probiers noch morgen mal, wer weiß, wann die richtige gedanke plötzlich kommt?! wenn ichs doch nicht schaffe, zahlen sich meine bemühungen bei der prüfung sicher aus! :engel:

[Lukas.P]

wäre aber schon interessant welche Sprache eigentlich erzeugt wird, um dann von der Sprache vlt. auf die eindeutige Grammatik schließen zu können....ich probiers mal......(zu der Lösung ganz oben...ich verstehs noch nicht ^^...)

die sprache die erzeugt wird:

1) muss immer mit a beginnen
2) für jedes b in einer folge von b's müssen mindestens genausoviele a stehen (da S->aSbS die einzige möglichkeit ist um an b zu kommen, erstes S ersetzen gibt für jedes b auch ein weiteres a nach vorne)
3) kann auf a oder b enden

Meine Lösung (evtl einfacher zu verstehen)

S->aS|A|eps
A->aAbS|eps

[crashOverride]

Hi,

Wie wärs mit:

G' = < {S, A, B}, {a, b}, {S --> ABA | eps., A --> aA | eps., B --> abB | eps. }, {S} >

mfg

[Lukas.P]

damit kannst du kein "aabb" erzeugen

[schrankk]

S->aS|A|eps
A->aAbS|eps
ist aber mMn nicht eindeutig, da es verschiedene Linksableitungen gibt! Z.B. fürs Wort aab:
1) S->aS->aA->aaAbS->aabS->aabA->aab //zuerst S->A, dann A->Eps
2) S->aS->aA->aaAbS->aabS->aab //gleich S->Eps

und schon fürs Eps allein:
1) S->Eps
2) S->A->Eps

[crashOverride]

@Lukas

aber mit G (Angabe) kann ich ja auch kein aabb erzeugen!

mfg

[willi.m]

Ich bin drauf gekommen, weils im Buch steht...

Schau das Beispiel mit den imperativen Programmiersprachen

Anw => if expr then Anw
| if expr then Anw else Anw
| others

Anw=S / if expr then = a / else = b / others = epsilon|

[Octavius]

@Lukas

aber mit G (Angabe) kann ich ja auch kein aabb erzeugen!

mfg

leider doch...

S -> aSbS -> (erstes S wird aSbS): aaSbSbS -> (alle S werden eps.): aabb

[Lukas.P]

ist aber mMn nicht eindeutig, da es verschiedene Linksableitungen gibt! Z.B. fürs Wort aab:
1) S->aS->aA->aaAbS->aabS->aabA->aab //zuerst S->A, dann A->Eps
2) S->aS->aA->aaAbS->aabS->aab //gleich S->Eps

und schon fürs Eps allein:
1) S->Eps
2) S->A->Eps


hm hab ich wohl beim ausprobieren von mehreren lösungen übersehen, man kann theoretisch S-> eps weglassen und für jedes eps das man statt S haben möchte S->A->eps umformen

Weitere Mehrdeutigkeiten sind aber glaube ich nicht drin in der Grammatik