zagadki i łamigłówki logiczne

13. Ok

G=<{a,b}, {S,R,L,P}, S, {
S->XabE
X->XLb
X->e
Lb->abL
La->aL
LE->E
E->e}

Tzn:
X na początku produkuje nowy początek i znacznik L.
L przesuwa się w prawo i jak trafi na b, to podnosi liczbę literek a przed tym b o 1.
Jak L dotrze do końca, to E je zjada.
Jak przy produkcji E przejdzie w e, to nikt nie zje L (ale to ponoć było dopuszczalne...).

EDIT:
W 15. i 16. chodzi o to, że N jest dane? Czy że 16. ma dawać tylko wyrazy o długości będącej liczbą pierwszą?

14. Brawo Sierrgiej



Nie N nie jest podane. W 15-tym gramatyka ma wytwarzać wszystkie słowa których długość jest liczbą złożoną czyli {aaaa,aaaaaa,aaaaaaaa,aaaaaaaaa,aaaaaaaaaa...}
W 16 dopełnienie do 15 czyli wszystkie wyrazy których długość nie jest liczbą złożoną:
{e,a,aa,aaa,aaaaa,aaaaaaa,aaaaaaaaaaa...}

A 15 i 16 się da?
Bo 16 generuje ciągi o długości danej liczbą pierwszą... i prostą metodą możemy generować liczby pierwsze!

15. się da
16. wg Wikipedii też się da
Podpowiedź: oba są kontekstowe.
Metoda generowania liczb pierwszych nie musi być prosta. Gramatyki kontekstowe to zwykle algorytmy niedeterministyczne, co oznacza, że np. jest tysiąc możliwości w każdym kroku do wykonania, kroków jest kolejny tysiąc, a tylko jedna ścieżka z miliona prowadzi do słowa nad alfabetem końcowym.

15.
G=<{a},{1,0,S,I,J,K,N,R},S,{
S->1aa0aaK
K->0aaK
K->IN
K->J
aJ->Ja
0J->J
1J->e
aI->Ia
0I->I0a
1I->1R
Ra->aR
R0->0R
RN->IN
RN->J
}>
i krótki komentarz:
najpierw tworzę element ciągu:1aa0aaK, 1aa0aa0aaK, 1aa0aa0aa0aaK...
później K zamieniam na IN lub J.
Wskaźniki:
I - idzie w lewo i po każdym zerze i jedynce dodaje literkę "a", a gdy dojdzie na sam początek (spotka jedynkę), to zamienia się we wskaźnik R.
J - idzie w lewo i usuwa wszystko co nie jest literką "a", a gdy dojdzie na sam początek, to usuwa samego siebie
R - po prostu idzie w prawo, a gdy dotrze na sam koniec (spotka N), to zamienia się na I lub J.
Tym sposobem otrzymamy wszystkie ciagi literek a dlugosci n*m, gdzie n>1 i m>1, czyli n*m to liczba złożona.