Aufgabe 11.3

[Chrisor]

Erkennt jemand von euch, was die Grammatik für eine Sprache beschreibt?? Ich erkenne da nicht wirklich ein System, es können mehr oder weniger wahhlos Wörter zusammengesetzt werde, nur können nicht mehr als 2 b's hintereinander vorkommen..

[SLS]

Die Sprache erkenne ich auch nicht (vor allem wegen dieses "Y --> aS", das die Rekursion zu kompliziert für mich macht). Ich glaube aber, man muss nicht die Sprache unbedingt kennen, um die Aufgabe zu lösen. (Deswegen ist da der zweite Aufgabenteil da - wenn es für eine allgemeine rechtslineare Grammatik möglich ist (und davon kennt man die Sprache nicht), dann ist es insbesondere für unsere möglich ).
Abstrahiere also von der Komplexität der gegebenen Grammatik. Abstrahiere auch von der Sprache, die diese erzeugt, und konzentriere dich auf die Aufgabe. Dann wird es relativ leicht, und man hatt in einem Schritt die Lösung für beide Teilaufgaben
Hoffentlich, hilft das weiter

[ryo]

ich hatte da ne idee, bei der ich gedacht habe, dass die zu einfach [=falsch] sei, aber wenn du jetzt auch meist, dass das sehr einfach ist... poste ich das halt mal mit todesverachtung, auch auf die gefahr hin, falsch zu liegen

stimmt das da in etwa:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

bei 1. gibt es ja nur eine möglichkeit für den abbruch, nämlich Y-> b
wenn man nun z.b. anstatt y-> b y-> z verlinkt und dann z -> b | S gehen lässt, hat man L(g)+ erreicht (ok, so komliziert mit zusätzlichem zustand braucht man wohl garnicht)
um L(g)* zu erhalten, muss man noch bei S -> epsilon hinzufügen, damit das Wort auch die Länge 0 /leeres Wort sein kann.


bei der 2. müsste man es nur entsprechend für allgemeine Sprachen formulieren, wobei man bei der 1 ja dann schon nen Großteil der Denkarbeit hinter sich hat

[Snoop]

ich hatte da ne idee, bei der ich gedacht habe, dass die zu einfach [=falsch] sei, aber wenn du jetzt auch meist, dass das sehr einfach ist... poste ich das halt mal mit todesverachtung, auch auf die gefahr hin, falsch zu liegen

stimmt das da in etwa:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

bei 1. gibt es ja nur eine möglichkeit für den abbruch, nämlich Y-> b
wenn man nun z.b. anstatt y-> b y-> z verlinkt und dann z -> b | S gehen lässt, hat man L(g)+ erreicht (ok, so komliziert mit zusätzlichem zustand braucht man wohl garnicht)
um L(g)* zu erhalten, muss man noch bei S -> epsilon hinzufügen, damit das Wort auch die Länge 0 /leeres Wort sein kann.


bei der 2. müsste man es nur entsprechend für allgemeine Sprachen formulieren, wobei man bei der 1 ja dann schon nen Großteil der Denkarbeit hinter sich hat

Ich habe eine ähnliche Lösung, allerdings darf man nicht mehr nach S zurück (z -> b | S), da man in S ja jederzeit per epsilon abbrechen könnte und so unvollständige Wörter erzeugen kann..
Habe das in etwa so:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Produktion von S ganz normal, nur S -> e hinzugefügt
Y -> bZ|b hinzugefügt (das Y-> b ersetzt)
Z ist wiederum die ursprüngliche Produktion von S.

Das für die 2. allgemein zu formulieren ist allerdings nicht ganz trivial.. und das ganze noch formal auszudrücken erst recht nicht

[sockenjodler]

so müsste es doch auch gehen. dann muss man das S nicht nochmals in Z schreiben;
P={
S'->|S
S->aS|baS|aY
Y->abY|baY|aS|bS'
}

[Ruben]

Hab mir am Anfang zuerst die Sprache überlegt, hat allerdings nicht geholfen. Trotzdem, hier ist sie:
{a,ba}*{a}{ab,ba}*({a}{a,ba}*{a}{ab,ba}*)*b

[mixIT]

Ruben das hatte ich auch, aber wie bildest du mit dieser Sprache z.B. "aab"? :p
Also ich denke, dass man L(G)* aufgrund der Rekursion("aS") nicht in der Form darstellen kann.