Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .
Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób:
Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób:
Możemy zastosować dobrze zdefiniowaną procedurę, aby utworzyć tego rodzaju DFA. Czy jednak może istnieć jakaś dobrze zdefiniowana procedura lub lepiej powiedzieć logikę tworzenia DFA przyjmujących liczby postaci ?
Rozważmy na przykład, że DFA akceptuje wszystkie liczby w postaci . Tym językiem będzie , dlatego też wyrażenia regularne . Możemy utworzyć DFA w następujący sposób:
Próbowałem utworzyć DFA dla i podobne? Ale nie był w stanie tego zrobić. A może po prostu taki jest jego wzórbinarne odpowiedniki, które umożliwiły utworzenie DFA i nie możemy utworzyć DFA akceptującego wszystkie liczby binarne formularza dla konkretnego ?
Odpowiedzi:
Oto szybki i nieprzyzwoity dowód przy użyciu Pumping Lemma w tym językuL składający się z 3n binarny nie jest regularny (uwaga: jest regularny, jeśli jest reprezentowany w trójce, więc reprezentacja jest ważna).
Użyję zapisu z artykułu z Wikipedii dotyczącego Pumping Lemma . Załóżmy, że to sprzecznośćL jest regularny. Pozwolićw∈L być dowolnym ciągiem z |w|≥p (długość pompowania). Pumping Lemma, napiszw=xyz z |y|≥1,|xy|≤p i dla wszystkich i≥0 xyiz∈L . Napiszęx , y , i z również dla wartości liczbowych odpowiednich części, oraz |x|,|y|,|z| za ich długości w w . Mamy liczbowow=3k0 dla niektórych k0∈N . Jednocześnie mamy numeryczniew=z+2|z|y+2|z|+|y|x . Tak więc mamy
Teraz pompujmyw dostać za wszystko i≥0
gdziek0<k1<k2<… . Uproszczenie, za które otrzymujemyi≥1
PozwolićC=z−2|z|y/(2|y|−1) . Potem będzie
Teraz obserwuj to
Dlatego mamyC(2|y|−1)=3ki−1(2|y|−3ki−ki−1). Zauważ, że |2|y|−3ki−ki−1|≥1 . Tak więc z jednej strony wartość bezwzględna prawej strony rośnie co najmniej jako3ki−1 , która idzie w nieskończoność i . Z drugiej stronyC(2|y|−1) jest niezależny od i i jest stały. To daje sprzeczność.
źródło
Jednym ze sposobów przekonania się, że nie jest to możliwe (np.) Dla językaL uprawnień 3 w ekspansji binarnej bierze się pod uwagę funkcję generującą
gdzienk jest liczbą słów długości k w L . Ta funkcja jest znana jako racjonalna, tzn. Ilorazp(x)/q(x) wielomiany, dla każdego regularnego L . W szczególności liczbynk spełniają liniową rekurencję nk+p+1=a0nk+⋯+apnk+p dla niektórych p∈N i a1,…,ap∈Z .
Z drugiej strony, ponieważlog2(3) jest liczbą nieracjonalną w (1,2) rozumiemy nk∈{0,1} dla wszystkich k i sekwencja (nk)k≥1 nie jest okresowy. Daje to sprzeczność, ponieważ po co najwyżej2p kroki, wartości nk,…,nk+p muszą się powtarzać, a nawrót doprowadziłby do okresowego zachowania.
źródło
Pełną odpowiedź na twoje pytanie zapewnia (trudny) wynik Cobhama [2].
Biorąc pod uwagę podstawę numeracjib , mówi się, że zbiór liczb naturalnych b - rozpoznawalne, jeśli reprezentacje w bazie b jego elementów tworzy regularny język na alfabecie {0,1,⋯,b−1} . Tak więc, jak zauważyłeś, zestaw mocy2 jest 2 - rozpoznawalny, ponieważ jest reprezentowany przez zwykły zestaw 10∗ na alfabecie {0,1} . Podobnie zestaw uprawnień4 jest 2 - rozpoznawalny - odpowiada zwykłemu zestawowi 1(00)∗ - i zestaw uprawnień 3 jest 3 - rozpoznawalny - odpowiada zwykłemu zestawowi 10∗ nad alfabetem {0,1,2} .
Mówi się, że zbiór liczb naturalnych ma charakter okresowy, jeśli jest skończonym połączeniem postępów arytmetycznych.
Dwie bazyb,c>1 mówi się, że są multiplikatywnie zależne, jeśli istniejer>1 takie, że oba b i c są mocami r : na przykład 8 i 32 od tego czasu są multiplikatywnie zależne 8=23 i 8=25 .
Twierdzenie [Cobham] Letb i c dwie multiplikatywnie niezależne zasady. Jeśli zestaw jestb - rozpoznawalny i c - rozpoznawalne, to ostatecznie jest okresowe.
W szczególności pozwólS być zbiorem mocy 3 . Widzieliśmy, że tak jest3 -rozpoznawalny. Gdyby tak było2 - rozpoznawalne, byłoby to ostatecznie okresowe, co z pewnością nie jest przypadkiem S .
Twierdzenie Cobhama doprowadziło do wielu zaskakujących uogólnień i zmian. Polecam ankietę [1], jeśli jesteś zainteresowany.
[1] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic andp -poznawalne zestawy liczb całkowitych, Journées Montoises (Mons, 1992). Byk. Belg. Matematyka Soc. Simon Stevin 1 (1994), no. 2, 191--238. Korekta nr 4, 577.
[2] A. Cobham, Jednolite sekwencje znaczników, Math. Systems Theory 6 (1972), 164--192.
źródło