Sprache der Werte einer affinen Funktion

10

Schreiben Sie für die Dezimalerweiterung von (ohne führenden ). Sei und ganze Zahlen mit . Betrachten Sie die Sprache der Dezimalerweiterungen der Vielfachen Plus-Konstante: $\bar n$ $n$ 0 $a$ $b$ $a > 0$ $a$

M = {\bar{a x + b} ∣ x \in N}

$M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \}$

Ist regelmäßig? kontextfrei? $M$

(Kontrast zur Sprache des Graphen einer affinen Funktion )

_{Ich denke, dies wäre eine gute Hausaufgabenfrage. Antworten, die mit ein oder zwei Hinweisen beginnen und nicht nur erklären, wie die Frage zu lösen ist, sondern auch zu entscheiden, welche Techniken verwendet werden sollen, wären willkommen.}

formal-languages context-free regular-languages integers Gilles 'SO - hör auf böse zu sein'
quelle

Gerade jetzt merke ich, dass ich einen bestimmten Fall beantwortet habe, der der Idee von @vonbrand folgt. DFA, das Dezimaldarstellungen einer natürlichen Zahl akzeptiert, die durch 43 teilbar ist

Hendrik

9

Sehr einfach: Angenommen, Zahlen werden dezimal geschrieben (andere Basen werden durch eine triviale Modifikation behandelt). Bauen Sie einen DFA, mit Zuständen 0, 1, ..., . Der Startzustand ist 0, und vom Zustand bei der Eingabe geht die Ziffer in den Zustand . Der akzeptierende Status ist (muss möglicherweise angepasst werden, wenn ). $a$ $a - 1$ $q$ $d$ $(10 q + d) \bmod a$ $b \bmod a$ $b > a$

vonbrand
quelle

1

Sehr schön - viel besser als meins!

David Lewis

8

Es ist regelmäßig. Lassen Sie uns zunächst in Binärform arbeiten, die auf jede Basis> 1 verallgemeinert wird. Sei die fragliche Sprache. Für a = 1, b = 0 erhalten wir $M_{a,b}$

$M_{1,0} = \{1, 10, 11, 100, 101, ...\}$

Das sind alle Zeichenfolgen über ohne führende Nullen, was regulär ist (konstruiere einen regulären Ausdruck dafür). $\{0,1\}$

Nun erhalten wir für jedes mit b noch 0 von indem wir numerisch mit a multiplizieren, dh die Transformation für jede Zeichenfolge von ausführen . Dies kann bitweise durch eine Folge von Verschiebungen und Additionen von , die von den Bits der festen Zeichenfolge abhängen . Die zwei Transformationen, die wir brauchen, sind: $a$ $M_{a,0}$ $M_{1,0}$ $\bar x \rightarrow \overline {ax}$ $M_{a,0}$ $x$ $\bar a$

$\bar x \rightarrow \overline {2x}$ , also $\bar x \rightarrow \bar x0$

und

$\bar x \rightarrow \overline {2x+x}$

Durch Verketten einer 0 auf der rechten Seite bleibt die Regelmäßigkeit deutlich erhalten. Wir müssen also nur beweisen, dass die zweite Operation die Regelmäßigkeit bewahrt. Der Weg dazu ist mit einem Finite-State-Wandler, der von rechts nach links an . Das ist der schwierigste Schritt. Ich schlage vor, dies mit einem Pseudocode-Programm und einem endlichen Hilfsspeicher (wie einigen Bitvariablen) zu tun, anstatt Zustände zu verwenden. Solange der Speicher über alle Eingänge hinweg eine feste Größe hat und Sie streng von rechts nach links scannen, handelt es sich um eine endliche Zustandsübertragung und behält die Regelmäßigkeit bei. $\bar x$

Um schließlich von , müssen wir jedem String numerisch hinzufügen , aber dies geschieht mit einem ähnlichen Wandler der von der festen Zahl b abhängt. $M_{a,b}$ $M_{a,0}$ $b$ $T_b$

