Gramatyka bezkontekstowa prawostronnie liniowa

0

Napisz gramatykę prawostronnie liniową opisującą następujący język nad alfabetem Σ = {0, 1}.

  1. zbiór ciągów zerojedynkowych, w których różnica liczby zer i jedynek jest parzysta.

Zrobiłem już kilka przykładów natomiast ten jeden sprawił mi problem, czy tu chodzi o to żeby po odjęciu tych zer od jedynek liczba pozostałych terminali musi być parzysta?
I miałby ktoś pomysł jak ta gramatyka mogła by wyglądać? }
:)

P.S
Gramatyka bezkontekstowa jest prawostronnie liniowa
jeśli każda produkcja w P ma postać:
• albo A → x
(czyli: żadnych nieterminali)
• albo A → xB
(czyli: tylko jeden nieterminal po prawej)

1

Masz przecież jasno napisane że masz generować ciągi gdzie różnica w liczbie zer i jedynek jest parzysta. Niech po prostu każda twoja produkcja generuje trzy razy więcej symboli jednego typu (bo 3-1=2) ;] Poza tym opis tej gramatyki jest trochę dziwny bo wcale nie mówi jak szeroką klasę ciągów masz generować więc choćby głupie:

S -> 0111A
A -> S | epsilon

będzie spełniało wymaganie, bo generujemy ciągi (0111)n a każdy z kawałków 0001 ma parzystą różnicę liczby zer i jedynek (zawsze wynosi ona 2 ;])

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