Eine (ir) reguläre Sprache beweisen (Standardmethoden sind fehlgeschlagen)

Ich versuche gerade, eine reguläre Sprache zu beweisen (zur persönlichen Unterhaltung). Die Sprache ist:

Die Sprache, die alle ternären Zahlen enthält, die bei binärer Codierung sogar Bitparität aufweisen.

Derzeit habe ich einige verschiedene Ansätze ausprobiert, die mich zu keinem Erfolg geführt haben. Ich habe versucht, das Pump-Lemma (konnte nichts zum Pumpen finden), Myhill-Nerode (ähnlich) zu verwenden, und habe sogar die Anzahl der Zeichenfolgen jeder Länge gezählt, für die die Aussage wahr ist (meine Intuition ist, dass sie überprüft wird) ein probabilistisches Argument).

Gibt es andere Ansätze, die hier helfen könnten, oder gibt es Intuitionen, die hilfreich sein könnten? An diesem Punkt ist meine beste Vermutung, dass die Sprache nicht regelmäßig ist, aber ich scheine nicht in der Lage zu sein, eine Erklärung zu finden.

formal-languages regular-languages arithmetic James
quelle

Sind Sie sicher, dass es sich um eine nicht reguläre Sprache handelt? Betrachten Sie die Sprache auf so, dass die Zeichenfolgen eine gerade Anzahl von Einsen haben. Dies ist eine reguläre Sprache. Wenden Sie nun Homomorphismus auf diese Sprache an, um sie in eine Sprache zu konvertieren, die alle ternären Zeichenfolgen enthält. Der inverse Homomorphismus definiert ein Codierungsschema. Reguläre Sprachen werden unter Homomorphismus und inversem Homomorphismus geschlossen.

{0, 1}^{*}

$\{0,1\}^*$

Dib

@Dib Ich denke nicht, dass dies ein gültiger Ansatz ist, einfach weil ich nicht glaube, dass es einen solchen Homomorphismus gibt. Um zu erweitern, muss der Homomorphismus, so wie ich es verstehe, eine Funktion von Buchstaben des Alphabets bis zu Zeichenfolgen sein, also müssen 1, 0, 1101 A, B, AABA zugeordnet werden, wobei A und B Zeichenfolgen im Ternär sind. 1 Karten auf 1 im Ternär und 0 Karten auf 0 im Ternär, aber 1101 Karten auf 111 und nicht 1101 im Ternär.

James

Ich sollte hinzufügen, dass ich fast sicher bin, dass diese Sprache unregelmäßig ist. Dies liegt daran, dass ungefähr 50% der Zahlen vom Typ 10 * (dh Potenzen von 3) in Basis 3 eine gleichmäßige Parität aufweisen, wie wir vernünftigerweise erwarten könnten (empirisch habe ich bis zu überprüft ). Dies bedeutet, dass man vernünftigerweise erwarten könnte, auf etwas von dieser Form zu pumpen und auf etwas von der Form zu pumpen , um etwas wie . Dies wäre nicht in der Sprache mit einer Wahrscheinlichkeit von 0,5. Das Problem ist, dass ich das nicht genau beweisen kann - ich würde am Ende ein probabilistisches Argument haben.

3^{20000}

$3^{20000}$

3^{n}

$3^n$

3^{n + m}

$3^{n+m}$

James

Antworten:

Dies kann bewiesen werden, aber Sie benötigen einige nicht triviale Werkzeuge, um dies zu tun.

Beginnen Sie mit der Menge S = {0,3,5,6, ...} nicht negativer Ganzzahlen mit einer geraden Anzahl von Einsen in ihrer Basis-2-Erweiterung.

Es ist bekannt, dass dieses Set "2-automatisch" ist; das heißt, es gibt einen endlichen Automaten, der genau die Basis-2-Erweiterungen von Elementen von S akzeptiert. Außerdem ist bekannt, dass diese Menge letztendlich nicht periodisch ist (das heißt, es ist nicht wahr, dass es eine Periode P gibt, so dass Wenn nach einem Punkt C x> = C in S ist, ist x + P). (Wenn es so wäre, wäre das zugehörige Thue-Morse-Wort 01101001 ... letztendlich periodisch, aber es ist aus Thues Papier von 1912 bekannt, dass es keinen Block enthält, der dreimal hintereinander wiederholt wird.)

Als nächstes sei angenommen, dass S tatsächlich "3-automatisch" ist; Das heißt, es gibt einen Automaten, der genau die Basis-3-Erweiterungen von Elementen von S akzeptiert. Nach einem klassischen Satz von Cobham (Math. Systems. Theory 3 (1969) 186-192) würde dies bedeuten, dass S letztendlich periodisch ist wir haben schon gesehen, dass es nicht so ist.

Mehr über diese Ideen finden Sie in meinem Buch mit Allouche, "Automatic Sequences". Achtung, unser Beweis für Cobham ist etwas fehlerhaft, und eine korrigierte Version von Rigo finden Sie online hier: http://arxiv.org/abs/0907.0624 .

Jeffrey Shallit
quelle

Vielen Dank. Ich dachte, ich würde ein nicht triviales Werkzeug brauchen, aber ich habe (noch) nicht die Ausbildung, um herauszufinden, welches!

James

@ Jeffrey: Gute Verwendung von Cobham; Glauben Sie aus Neugier, dass ein Beweis dies erfordert - oder es irgendwie einbetten wird?

Michaël