Um dasselbe in jeder Basis zu tun, zeigen Sie zusätzlich, wie eine Multiplikation mit einer einzelnen Ziffer in dieser Basis unter Verwendung eines Wandlers , der von d abhängt. Damit können wir mit mehrstelligen Zahlen multiplizieren und bleiben dennoch in den regulären Sprachen. Oder wir können dies verfeinern, indem wir sagen, dass die Multiplikation mit nur eine wiederholte Addition ist. $d$ $S_d$ $d$

Sie wollten nur Hinweise. Jeder dieser Schritte hängt von einem ziemlich komplexen Theorem / einer ziemlich komplexen Technik ab. Daher ist es die zusätzliche Arbeit, zu beweisen, dass diese einen vollständigen Beweis erhalten.

David Lewis
quelle

Ihr FA erhält als Eingabe, daher sehe ich nicht, wie das, was Sie schreiben, zeigt, dass die vorliegende Sprache regulär ist. Beachten Sie, dass nicht jedes Programm, das endlichen Speicher verwendet, FA entspricht: Es ist wichtig, dass nur einmal und von links nach rechts über die Eingabe gefahren werden kann, wobei jedes Eingabesymbol genau einmal berücksichtigt wird.

\bar{x}

$\bar{x}$

Raphael

@ Raphael Sie können von rechts nach links gehen, wenn Sie möchten, was zählt, ist konsequent zu sein. Ich kann keinen Fehler in Davids Beweisskizze finden; Das Aufrufen von Wandlern ist etwas weniger elementar als ich es mir vorgestellt habe, aber es sieht gültig aus.

Gilles 'SO - hör auf böse zu sein'

@ Gilles: Zunächst erklärt er nicht, wie man die Multiplikation mit verschachtelt und in einem Durchgang zum Ergebnis addiert . er reduziert sogar die Multiplikation um auf "eine Folge von Verschiebungen und Additionen von ". Jede einzelne Verschiebung und Addition ist in Ordnung, aber wie wird die Sequenz ausgeführt? Zweitens, und was noch wichtiger ist, zeigt er, wie man einen Wandler baut, der berechnet ; das gibt Ihnen nicht sofort eine FA, die akzeptiert . Zum Beispiel ist das Multiplizieren von Zahlen einfach, das Factoring jedoch (angeblich) nicht. Sie benötigen also mindestens ein zusätzliches Argument.

a

$a$

b

$b$

a

$a$

x

$x$

\bar{x} \mapsto \bar{a x + b}

$\bar{x} \mapsto \overline{ax + b}$

M

$M$

Raphael

Ich baue keine FSA. Ich beginne mit einer Menge, die leicht als regulär dargestellt werden kann ( ), und transformiere dann alle darin enthaltenen Zeichenfolgen mit einer endlichen Reihe von Operationen, von denen jede die Regelmäßigkeit bewahrt. Dies erfordert eine Anzahl von Durchgängen (Wandlern). Dies ist jedoch in Ordnung, da die Reihenfolge der Wandler und die Struktur der einzelnen Wandler im Voraus nur auf der Grundlage von und . Jeder Durchgang (Wandler) bewahrt die Regelmäßigkeit, sodass sie nicht in einem Durchgang verschachtelt werden müssen. Ja, nicht "elementar". Der Aufbau einer FSA auf einmal mit einem Durchgang wäre jedoch äußerst komplex.

M_{1, 0}

$M_{1,0}$

a

$a$

b

$b$

David Lewis

1

@ Raphael - ja, das ist sehr mächtig. Tatsächlich sind viele nicht reguläre Familien auch unter Wandlern mit endlichem Zustand geschlossen. Und Sie können Wandler als Reduktionsmechanismen verwenden, um eine ganze Theorie der "strukturellen" Komplexität nicht regulärer Sprachen zu erhalten.

