Gramatyka jednoznaczna i niejednoznaczna

0

Witam, mam zadanie domowe o takiej treści:

Jaki język generuje gramatyka G = Σ, V, S, P , gdzie Σ = {0, 1},
V = {S}, zaś P = {S → 0S1, S → 0S, S → }? Wykaż, że jest ona niejednoznaczna. Zdefiniuj jednoznaczną gramatykę opisującą ten sam język. Udowodnij, że Twoja gramatyka jest jednoznaczna i że generuje ten sam język.

Jednak według mnie powyższa gramatyka jest jednoznaczna, bo dla każdego słowa można opracować tylko 1 drzewo "rozbioru".
Czyżby był błąd w treści zadania?
A jak Wy uważacie?
Pozdrawiam :)

2

Opracuj drzewo/a dla 0001.

0

Nie jest jednoznaczna, a może ktoś ma pomysł jak ją "podrasować" by była jednoznaczna ?

0

Gramatyka generuje język taki że mamy N zer oraz M jedynek i N>=M. Niejednoznaczność wprowadza tutaj epsilon i żeby się jej pozbyć musisz wprowadzić więcej nieterminali do gramatyki, tak żeby epsilon mógł wystąpić tylko w jakimś konkretnym miejscu. Coś w stylu:

S -> A | B | eps
A -> 01| 0A1 | 0B1
B -> 0 | 0B

1 użytkowników online, w tym zalogowanych: 0, gości: 1