DFA zum Akzeptieren aller binären Zeichenfolgen der Formkraft von

Wir können DFA bilden, indem wir durch teilbare Binärzahlen akzeptieren .$n$

Zum Beispiel kann DFA, das durch 2 teilbare Binärzahlen akzeptiert, wie folgt gebildet werden:

In ähnlicher Weise kann DFA, das durch 3 teilbare Binärzahlen akzeptiert, wie folgt gebildet werden:

Wir können ein genau definiertes Verfahren befolgen, um diese Arten von DFAs zu bilden. Kann es jedoch ein genau definiertes Verfahren oder besser eine Logik zum Bilden von DFAs geben, die Zahlen der Form akzeptieren ?$n^k$

Betrachten wir zum Beispiel, dass DFA alle Zahlen der Form akzeptiert . Diese Sprache ist , hat also Regex . Wir können DFA wie folgt bilden: { 1 , 10 , 100 , 1000 , . . . } 10 $2^k$$\{1,10,100,1000,...\}$$10^*$

Ich habe versucht, DFA für und ähnliche zu bilden? War aber nicht dazu in der Lage. Oder war es nur das Muster von binären Äquivalenten, das es ermöglichte, DFA zu erstellen, und wir können nicht DFA bilden, indem wir alle Binärzahlen der Form für bestimmte akzeptieren ?$3^k$n k n$2^n$$n^k$$n$

Hier ist ein schneller und schmutziger Beweis mit Pumping Lemma, dass die Sprache die aus 3 n in Binärform besteht, nicht regulär ist (Hinweis: Sie ist regulär, wenn sie ternär dargestellt wird, daher ist die Darstellung wichtig).$L$$3^n$

Ich werde die Notation aus dem Wikipedia-Artikel zu Pumping Lemma verwenden . Nehmen Sie für den Widerspruch an, dass regulär ist. Sei w ∈ L eine beliebige Zeichenkette mit | w | ≥ p (Pumplänge). Schreiben Sie mit Pumping Lemma w = x y z mit | y | ≥ 1 , | x y | ≤ p und für alle i ≥ 0 x y i z ∈ L . Ich werde x , y schreiben$L$$w \in L$$|w| \ge p$$w = x y z$$|y| \ge 1, |xy| \le p$$i \ge 0$ $xy^i z \in L$$x$$y$und $z$ auch für numerische Werte entsprechender Teile und für ihre Länge in w . Numerisch haben wir w = 3 k 0 für einige k 0 ∈ N . Gleichzeitig haben wir numerisch w = z + 2 | z | y + 2 | z | + | y | x . So haben wir$|x|, |y|, |z|$$w$$w = 3^{k_0}$$k_0 \in \mathbb{N}$$w = z + 2^{|z|} y + 2^{|z|+|y|}x$

Lassen Sie uns nun pumpen , um für alle i ≥ $w$$i \ge 0$

wobei . Vereinfachend erhalten wir für i ≥ $k_0 < k_1 < k_2 < \ldots$$i \ge 1$

Sei . Dann haben wir$C = z - 2^{|z|} y / (2^{|y|}-1)$

Beobachten Sie das jetzt

Daher haben wir Beachten Sie, dass| 2 | y | -3 k i - k i - 1 | ≥1. Somit wächst einerseits der Absolutwert der rechten Seite um mindestens3$C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$$|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$ , das mitiins Unendliche geht. Andererseits istC(2 | y | -1)unabhängig voniund eine Konstante. Dies ergibt einen Widerspruch.$3^{k_{i-1}}$$i$$C(2^{|y|}-1)$$i$

Eine Möglichkeit zu sehen, dass dies für (z. B.) die Sprache von Potenzen von 3 bei der binären Expansion nicht möglich ist, besteht darin, die Erzeugungsfunktion zu berücksichtigen$L$$3$

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

wobei die Anzahl der Wörter der Länge k in L ist . Es ist bekannt, dass diese Funktion rational ist, dh ein Quotient p ( x ) / q ( $n_k$$k$$L$ Polynome, für jede reguläre L . Insbesondereerfüllendie Zahlen n k eine lineare Wiederholung n k + p + 1 = a 0 n k + ⋯ + a p n k + p für einige p ∈ $p(x)/q(x)$$L$$n_k$$n_{k+p+1}=a_0n_k+\dots+a_{p}n_{k+p}$$p\in\mathbb{N}$und .$a_1,\dots,a_p\in\mathbb{Z}$

Andererseits erhalten wir das , da eine irrationale Zahl in ( 1 , 2 ) ist$\log_2(3)$$(1,2)$ für alle k ist und die Folge ( n k ) k ≥ 1 nicht periodisch ist . Dies ergibt einen Widerspruch, da nach höchstens 2 p Schritten die Werte von n k , … , n k + $n_k\in\{0,1\}$$k$$(n_k)_{k\ge 1}$$2^p$$n_k,\dots,n_{k+p}$ wiederholen müssen, und die Wiederholung würde dann zu periodischem Verhalten führen.

Eine vollständige Antwort auf Ihre Frage liefert ein (schwieriges) Ergebnis von Cobham [2].

Bei einer gegebenen Zahlenbasis wird eine Menge natürlicher Zahlen als b- erkennbar bezeichnet, wenn die Darstellungen in Basis b ihrer Elemente eine reguläre Sprache im Alphabet { 0 , $b$$b$$b$ . Wie Sie gesehen haben, ist die Potenzmenge von 2 also 2- erkennbar, da sie durch die reguläre Menge 10 ∗ im Alphabet { 0 , 1 } dargestellt wird . In ähnlicher Weise die Menge der Kräfte von 4 ist$\{0, 1, \dotsm, b-1\}$$2$$2$$10^*$$\{0,1\}$$4$$2$- erkennbar - es entspricht der regulären Menge - und die Menge der Potenzen von 3 ist 3 - erkennbar - es entspricht der regulären Menge 10 ∗ über dem Alphabet { 0 , 1 , 2 } .$1(00)^*$$3$$3$$10^*$$\{0,1,2\}$

Eine Menge natürlicher Zahlen gilt letztendlich als periodisch, wenn es sich um eine endliche Vereinigung arithmetischer Progressionen handelt.

Zwei Basen gelten als multiplikativ abhängig, wenn es ein r > 1 gibt, so dass sowohl b als auch c Potenzen von r sind : Zum Beispiel sind 8 und 32 multiplikativ abhängig, da 8 = 2 3 und 8 = 2 5 .$b, c > 1$$r > 1$$b$$c$$r$$8$$32$$8 = 2^3$$8 = 2^5$

Satz [Cobham] Sei und c zwei multiplikativ unabhängige Basen. Wenn eine Menge b- erkennbar und c- erkennbar ist, ist sie letztendlich periodisch.$b$$c$$b$$c$

Insbesondere sei die Potenzmenge von 3 . Wir haben gesehen, dass es 3- erkennbar ist. Wenn es auch 2- erkennbar wäre, wäre es letztendlich periodisch, was bei S sicherlich nicht der Fall ist .$S$$3$$3$$2$$S$

Cobhams Theorem führte zu vielen überraschenden Verallgemeinerungen und Entwicklungen. Ich empfehle die Umfrage [1], wenn Sie interessiert sind.

[1] V. Bruyère, G. Hänsel, C. Michaux, R. Villemaire, Logik und erkennbare Mengen von ganzen Zahlen, Journées Montoises (Mons, 1992). Stier. Belg. Mathematik. Soc. Simon Stevin 1 (1994), Nr. 2, 191-238. Korrektur in Nr. 4, 577.$p$

[2] A. Cobham, Uniform Tag Sequences, Math. Systems Theory 6 (1972), 164-192.