David Lewis

8

Tipp 1 : Lösen Sie zuerst das populärere Problem "Schreiben Sie einen Automaten, der die durch 3 teilbaren Dezimal- / Binärdarstellungen von Zahlen erkennt", wenn das am wenigsten signifikante Bit zuerst erscheint.

Zwischenfrage: Beweisen Sie, dass regulär ist. $\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{Z}\}$

Hinweis Nr. 2 : Der Graph der Funktion "modulo " ist endlich. Sie können es für jedes in berechnen das sowohl die Ziffernmenge als auch die Sprache Ihres Automaten ist. $(n \mapsto 10n+d)$ $a$ $d$ $\{0, \dots, 9\}$

Tipp # 3 : jetzt, ersetzen mit . Was ändert sich daran? Versuchen Sie, die Tatsache zu nutzen, dass reguläre Sprachen durch Schnittpunkte stabil sind, anstatt einen Ad-hoc- Automaten zu erstellen. $x∈\mathbb Z$ $x∈\mathbb N$

Tipp 4 : wir nun an, dass eine Primzahl ist (so dass ein Feld ist) und dass wir uns immer noch in dem Fall befinden, in dem . Wir verwenden jetzt eine Darstellung, bei der das erste Bit das höchstwertige Bit ist. Können Sie den Automaten auf die gleiche Weise bauen? $a$ $\mathbb Z/a\mathbb Z$ $x∈\mathbb Z$

Tipp 5 : Sie müssen nicht immer einen Automaten bauen, um zu beweisen, dass eine Sprache regelmäßig ist. Wie können Sie frühere Ergebnisse verwenden, um zu beweisen, dass regelmäßig ist? (mit dem höchstwertigen Bit zuerst) $M$

jmad
quelle

Fühlen Sie sich frei zu kommentieren, wenn Sie der Meinung sind, dass dies nicht angemessen ist.

jmad

Tipp 1 ist ein großer Schritt. In Hinweis 4 ist es wichtig zu erkennen, dass und unterschiedlich sind. Wenn Sie über fühlt es sich wie ein Umweg an. Sie müssen das Zeichen verwalten: Warum nicht in bleiben ?

a \in {2, 5}

$a\in\{2,5\}$

a ⊥ 10

$a\bot10$

Z

$\mathbb{Z}$

N

$\mathbb{N}$

Gilles 'SO - hör auf böse zu sein'

@ Gilles: Ich wollte sagen, wenn und , weil mühsam zu erkennen ist.

\bar{a x + b}

$\overline{ax+b}$

a x + b \geq 0

$ax+b≥0$

x \in Z

$x∈\mathbb Z$

3 x + 1234

$3x+1234$

jmad

@ Gilles: Ich denke, Tipp Nr. 1 ist zu cool, um verwöhnt zu werden. Sie haben wahrscheinlich Recht mit Hinweis Nr. 4.

jmad

5

Ich folge der Idee von @vonbrand:

Tipp 1:

Löse zuerst nach . Sie können den Myhill-Nerode- Satz verwenden. $b=0$

Wir definieren die folgende Beziehung . Dies ist offensichtlich eine Äquivalenzbeziehung. Außerdem ist es rechtskongruent, da wir, wenn wir eine Ziffer anhängen , . Schließlich sättigt es , da die Äquivalenzklasse ist . Da eine endliche Anzahl von Klassen hat, haben wir nach dem Myhill-Nerode-Theorem, dass es regulär ist. Die zugehörige FSA ist minimal und hat Status. $\bar x\approx \bar y :\iff x\equiv y \mod a$ $d$ $\bar x \approx \bar y \iff 10x+d \equiv 10y+d \mod a \iff \bar x d \approx \bar y d$ $L$ $L$ $[0]$ $\approx$ $a$

Tipp 2:

