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:

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 ? $n^k$

Rozważmy na przykład, że DFA akceptuje wszystkie liczby w postaci . Tym językiem będzie , dlatego też wyrażenia regularne $2^k$ $\{1,10,100,1000,...\}$ $10^*$ . Możemy utworzyć DFA w następujący sposób:

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

— Maha
źródło

Myślę, że masz tutaj

3

@Raphael, nie, to dla wielokrotności

n

$n$ ; chodzi o moce

n

$n$ .

— 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

10

Oto szybki i nieprzyzwoity dowód przy użyciu Pumping Lemma w tym języku $L$ składający się z $3^n$ 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 \in L$ być dowolnym ciągiem z $|w| \ge p$ (długość pompowania). Pumping Lemma, napisz $w = x y z$ z $|y| \ge 1, |xy| \le p$ i dla wszystkich $i \ge 0$ $xy^i z \in 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 liczbowo $w = 3^{k_0}$ dla niektórych $k_0 \in \mathbb{N}$ . Jednocześnie mamy numerycznie $w = z + 2^{|z|} y + 2^{|z|+|y|}x$ . Tak więc mamy

z + 2^{| z |} y + 2^{| z | + | y |} x = 3^{k_{0}}

$z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k_0}$

Teraz pompujmy $w$ dostać za wszystko $i \ge 0$

z + 2^{| z |} y (\sum_{j = 0}^{i - 1} (2^{| y |})^{j}) + 2^{| z | + i | y |} x = 3^{k_{i}},

$z + 2^{|z|} y \left( \sum_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k_i},$

gdzie $k_0 < k_1 < k_2 < \ldots$ . Uproszczenie, za które otrzymujemy $i \ge 1$

z + 2^{| z |} y (2^{i | y |} - 1) / (2^{| y |} - 1) + 2^{| z | + i | y |} x = 3^{k_{i}} .

$z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k_i}.$

Pozwolić $C = z - 2^{|z|} y / (2^{|y|}-1)$ . Potem będzie

3^{k_{i}} = 2^{| z | + i | y |} y / (2^{| y |} - 1) + 2^{| z | + i | y |} x + C .

$3^{k_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C.$

Teraz obserwuj to

3^{k_{i}} - 3^{k_{i - 1}} = (2^{| y |} - 1) (3^{k_{i - 1}} - C) .

$3^{k_i} - 3^{k_{i-1}} = (2^{|y|}-1)(3^{k_{i-1}} - C).$

Dlatego mamy $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$ Zauważ, że $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ . Tak więc z jednej strony wartość bezwzględna prawej strony rośnie co najmniej jako $3^{k_{i-1}}$ , która idzie w nieskończoność $i$ . Z drugiej strony $C(2^{|y|}-1)$ jest niezależny od $i$ i jest stały. To daje sprzeczność.

— Denis Pankratov
źródło

Czy mógłbyś trochę wyjaśnić, dlaczego?

| 2^{| y |} - 3^{k_{i} - k_{i - 1}} | \geq 1

$|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ jest prawdziwy? Pytam, ponieważ sama ta nierówność może być wykorzystana do osiągnięcia sprzeczności:

| 2^{| y |} - 3^{k_{i} - k_{i - 1}} | \geq 1

$|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ , mnożąc obie strony przez

3^{k_{i - 1}}

$3^{k_{i-1}}$ rozumiemy

| 3^{k_{i - 1}} 2^{| y |} - 3^{k_{i}} | \geq 3^{k_{i - 1}}

$|3^{k_{i-1}} 2^{|y|} - 3^{k_i}| \ge 3^{k_{i-1}}$ w ten sposób

| C (2^{| y |} - 1) | \geq 3^{k_{i - 1}}

$|C (2^{|y|} - 1)| \ge 3^{k_{i-1}}$ , co jest sprzecznością (z powodu podanego w dowodzie).

— Anton Trunov

1

Od

| y | \geq 1

$|y| \ge 1$ mamy to

2^{| y |}

$2^{|y|}$ jest parzysty i

3^{k_{i} - k_{i - 1}}

$3^{k_i - k_{i-1}}$ to 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ą

$\sum_{k=0}^{\infty}n_kz^k$ ,

gdzie $n_k$ jest liczbą słów długości $k$ w $L$ . Ta funkcja jest znana jako racjonalna, tzn. Iloraz $p(x)/q(x)$ wielomiany, dla każdego regularnego $L$ . W szczególności liczby $n_k$ spełniają liniową rekurencję $n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$ dla niektórych $p\in\mathbb{N}$ i $a_1,\dots,a_p\in\mathbb{Z}$ .

Z drugiej strony, ponieważ $\log_2(3)$ jest liczbą nieracjonalną w $(1,2)$ rozumiemy $n_k\in\{0,1\}$ dla wszystkich $k$ i sekwencja $(n_k)_{k\ge 1}$ nie jest okresowy. Daje to sprzeczność, ponieważ po co najwyżej $2^p$ kroki, wartości $n_k,\dots,n_{k+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, \dotsm, b-1\}$ . Tak więc, jak zauważyłeś, zestaw mocy $2$ 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 > 1$ mówi się, że są multiplikatywnie zależne, jeśli istnieje $r > 1$ takie, że oba $b$ i $c$ są mocami $r$ : na przykład $8$ i $32$ od tego czasu są multiplikatywnie zależne $8 = 2^3$ i $8 = 2^5$ .

Twierdzenie [Cobham] Let $b$ i $c$ dwie multiplikatywnie niezależne zasady. Jeśli zestaw jest $b$ - rozpoznawalny i $c$ - rozpoznawalne, to ostatecznie jest okresowe.

W szczególności pozwól $S$ być zbiorem mocy $3$ . Widzieliśmy, że tak jest $3$ -rozpoznawalny. Gdyby tak było $2$ - 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