Niejednoznaczność w gramatykach bezkontekstowych

Jeśli gramatyka bezkontekstowa G ma więcej niż jedno drzewo pochodne dla danego łańcucha w ∈ L(G), to się nazywa ambiguous grammar. Istnieje wiele wyprowadzeń z prawej lub lewej strony dla jakiegoś ciągu wygenerowanego na podstawie tej gramatyki.

Problem

Sprawdź, czy gramatyka G z regułami produkcji -

X → X + X | X * X | X | za

jest niejednoznaczne, czy nie.

Rozwiązanie

Znajdźmy drzewo derywacyjne dla łańcucha „a + a * a”. Ma dwie skrajne lewe wyprowadzenia.

Derivation 1- X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse tree 1 -

Derivation 2- X → X * X → X + X * X → a + X * X → a + a * X → a + a * a

Parse tree 2 -

Ponieważ istnieją dwa drzewa parsowania dla pojedynczego łańcucha „a + a * a”, gramatyka G jest dwuznaczny.