Sind reguläre Sprachen zusätzlich geschlossen?

Konkret meine ich mit Addition, wir definieren als das Alphabet . Schauen Sie sich bei den regulären Sprachen und unter einem Alphabet . $\Sigma_i$ $\{0, 1, 2, ..., i\}$ $A$ $B$ $\Sigma_i$ $A\times B$

Definieren Sie für jedes geordnete Paar die "Summe" dieses geordneten Paares als , wobei und Zahlen in der Basis i sind. Führende Nullen werden ignoriert, daher steht vor jeder akzeptierten Zeichenfolge. Dies impliziert, dass als 0 definiert ist. $(a, b) \in A\times B$ $a+b$ $a$ $b$ $0^*$ $\epsilon$

Die Sprache ist die Menge von Zeichenfolgen, die alle diese möglichen Summen darstellen. $A+B$

Bisher weiß ich:

Dies gilt für unary ( ). $\Sigma_1$
Dies gilt für alle endlichen regulären Sprachen und , da jede endliche Sprache regulär und endlich ist. $A$ $B$ $A+B$
Die Sprache = s s ist ein Vielfaches von n in der Basis b unter ist regulär für jedes . Dies bedeutet, dass auch beliebige Sprachen der Form hinzugefügt werden können, da , was ebenfalls regulär ist. Es gibt jedoch Sprachen wie = s s beginnt und endet mit einer 1}, die diesen Kriterien nicht entspricht, sodass nicht alle regulären Sprachen beschrieben werden. $C_n$ $\{$ $|$ $\}$ $\Sigma_b$ $b >= 1$ $C_n$ $C_i+C_j=C_{i + j}$ $D$ $\{$ $|$

automata-theory Phylliida
quelle

Es ist nicht wahr, dass wenn A in Basis 2 regulär ist, es auch in Basis 3 regulär ist, z. B. die Potenzen von 2.

domotorp

Ich verstehe, du hast recht. Ich habe die Frage entsprechend bearbeitet. Ich habe versucht, dies zu beweisen, und es schien wahr zu sein, und dann habe ich falsch verstanden, was ein Homomorphismus ist, und angenommen, dass es wahr ist. Aber das tut es nicht, tut mir leid. Wenn eine Sprache in der Basis b ^ a für einige a> 1 regulär ist, ist sie in jeder anderen Basis b ^ (ac) für jede 1 <= c <a jedoch regulär. (Wenn beispielsweise eine Sprache in Basis 8 regulär ist, ist sie auch in Basis 4 und 2 regulär, indem einfach die Basis-8-dfa simuliert wird.)

Phylliida

"Dies impliziert, dass ϵ als 0 definiert ist". Ich verstehe nicht, was das bedeutet. Wenn 0 und ϵ gleich sind, können alle Nullen entfernt werden und die Zahleninterpretation funktioniert nicht mehr.

Babou

Der Punkt ist einfach, dass, wenn sich eine leere Zeichenfolge ϵ in einem geordneten Paar befindet, sie der anderen Zeichenfolge 0 hinzufügt. Auch für jede Zeichenfolge mit führenden Nullen können sie entfernt werden. Dies bedeutet, dass 000101 beispielsweise mit 101 identisch ist. Dies ist, was ich meinte, wenn ein ϵ in einer Zeichenfolge für sich selbst auftaucht , dann ist es in Bezug auf eine Summe als 0, 00 oder 000 für sich gleichwertig . Wenn sich diese Zeichenfolgen innerhalb einer anderen Zeichenfolge befinden, sind alle Wetten deaktiviert, und diese Ersetzung ist nicht mehr gültig.

Phylliida

Antworten:

Ja, sind Sie.

$\Sigma_i^3$ $A'$ $A$ $B'$ $B$ $C$ $A'$ $B'$ $A$ $B$ $C$ Verwendet die Tatsache, dass Sie eine Addition durchführen können, indem Sie von rechts nach links scannen und dabei nur eine einzige Ziffer des Übertrags als Status beibehalten.

$A'\cap B'\cap C$ $A$ $B$

David Eppstein
quelle

Das ist wirklich großartig. Ich wusste nicht, dass Sie diese Stapel auf diese Weise verwenden können. Vielen Dank!

Phylliida

Zugegeben, dies ist etwas zweifelhaft, da es in diesem Fall nur Summen von Zeichenfolgen gleicher Größe enthält, da wir jedoch Summen von Zeichenfolgen unterschiedlicher Größe "simulieren" können, indem wir links Nullen hinzufügen, und es einfach ist, eine dfa zu ändern eine weitere dfa, die 0 * vor allen akzeptierenden Zeichenfolgen erkennt (sobald Sie die summierende dfa erstellt haben, um C mit Homomorphismus zu erkennen).

Phylliida

Ich nehme an, der größte Schlüssel ist, dass A und B auf die gleiche Weise "technisch modifiziert" werden müssen, um 0 * A und 0 * B zu sein, und wenn wir dies tun, reicht es aus, für jedes Paar von a und b das zu finden Summe von 0 * a + 0 * b st Beide Werte haben genug führende Nullen, um mit den Größen übereinzustimmen, und dann kann das Ergebnis nach Bedarf von Nullen befreit werden, da C auf die gleiche Weise geändert wird. War das impliziert oder gibt es eine einfachere Möglichkeit, das zu betrachten, was mir fehlt?

Phylliida

Ja, es gibt einige technische Aspekte beim Auffüllen, aber sie ändern die Grundideen nicht wirklich, so dass ich sie weggelassen habe.

David Eppstein

Cool, das macht Sinn.

Phylliida

$A$ $B$ $M_A$ $M_B$ $a$ $b$ $M_A$ $M_B$ $M_A$ $M_B$

domotorp
quelle