DFA za akceptację wszystkich ciągów binarnych mocy formy

9

Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .n

Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób:

wprowadź opis zdjęcia tutaj

Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób: wprowadź opis zdjęcia tutaj

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

Rozważmy na przykład, że DFA akceptuje wszystkie liczby w postaci . Tym językiem będzie , dlatego też wyrażenia regularne2k{1,10,100,1000,...}10 . Możemy utworzyć DFA w następujący sposób: wprowadź opis zdjęcia tutaj

Próbowałem utworzyć DFA dla 3ki podobne? Ale nie był w stanie tego zrobić. A może po prostu taki jest jego wzór2nbinarne odpowiedniki, które umożliwiły utworzenie DFA i nie możemy utworzyć DFA akceptującego wszystkie liczby binarne formularzank dla konkretnego n?

Maha
źródło
Myślę, że masz tutaj
3
@Raphael, nie, to dla wielokrotności n; chodzi o mocen.
DW
fyi mogą być inne „obok siebie”, które są funkcjami obliczeniowy przez DFAS takie jak podzielności uprawnienia itp na przykład funkcja Collatz (co wiąże się uprawnienia 3) może być obliczany za pomocą stanu ograniczonej przetwornika etc
vzn

Odpowiedzi:

10

Oto szybki i nieprzyzwoity dowód przy użyciu Pumping Lemma w tym języku L 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śćLjest regularny. PozwolićwL być dowolnym ciągiem z |w|p(długość pompowania). Pumping Lemma, napiszw=xyz z |y|1,|xy|p i dla wszystkich i0 xyizL. 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 k0N. Jednocześnie mamy numeryczniew=z+2|z|y+2|z|+|y|x. Tak więc mamy

z+2|z|y+2|z|+|y|x=3k0

Teraz pompujmy w dostać za wszystko i0

z+2|z|y(j=0i1(2|y|)j)+2|z|+i|y|x=3ki,

gdzie k0<k1<k2<. Uproszczenie, za które otrzymujemyi1

z+2|z|y(2i|y|1)/(2|y|1)+2|z|+i|y|x=3ki.

Pozwolić C=z2|z|y/(2|y|1). Potem będzie

3ki=2|z|+i|y|y/(2|y|1)+2|z|+i|y|x+C.

Teraz obserwuj to

3ki3ki1=(2|y|1)(3ki1C).

Dlatego mamy C(2|y|1)=3ki1(2|y|3kiki1). Zauważ, że |2|y|3kiki1|1. Tak więc z jednej strony wartość bezwzględna prawej strony rośnie co najmniej jako3ki1, która idzie w nieskończoność i. Z drugiej stronyC(2|y|1) jest niezależny od ii jest stały. To daje sprzeczność.

Denis Pankratov
źródło
Czy mógłbyś trochę wyjaśnić, dlaczego? |2|y|3kiki1|1jest prawdziwy? Pytam, ponieważ sama ta nierówność może być wykorzystana do osiągnięcia sprzeczności:|2|y|3kiki1|1, mnożąc obie strony przez 3ki1rozumiemy |3ki12|y|3ki|3ki1w ten sposób |C(2|y|1)|3ki1, co jest sprzecznością (z powodu podanego w dowodzie).
Anton Trunov
1
Od |y|1mamy to 2|y| jest parzysty i 3kiki1to jest dziwne. Ich różnica jest nieparzysta, dlatego co najmniej 1 w wartości bezwzględnej.
Denis Pankratov
10

Jednym ze sposobów przekonania się, że nie jest to możliwe (np.) Dla języka L uprawnień 3 w ekspansji binarnej bierze się pod uwagę funkcję generującą

k=0nkzk,

gdzie nk 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 pN i a1,,apZ.

Z drugiej strony, ponieważ log2(3) jest liczbą nieracjonalną w (1,2)rozumiemy nk{0,1} dla wszystkich ki sekwencja (nk)k1nie 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.

Klaus Draeger
źródło
8

Pełną odpowiedź na twoje pytanie zapewnia (trudny) wynik Cobhama [2].

Biorąc pod uwagę podstawę numeracji b, 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,,b1}. 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 bazy b,c>1mó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 cdwie multiplikatywnie niezależne zasady. Jeśli zestaw jestb- rozpoznawalny i c- rozpoznawalne, to ostatecznie jest okresowe.

W szczególności pozwól S 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 and p-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.

J.-E. Kołek
źródło
Czy mógłbyś naprawić referencje? Teraz oba są ponumerowane [1] i [1].
Anton Trunov