Lösen Sie den allgemeinen Fall und verwenden Sie den durch den Fall induzierten Automaten erneut . $b=0$

Wir wissen, dass die Sprache für regulär ist . Nehmen Sie daher einfach den Zustand FSA für die Sprache . Jetzt haben wir eine FSA für konstruieren . Angenommen, hat Ziffern. Dann verzweigt sich die FSA wie ein 10-ariger Baum der Tiefe und enthält alle Pfade zu Zahlen mit Ziffern. Alle Zustände, die mit einer Zahl erreicht werden können, die nicht in der Form vorliegt, lehnen eine andere Annahme ab. Schließlich verbinden wir den Baumteil der FSA mit dem Automaten , entsprechend dem Rest durch die Division durch . $b=0$ $a$ $M$ $b=0$ $L$ $b$ $k$ $k$ $k$ $ax+b$ $M$ $a$

A.Schulz
quelle

Ich verstehe die Technik, aber nicht die Details. Adressiert Tipp 1 nicht auch den Fall ? Außerdem würde ich für Mod 10 10 Zustände erwarten (nicht )?

a = 1

$a=1$

a

$a$

Hendrik

3

Die Sprache ist regelmäßig.

Tipp: Neun austreiben

Beweisidee

Für und ist $a=9$ $b < 9$

Erstellen Sie einen Automaten mit Zuständen mit den Bezeichnungen bis . ist der Anfangszustand und der eine Endzustand ist . Von Zustand auf Ziffer Übergang zu Zustand . $9$ $0$ $8$ $0$ $b$ $s$ $d$ $(s + d) \;\mathrm{mod}\; 9$

Um andere Werte von , die mit koprime sind , $a$ $10$

gruppieren Sie Ziffern in Paketen, um einige zu finden, so dass teilt (z. B. nehmen Sie wenn weil ). $k$ $a$ $10^k-1$ $k=3$ $a=37$ $999 = 27 \times 37$

Um Werte von deren einzige Primfaktoren und , $a$ $2$ $5$

Beachten Sie, dass es am Ende nur um eine endliche Anzahl von Ziffern geht.

Um auf alle Werte von und zu verallgemeinern , $a$ $b$

Verwenden Sie die Tatsache, dass Vereinigung und Schnittmenge regulärer Sprachen regelmäßig sind, dass endliche Sprachen regelmäßig sind und dass die Vielfachen von genau die Vielfachen von beiden sind, wenn und Koprime sind. $a_1 \cdot a_2$ $a_1$ $a_2$

Beachten Sie, dass wir die jeweils geeignete Technik verwenden. Die drei wichtigsten Elementartechniken (reguläre Ausdrücke, endliche Automaten, satztheoretische Eigenschaften) sind in diesem Beweis alle dargestellt.

Detaillierter Beweis

Sei mit Koprime mit . Es sei und . Durch Elementararithmetik sind die Zahlen gleich modulo genau die Zahlen gleich modulo und modulo , also . Da der Schnittpunkt regulärer Sprachen regulär ist und $a = 2^p 5^q a'$ $a'$ $10$ $M' = \{\overline{a'\,x+b} \mid x\in\mathbb{Z} \wedge a'\,x+b \ge 0\}$ $M'' = \{\overline{2^p 5^q\,x+b} \mid x\in\mathbb{Z} \wedge 2^p 5^q\,x+b \ge 0\}$ $b$ $a$ $b$ $a'$ $b$ $2^p5^q$ $M \cap \{\overline{x} \mid x \ge b\} = M' \cap M'' \cap \{\overline{x} \mid x \ge b\}$ $\{\overline{x} \mid x \ge b\}$ ist regulär, weil es das Komplement einer endlichen (daher regulären) Sprache ist. Wenn und auch regulär sind, dann ist regulär; und ist daher regelmäßig, da es die Vereinigung dieser Sprache mit einer endlichen Menge ist. Um den Beweis abzuschließen, genügt es zu beweisen, dass und regulär sind. $M'$ $M''$ $M \cap \{\overline{x} \mid x \ge b\}$ $M$ $M'$ $M''$

