Fachrat Informatik - Forum

Quoted

Original von vier
kommt irgendwer mit dem 2. Übungszettel klar?
http://www-thi.informatik.uni-hannover.d…en/uebung02.pdf

ich jedenfalls gar nicht.. kann mir wer helfen?

Es wäre ja nicht schlecht gewesen, wenn du geschrieben hättest, was dir an dem Zettel genau Probleme bereitet bzw. was du schon verstanden hast. Ohne diese Information kann man bestenfalls raten, wo das Problem liegt -- und das macht nicht wirklich Spaß ...

Ich nehme also mal an, daß dir eine Umformulierung der Aufgabenstellung mit ein paar Hinweisen hilft. Falls nicht, dann solltest du nochmal (etwas genauer!) nachfragen.


Aufgabe 1:
Gegeben sei eine beliebige Grammatik G vom Typ 3. Nun ist es zu zeigen, daß es zu dieser Grammatik G eine Grammatik G' vom selben Typ gibt, die die selbe Sprache wie G erzeugt. Zudem ist gefordert, daß G' in keiner Produktion auf der rechten Seite das Startsymbol von G' enthält.

Das selbe soll für Grammatiken vom Typ 1 und 2 gezeigt werden.

Hinweise:
- enthält G in keiner Produktion auf der rechten Seite das Startsymbol, dann gilt natürlich G = G'
- für alle anderen Fälle müssen die Produktion nach einem allgemeinen Verfahren (das beschrieben werden soll) so umgebaut werden, daß auf keiner rechten Seite mehr das Startsymbol vorkommt.


Aufgabe 2a:
Geben Sie eine Grammatik vom Typ 3 an, die alle Wörter über dem Alphabet {a, b} erzeugt, die eine gerade Anzahl des Symbols a enthalten.

Aufgabe 2b:
Geben Sie eine Grammatik vom Typ 1 an, die alle Wörter über dem Alphabet {a, b, c} erzeugt, bei denen die Anzahl der Symbole a, b und c gleich ist.


HTH,
Joachim

G' ist keine "abgeleitete" grammatik, sondern nur eine andere. man hätte sie auch XYZ nennen können. die namensgebung G' ist, wenn ich das richtig sehe, nur als hinweis darauf zu verstehen, dass die sprache L, die durch G erzeugt wird, diegleiche sei, die durch G' erzeugt wird, sprich, die grammatiken ähnlich sind.

G' steht hierbei nicht für die ableitung sondern für ein anderes G, also heisst soviel wie G1.

edit: mist, wenige sekunden zu spät...

Quoted

Original von vier
nur bei Aufgabe 1 versteh ich noch nicht so ganz den Kram mit G und G'... was genau ist G' wie hab ich mir das vorzustellen? G ist doch eine Grammatik.. wie kann ich die ableiten?!

Das Problem scheint wohl der Begriff "Ableitung" zu sein. Dazu ein Beispiel:

Gegeben sei die Grammatik G mit dem Startsymbol S und folgenden Produktionen:

S -> aT
T -> bT | a

Dann ist jede der folgenden Zeilen ein Ableitungsschritt:

S
aT
abT
abbT
abba

Die Grammtik G kann also zum Beispiel das Wort "abba" erzeugen. Man sagt auch: "abba" ist (aus dem Startsymbol) ableitbar.