Links- Rechtsableitung

[leobasil]

Hi!
Ich glaub ich hab mir so ziemlich alles angeschaut, aber ich erinner mich, dass es bei den übungen _irgendwo_ _ irgendwas_ mit links- rechtsableitung gegeben hat. (und bei einer Linskableitung konnte man irgendwas anders feststellen als bei der rechtsableitung oder der Parallelableitung)
Kann mir schnell einer erklären was das war, und wie das gegangen ist ?

[12gauge]

Hi!
Ich glaub ich hab mir so ziemlich alles angeschaut, aber ich erinner mich, dass es bei den übungen _irgendwo_ _ irgendwas_ mit links- rechtsableitung gegeben hat. (und bei einer Linskableitung konnte man irgendwas anders feststellen als bei der rechtsableitung oder der Parallelableitung)
Kann mir schnell einer erklären was das war, und wie das gegangen ist ?
Linksableitung
Du leitest immer nur das Nonterminal ab, das am weitesten links steht

Rechtsableitung
Du leitest immer nur das Nonterminal ab, das am weistesten rechts steht

Parallelableitung
Du leitest alle Nonterminale in der Zeile auf einmal ab


Beweis für mehrdeutigkeit:

Es gibt zwei verschiedene Linksableitungen für das gleiche Wort

[oopster]

Hi!
Ich glaub ich hab mir so ziemlich alles angeschaut, aber ich erinner mich, dass es bei den übungen _irgendwo_ _ irgendwas_ mit links- rechtsableitung gegeben hat. (und bei einer Linskableitung konnte man irgendwas anders feststellen als bei der rechtsableitung oder der Parallelableitung)
Kann mir schnell einer erklären was das war, und wie das gegangen ist ?
Mit ner Linksableitung kannst du Feststellen ob eine Grammatik mehrdeutig ist, wenn du also zu einem Wort zwei unterschiedliche Linksableitungen hast, dann ist die Grammatik (also die Produktionen) mehrdeutig.
soweit ich mich auch erinnern kann gibt es zu jeder grammatik ne links und ne parallelableitung, rechts bin ich mir leider nicht sicher.

//edit oha da war wer schneller
lg

[keito]

Ich glaube, das ist so nicht richtig.
Es ist völlig äquivalent ob man eine Links- oder Rechtsableitung macht um Mehrdeutigkeit festzustellen. Es kann sein, dass beispielsweise 2 Rechtsableitungen existieren, aber nur eine Linksableitung.
Dann ist das Ganze genauso mehrdeutig.

Ansonsten: agree

[12gauge]

Ich glaube, das ist so nicht richtig.
Es ist völlig äquivalent ob man eine Links- oder Rechtsableitung macht um Mehrdeutigkeit festzustellen. Es kann sein, dass beispielsweise 2 Rechtsableitungen existieren, aber nur eine Linksableitung.
Dann ist das Ganze genauso mehrdeutig.

Ansonsten: agree
Das glaub ich eben nicht - im Skriptum steht eindeutig etwas von Linksableitung, die anderen werden nicht erwähnt:


Eine Grammatik heisst mehrdeutig, wenn es ein Wort mit mehreren Linksableitungen gibt.

[keito]

Aber wenn es zwei Rechtsableitungen gibt, dann kann das Teil doch nicht mehr deterministisch sein....

Aber bitte, ich nehme mal an du hast Recht. Thanx :thumb:

[Lord Binary]

Detailierte Diskussion -> siehe hier (http://www.informatik-forum.at/showthread.php?t=17833&highlight=Linksableitung)

[keito]

... und was sagt mir das? Ich hab' recht, und trotzdem ist es falsch. Na super. *grummel*