zagadki i łamigłówki logiczne

rozkosze łamania głowy
Teraz jest Pt wrz 10, 2010 8:54 am

Wszystkie czasy w strefie UTC + 1




Stwórz nowy wątek Odpowiedz w wątku  [ Posty: 31 ]  Przejdź na stronę Poprzednia strona  1, 2
Autor Wiadomość
 Temat: Re: Gramatyki
PostNapisane: Cz lut 12, 2009 3:34 pm 
Offline
pro SZEF
Avatar użytkownika

Dołączył: Cz wrz 02, 2004 11:56 pm
Posty: 1931
Lokalizacja: Warszawa
13. Ok :)

_________________
Deep in human unconsciousness is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic.


Góra
 Zobacz profil  
 
 Temat: Re: Gramatyki
PostNapisane: Pt lut 13, 2009 8:51 am 
Offline
starszy zagadkomaniak
Avatar użytkownika

Dołączył: Śr gru 13, 2006 10:11 am
Posty: 967
Lokalizacja: Gdynia
RFabianski napisał(a):
14. gramatyka nad alfabetem {a,b}, wytwarza ciąg : ab, abaab, abaabaaab, abaabaaabaaaab, abaabaaabaaaabaaaaab...


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ą?


Góra
 Zobacz profil  
 
 Temat: Re: Gramatyki
PostNapisane: So lut 14, 2009 7:24 pm 
Offline
zagadkomaniak
Avatar użytkownika

Dołączył: Cz wrz 06, 2007 8:17 pm
Posty: 50
Lokalizacja: Europa środkowa
14. Brawo Sierrgiej

siergiej napisał(a):
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ą?


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...}


Góra
 Zobacz profil  
 
 Temat: Re: Gramatyki
PostNapisane: N lut 15, 2009 10:27 pm 
Offline
starszy zagadkomaniak
Avatar użytkownika

Dołączył: Śr gru 13, 2006 10:11 am
Posty: 967
Lokalizacja: Gdynia
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!


Góra
 Zobacz profil  
 
 Temat: Re: Gramatyki
PostNapisane: Pn lut 16, 2009 8:55 am 
Offline
starszy zagadkomaniak
Avatar użytkownika

Dołączył: Śr sie 13, 2008 2:37 pm
Posty: 234
Lokalizacja: Grudziądz
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.

_________________
Wiedzieć, że się wie, co się wie i wiedzieć, że się nie wie, czego się nie wie - oto prawdziwa wiedza
Konfucjusz
Obrazek


Góra
 Zobacz profil  
 
 Temat: Re: Gramatyki
PostNapisane: So sty 30, 2010 10:56 am 
Offline
starszy zagadkomaniak
Avatar użytkownika

Dołączył: Pt lip 20, 2007 3:22 pm
Posty: 963
Lokalizacja: Kraków
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.

_________________
Obrazek


Góra
 Zobacz profil  
 
Wyświetl posty nie starsze niż:  Sortuj wg  
Stwórz nowy wątek Odpowiedz w wątku  [ Posty: 31 ]  Przejdź na stronę Poprzednia strona  1, 2

Wszystkie czasy w strefie UTC + 1


Kto przegląda forum

Użytkownicy przeglądający to forum: Brak zalogowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów

Szukaj:
Skocz do:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL