DFA zum Akzeptieren aller binären Zeichenfolgen der Formkraft von

9

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:

Geben Sie hier die Bildbeschreibung ein

In ähnlicher Weise kann DFA, das durch 3 teilbare Binärzahlen akzeptiert, wie folgt gebildet werden: Geben Sie hier die Bildbeschreibung ein

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

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 2k{1,10,100,1000,...}10Geben Sie hier die Bildbeschreibung ein

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 ?3kn k n2nnkn

Maha
quelle
Ich denke, dass Sie die Antwort hier haben
3
@ Raphael, nein, das ist für Vielfache von ; Hier geht es um Potenzen von . nnn
DW
Zu Ihrer Information kann es andere "nahe" Funktionen geben, die durch DFAs berechenbar sind, wie z. B. die Teilbarkeit von Potenzen usw. Zum Beispiel kann die Collatz-Funktion (die Potenzen von 3 beinhaltet) von einem Wandler mit endlichen
Zuständen

Antworten:

10

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).L3n

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 schreibenLwL|w|pw=xyz|y|1,|xy|pi0 xyizLxyund 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 0N . Gleichzeitig haben wir numerisch w = z + 2 | z | y + 2 | z | + | y | x . So haben wir|x|,|y|,|z|ww=3k0k0Nw=z+2|z|y+2|z|+|y|x

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

Lassen Sie uns nun pumpen , um für alle i 0 zu erhaltenwi0

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

wobei . Vereinfachend erhalten wir für i 1k0<k1<k2<i1

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

Sei . Dann haben wirC=z2|z|y/(2|y|1)

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

Beobachten Sie das jetzt

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

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 kC(2|y|1)=3ki1(2|y|3kiki1).|2|y|3kiki1|1 , das mitiins Unendliche geht. Andererseits istC(2 | y | -1)unabhängig voniund eine Konstante. Dies ergibt einen Widerspruch.3ki1iC(2|y|1)i

Denis Pankratov
quelle
Könnten Sie etwas näher erläutern, warum ist wahr? Ich frage, weil diese Ungleichung allein dazu verwendet werden könnte, einen Widerspruch zu erreichen: | 2 | y | - 3 k i - k i - 1 | 1 , multipliziert man beide Seiten mit 3 k i - 1 , so erhält man | 3 k i - 12 | y | - 3 k|2|y|3kiki1|1|2|y|3kiki1|13ki1 , also| C(2 | y | -1)| 3 k i - 1 , was ein Widerspruch ist (aus dem in Ihrem Beweis angegebenen Grund). |3ki12|y|3ki|3ki1|C(2|y|1)|3ki1
Anton Trunov
1
Da , wir haben diese 2 | y | ist gerade und 3 k i - k i - 1 ist ungerade. Ihre Differenz ist ungerade, daher mindestens 1 im absoluten Wert. |y|12|y|3kiki1
Denis Pankratov
10

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ücksichtigenL3

,k=0nkzk

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 ( xnkkL 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 N.p(x)/q(x)Lnknk+p+1=a0nk++apnk+ppNund .a1,,apZ

Andererseits erhalten wir das , da eine irrationale Zahl in ( 1 , 2 ) istlog2(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 + p sindnk{0,1}k(nk)k12pnk,,nk+p wiederholen müssen, und die Wiederholung würde dann zu periodischem Verhalten führen.

Klaus Draeger
quelle
8

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 , 1 bildenbbb . 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 2{0,1,,b1}2210{0,1}42- 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)3310{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>1r>1bcr8328=238=25

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

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

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.

J.-E. Stift
quelle
Könnten Sie bitte die Referenzen korrigieren? Jetzt sind beide nummeriert [1] & [1].
Anton Trunov