Den Algorithmus 4.28 und 4.29 hab ich nicht so ganz verstanden. Kann den jemand an folgendem Bsp anwenden ?

Meine CNF sieht so aus:

S -> S<a>| AB| A<b>
A -> A<a>| b
B -> <a>B| b
<a> -> a
<b> -> b

Wie bilde ich jetzt eine GNF?

boah, mal eben ne aufwendige aufgabe in den raum stellen,
aber ich muss ja üben [img]http://images.rapidforum.com/images/i25.gif[/img]:

S -> S<a> | AB | A<b>
A -> A<a> | b
B -> <a>B | b
<a> -> a
<b> -> b

erstmal umbenennen, (intelligent gewählt macht weniger arbeit)

A1 -> A1A4 | A2A3 | A2A5
A2 -> A2A4 | b
A3 -> A4A3 | b
A4 -> a
A5 -> b

algorithmus 4.28:

k=1

for j = 1 to 0 findet nicht statt…

A1 -> A1u gefunden (u = A4)

neues Symbol: B1 -> A4 | A4B1

A1 -> A1A4 gestrichen

neue Produktionen A1 -> A2A3B1 | A2A5B1

k=2

for j = 1 to 1 nix zu tun

A2 -> A2u gefunden (u = A4)

neues Symbol: B2 -> A4 | A4B2

A2 -> A2A4 gestrichen

neue Produktion A2 -> bB2

k=3-5 nix zu tun


nun folgende Produktionen

A1 -> A2A3 | A2A5 | A2A3B1 | A2A5B1
A2 -> b | bB2
A3 -> A4A3 | b
A4 -> a
A5 -> b

B1 -> A4 | A4B1
B2 -> A4 | A4B2


algorithmus 4.29:

k=5 nix zu tun

k=4

für j=3 was gefunden,
A3 -> A4A3 ersetzt durch A3 -> aA3

k=3 nix zu tun

k=2

für j=1 was gefunden

A1 -> A2A3 ersetzt durch A1 -> bA3 | bB2A3
A1 -> A2A5 ersetzt durch A1 -> bA5 | bB2A5
A1 -> A2A3B1 ersetzt durch A1 -> bA3B1 | bB2A3B1
A1 -> A2A5B1 ersetzt durch A1 -> bA5B1 | bB2A5B1


nun folgende Produktionen

A1 -> bA3 | bB2A3 | bA3 | bB2A3 | bA3B1 | bB2A3B1 | bA5B1 | bB2A5B1
A2 -> b | bB2
A3 -> aA3 | b
A4 -> a
A5 -> b

B1 -> A4 | A4B1
B2 -> A4 | A4B2

es werden noch B1 und B2 bearbeitet:
B1 -> A4 | A4B1 ersetzt B1 -> a | aB1
B2 -> A4 | A4B2 ersetzt B2 -> a | aB2


endgültige GNF:

A1 -> bA3 | bB2A3 | bA3 | bB2A3 | bA3B1 | bB2A3B1 | bA5B1 | bB2A5B1
A2 -> b | bB2
A3 -> aA3 | b
A4 -> a
A5 -> b

B1 -> a | aB1
B2 -> a | aB2

wenn auch noch reduktionswürdig [img]http://images.rapidforum.com/images/i24.gif[/img],
frohe fehlersuche

Mensch Slater!!! Bin stolz auf dich. Du hast es wohl echt drauf, was? [img]http://images.rapidforum.com/images/i15.gif[/img]

Oh mann, wenn ich das so sehe überleg ich mir nochmal ob ich mich morgen anmelde

Mensch Slater!!! Bin stolz auf dich. Du hast es wohl echt drauf, was? [img]http://images.rapidforum.com/images/i15.gif[/img]

genau so ist es [img]http://images.rapidforum.com/images/i15.gif[/img]

war das etwa ironisch gemeint?, vorsicht vorsicht [img]http://images.rapidforum.com/images/i18.gif[/img]

Wie kann ich aus folgender kontextfreier Sprache (10.1 ii.)): {a^n b^m b^n a^m / n, m element N ohne null}

eine GNF mit entsprechender Grammatik bilden? Zwar habe ich die Musterlösung gesehen aber die sagt mir nicht viel.

hmm da steht gar nicht der lösungsweg, dann hilft die lösung ja auch nicht viel,

kleiner trick: a^n b^m b^n a^m ist wohl gleich zu a^n b^n b^m a^m

und daraus sollte man sich schon mehr oder weniger effizient eine
grammatik ausdenken können, ähnlich zu a^n b^n:

S -> S'S''

S' -> aS'b | ab

S'' -> bS''a | ba

wenn man denn denkt das die richtig ist (denk ich jetzt mal [img]http://images.rapidforum.com/images/i25.gif[/img] ),
macht man daraus ne GNF, über die standard-verfahren sicherlich
aufwendig, hier kann man ein bisschen raten:

S -> S'S''

S' -> aS'B | aB

S'' -> bS''A | bA

A -> a

B-> b

fehlt nur noch die erste zeile mit S, baut man da ein kleines a
an den Anfang muss man das durch ein B (also b) ausgleichen, und
nur dann noch beachten, dass es nicht mindestens 3 a's und b's werden,
also noch eine zeite regel:

S -> aS'BS'' | aBS''

so siehts dann in der lösung aus…

Bitte ich bin total am verzweifeln…
Kann mir einer sagen woran man erkennen kann ob eine Sprache kontextfrei ist oder nicht, so dass ich weiss ob ich das Pumping- Lemma anwenden oder eine Greibach- Grammatik schreiben muss.
z.B. Aufgabenblatt 10 dort sind ja b.) und c.) kontextfrei, wie sehe ich das?
Danke im voraus..

Wenn es ein sicheres einfaches Verfahren gäbe, könnten wir uns die Mühe mit dem Pumping-Lemma sparen …

Bei (ii) muss man sich nur überlegen, dass b^m b^n = b^n b^m ist und dann hat man halt DUP und DUP rückwärts. Und das DUP kontextfrei ist, sollte man wissen.

Bei (iii) kann man schnell darauf kommen, dass es sich um eine CFG handeln muss, weil es keine "Verschachtelung" von Exponenten gibt. Wenn es Verschachtelungen für mehr als 2 Symbole gibt (a^n b^m c^n d^m, a^n b^n c^n usw.) ist die Sprache meist nicht kontextfrei. Siehe auch (i) der selben Aufgabe. Wenn man das ein wenig übt, sollte man schnell ein Gespür dafür bekommen, wo solche Grammatiken einzuordnen sind.