Matematyka.pl

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!

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

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?

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

\(\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ć.

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

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?

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}\)

\(\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?

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 )

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}\)

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

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

brakuje b po S

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}\)

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

tak

\(\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?