[Gramatyki] Gramatyki generujące język z liczb binarnych

[Hubu999]

Cześć,
Mam problem z zadaniem, mianowicie podać gramatykę generującą język:

-liczby binarne o parzystej liczbie zer
-liczby binarne o parzystej liczbie zer i nieparzystej liczbie jedynek
-liczby binarne o nieparzystej liczbie zer i nieparzystej liczbie jedynek

Z góry dziękuję za pomoc!

[leg14]

1)
\(\displaystyle{ S \rightarrow BS| \epsilon| aSaS; B \rightarrow \epsilon|bB}\)

2)
\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)

S na razie robi słowo o parzystej liczbie a i b i teraz dodajemy:
\(\displaystyle{ T \rightarrow aTa|bS|Sb}\)

trzecie dla Ciebie. Hint - możesz wykorzystać podpunkt drugi

[Hubu999]

Ok dzieki, więc z wykorzystaniem podpunktu 2 wnioskuję, że można będzie zrobić tak:

3.
\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)

i dodajemy
\(\displaystyle{ T \rightarrow bSa|aSb}\)

Czy to będzie poprawnie?

[leg14]

A jak wyprodukujesz
\(\displaystyle{ a aba}\)?

[Hubu999]

\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)
\(\displaystyle{ T \rightarrow bSa|aSb|aS|Sa|bS|Sb}\)

Wydaje mi się, że teraz byśmy mogli lecz dalej da się utworzyć słowo, w której jedna z liter będzie dalej parzysta... Nie wiem za bardzo jak można się przed tym zabezpieczyć.

[leg14]

Masz do dyspozycji gramatykę tworzącą słowo z liter \(\displaystyle{ a,b}\), wkotrym \(\displaystyle{ b}\) jest nie[arzyscie wiele, a \(\displaystyle{ a}\) parzyscie.
Niech \(\displaystyle{ S}\) bedzoe slowem, ktore ma nieparzystą liczbę \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\).
Wówczas zachodzi jeden z nastepujących warunków:
1) \(\displaystyle{ S = a T}\), gdzie \(\displaystyle{ T}\) ma parzyście wiele a i nieparzyście wiele b
2) \(\displaystyle{ S = T a}\), gdzie \(\displaystyle{ T}\) ma parzyście wiele a i nieparzyście wiele b
3) \(\displaystyle{ S = bS'b}\) gdzie \(\displaystyle{ S '}\) ma nieparzyscie wiele a i nieparzyscie wiele b

[Hubu999]

Powiem szczerze, że trochę się pogubiłem. Czy to rozwiązanie bedzie już lepsze?

\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)
\(\displaystyle{ T \rightarrow aSa|bSb|aT|Ta|bT|Tb}\)

Jesli nie to móglbyś mi powiedziec jakie będzie rozwiązanie?

[leg14]

przecież nadal możesz zrobić słowo o nieparzystej liczbie a.

\(\displaystyle{ <nieparzyste> \rightarrow b<nieparzyste>b|a<a -parzyste;b-nieparzyste>|<a -parzyste; b -nieparzyste>a}\)

[Hubu999]

\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)
\(\displaystyle{ S \rightarrow bSb | aT | Ta}\)
\(\displaystyle{ T \rightarrow aTa|bS|Sb}\)

Zależy mi żeby i liczba b i liczba a była nieparzysta, czy teraz jest lepiej?

[leg14]

nadal możesz wyprowadzić słowo \(\displaystyle{ bbb}\). Przecież Ci napsiałem wyżej jak to zrobić ...

(\(\displaystyle{ <a -parzyste;b-nieparzyste>}\) oznacza aksjomat gramatyki generującej wyrazy o parzystej liczbie a i nieparzystej liczbie b )

[Hubu999]

Rozumiem założenie ale nie potrafię do końca zrozumieć jak mam to zapisac w postaci symboli terminalnych i nieterminalnych.

Z tego co napisałeś:
\(\displaystyle{ <nieparzyste> \rightarrow b<nieparzyste>b|a<a -parzyste;b-nieparzyste>|<a -parzyste; b -nieparzyste>a}\)
Wnioskuję, że powinno wyglądać tak:
\(\displaystyle{ S \rightarrow bS|aT|Ta}\)

[leg14]

Nie możesz używać jednego symbolu terminalnego w dwóch kontekstach!

\(\displaystyle{ S \rightarrow bS|aT|Ta}\)

brakuje b po S

[Hubu999]

Czyli potrzebujemy nowego symbolu dla tego?

\(\displaystyle{ <nieparzyste> \rightarrow b<nieparzyste>b|a<a -parzyste;b-nieparzyste>|<a -parzyste; b -nieparzyste>a}\)
\(\displaystyle{ S \rightarrow bSb | aT | Ta}\)

Tylko, że w przykładzie wyżej S robi liczby parzyste.

( \(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\) )

Jakbym utworzył nowy symbol, powiedzmy X to rozwiąze to problem?

\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)
\(\displaystyle{ T \rightarrow aTa|bS|Sb}\)
\(\displaystyle{ X \rightarrow bXb|aT|Ta}\)

[leg14]

Jakbym utworzył nowy symbol, powiedzmy X to rozwiąze to problem?

tak

[Hubu999]

\(\displaystyle{ S \rightarrow \epsilon|aR|bW; R \rightarrow aS|bbR|baW;W \rightarrow bS|aaW|abR}\)
\(\displaystyle{ T \rightarrow aTa|bS|Sb}\)
\(\displaystyle{ X \rightarrow bXb|aT|Ta}\)

Czyli to rozwiązanie jest poprawne na generowanie nieparzystej ilości a oraz nieparzystej b?