Beginnen wir mit , dh Zahlen modulo . Die ganzen Zahlen, deren Dezimalerweiterung in werden durch ihre letzten -Ziffern charakterisiert , da das Ändern der Ziffern weiter links das Hinzufügen eines Vielfachen von ist ein Vielfaches von . Daher ist wobei das Alphabet aller Ziffern ist und eine endliche Menge von Wörtern der Länge und ist eine reguläre Sprache. $M''$ $2^p 5^q$ $M''$ $\mathrm{max}(p,q)$ $10^{\mathrm{max}(p,q)}$ $2^p 5^q$ $0^* M'' = \aleph^* F$ $\aleph$ $F$ $\mathrm{max}(p,q)$ $M'' = (\aleph^* F) \cap ((\aleph \setminus \{0\}) \aleph^*)$

Wir wenden uns nun , dh Zahlen modulo wobei Koprime mit . Wenn dann ist die Menge der Dezimalerweiterungen aller Naturtöne, dh , was a ist reguläre Sprache. Wir nehmen jetzt . Sei . Nach Fermats kleinem Satz ist , was bedeutet, dass teilt . Wir bauen einen deterministischen endlichen Automaten, der wie folgt erkennt : $M'$ $a'$ $a'$ $10$ $a' = 1$ $M'$ $M' = \{0\} \cup ((\aleph \setminus \{0\}) \aleph^*)$ $a' > 1$ $k = a'-1$ $10^{a'-1} \equiv 1 \mod a'$ $a'$ $10^k-1$ $0^* M'$

Die Zustände sind . Der erste Teil repräsentiert eine Ziffernposition und der zweite Teil repräsentiert eine Zahl modulo . $[0,k-1] \times [0,10^k-2]$ $10^k-1$
Der Ausgangszustand ist . $(0,0)$
Es gibt einen mit bezeichneten Übergang von zu wenn und . $d$ $(i,u)$ $(j,v)$ $v \equiv d 10^i + u \mod 10^k-1$ $j \equiv i + 1 \mod k$
Ein Zustand ist endgültig, wenn (beachte, dass teilt ). $(i,u)$ $u \equiv b \mod a'$ $a'$ $10^k-1$

Der Zustand von einem Wort erfüllt und . Dies kann durch Induktion über das Wort nach den Übergängen auf dem Automaten bewiesen werden; Die Übergänge werden hierfür unter Verwendung der Tatsache berechnet, dass . Somit erkennt der Automat die Dezimalerweiterungen (die anfängliche Nullen zulassen) der Zahlen der Form mit ; da , erkennt der Automat die Dezimalerweiterungen der Zahlen gleich modulo erlaubt anfängliche Nullen, d. h $(i,u)$ $\overline{x}$ $i \equiv |\overline{x}| \mod k$ $u \equiv x \mod 10^k-1$ $10^k \equiv 1 \mod 10^k-1$ $u + y 10^k$ $u \equiv b \mod a'$ $10^k \equiv 1 \mod a'$ $b$ $a'$ $0^* M'$ . Diese Sprache ist somit regelmäßig bewiesen. Schließlich ist eine reguläre Sprache. $M' = (0^* M') \cap ((\aleph \setminus \{0\}) \aleph^*)$

Um auf andere Basen als zu verallgemeinern , ersetzen Sie und oben durch alle Primfaktoren der Basis. $10$ $2$ $5$

Formeller Beweis

Links als Übung für den Leser, in Ihrem Lieblingssatzbeweiser.

Gilles 'SO - hör auf böse zu sein'
quelle

Sprache der Werte einer affinen Funktion

Antworten:

Beweisidee

Detaillierter Beweis

Formeller Beweis