Informatiker Board | Druckvorschau: Mehrdeutige Grammatiken

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Mehrdeutige Grammatiken (http://www.informatikerboard.de/board/thread.php?threadid=259)

Geschrieben von Gisa am 16.09.2007 um 15:49:

Mehrdeutige Grammatiken

Hi Forum,

Ich habe folgendes Verständnisproblem bzgl. mehrdeutigen Grammatiken.

Konkret: Ist die folgende Grammatik mehrdeutig?

S-ABc
A->bc |df|epsilon
B->epsilon

Eine Grammatik ist doch mehrdeutig wenn ich zu einem Nichtterminal mehrere Produktionen habe wie oben bei A. Ist das so? Ist meine obige Grammatik mehrdeutig? Dann müsste die obige Grammatik mehrdeutig sein.
Welches wäre z.b. nicht mehrdeutig?

Danke und Grüße
Gisa

Geschrieben von Tobias am 16.09.2007 um 17:11:

Eine Grammatik ist mehrdeutig, wenn zu einem Wort w verschiedene Links- oder Rechtsableitungen existieren.

Geschrieben von Gisa am 16.09.2007 um 17:22:

also ist meine obige Grammatik nicht mehrdeutig, obwohl verschiedene Produktionen möglich sind?

P.S.: Eine Grammatik ist mehrdeutig, wenn es zu (mindestens) einem Wort aus der Sprache zwei unterschiedliche Ableitungsbäume gibt.

Geschrieben von Tobias am 17.09.2007 um 00:06:

Unsere beiden Definitionen der Mehrdeutigkeit ins äquivalent.

Mehrdeutigkeit hat nichts damit zu tun, dass man ein Terminalsymbol auf unterschiedliche Satzformen ableiten kann.

Es kommt nur darauf an, dass jedes Wort [latex]w[/latex]

mit $[latex]S \Rightarrow^\ast w[/latex]$ nur einen Ableitungsbaum, also z.B. nur eine eindeutige Linksableitung hat.

Geschrieben von Gisa am 17.09.2007 um 16:23:

Ok danke für deine Korrektur.
Ich dachte, dass es sich immer um Alternativen bzw. verschiedene Ableitungen handelt.

Gruß
Gisa