Es ist bekannt, dass die Sprache von Wörtern mit der gleichen Anzahl von 0 und 1 nicht regulär ist, während die Sprache von Wörtern mit der gleichen Anzahl von 001 und 100 regulär ist ( siehe hier ).
Ist es bei zwei gegebenen Wörtern entscheidend, ob die Sprache der Wörter, die die gleiche Anzahl von und regulär ist?
Antworten:
Ist es bei zwei gegebenen Wörtern , w 2 entscheidend, ob die Sprache L von Wörtern, die die gleiche Anzahl von w 1 und w 2 enthalten, regulär ist?w1 w2 L w1 w2
Zunächst einige Definitionen:
Sie könnten präziser formuliert und die Notationen verbessert werden, wenn sie in Proofs verwendet werden sollen. Dies ist nur ein erster Entwurf.
Ausgehend von zwei Wörtern und w 2 sagen wir:w1 w2
tritt immermit w 2 auf , notiert mit w 1 ≤ w 2 , wenn fw1 w2 w1◃w2
fällt immermit w 2 zusammen , notiert mit w 1 ◃ ◃w1 w2 , wenn jedes immer mit dem anderen auftritt,w1◃▹w2
und w 2 treten unabhängig voneinander auf, wobei w 1 ≤ ≤ istw1 w2 , wenn keines immer mit dem anderen auftritt,w1▹◃w2
tritt immer m mal oder mehrals w 2 stellte w 1 ◃ m w 2 , genau dannwenn für jedes Zeichenfolge s , so dass s = x w 2 y mit | x | , | y | | ≥ ∣ w 1 ∣ + ∣ w 2 ∣ es gibt m andere Zerlegungen s = x i w 1 y iw1 m w2 w1◃mw2 s s=xw2y ∣x∣, ∣y∣| ≥∣w1∣+∣w2∣ m s=xiw1yi für
so dass i ≠ j x i ≠ x j impliziert .i∈[1,m] i≠j xi≠xj
Diese Definitionen sind so aufgebaut, dass wir ignorieren können, was an den Enden der Zeichenkette passiert, an denen und w 2 auftreten sollen. Randeffekte am Ende der Zeichenfolge müssen separat analysiert werden, aber sie stellen eine begrenzte Anzahl von Fällen dar (tatsächlich denke ich, dass ich ein oder zwei solcher Randunterfälle in meiner ersten Analyse unten vergessen habe, aber das spielt keine Rolle). Die Definitionen sind kompatibel mit Überlappungen von Vorkommen.w1 w2
Es sind 4 Hauptfälle zu berücksichtigen (wobei die Symmetrie zwischen und w 2 ignoriert wird ):w1 w2
Beide Wörter müssen zusammenkommen, außer möglicherweise an den Enden der Zeichenkette. Dies betrifft nur Paare der Form 1 i 0 und 01 i oder 0 i 1 und 10 i . Dies wird leicht von einemendlichen Automatenerkannt, der nur an beiden Enden der zu erkennenden Zeichenfolge auf einzelne Vorkommen prüft, um sicherzustellen, dass an beiden Enden oder an keinem Ende ein einzelnes Vorkommen vorliegt. Es gibt auch den entarteten Fall, wenn w 1 = w 2 ist : dann ist die Sprache L offensichtlich regelmäßig.w1◃▹w2
1i0 01i 0i1 10i w1=w2
, aber nicht w 2 ◃ w 1 Eines der beiden Wörter kann ohne das andere nicht vorkommen, aber die Umkehrung ist nicht wahr (außer möglicherweise an den Enden der Zeichenkette). Dies passiert, wenn:w1◃w2 w2◃w1
ist eine Teilzeichenfolge von w 2 : Dann kann ein endlicher Automat nur überprüfen, dass w 1 nicht außerhalb einer Instanz von w 2 auftritt.w1 w2 w1 w2
und w 2 = v 1 j für ein Wort v ∈ { 0 , 1 } ∗ , v ≠ 01 i : dann eine endliche Automatenprüfung wie im vorhergehenden Fall, dass w 1 nicht getrennt von w 2 auftritt. Der Automat erlaubt jedoch das Zählen einer zusätzlichen Instanz von w 1 , die die Annahme von w 2 ermöglichtw1=1i0 w2=v1j v∈{0,1}∗ v≠01i w1 w2 w1 w2 ist ein Suffix der Zeichenfolge. Es gibt drei weitere symmetrische Fälle (1: 0-Symmetrie und Links-Rechts-Symmetrie).
One of the 2 words occurs twice in the other. That can be recognized by an a finite automation that checks that the smaller word never occurs in the string. The is also a slightly more complex variant that combines the two variations of case 2. In this case the automaton checks that the smaller string
The 2 words can occur independently of each other. We build a generalized-sequential-machine (gsm)
Actually we have
One way to organize a formal proof could be the following. First build a PDA that recognizes the language. Actually it can be done with a 1-counter machine, but it is easier to have two stack symbols to avoid duplicating the finite control. Then, for the cases where it should be a FA, show that the counter can be bounded by a constant that depends only on the two words. For the other cases show that the counter can reach any arbitrary value. Of course, the PDA should be organized so that the proofs are easy enough to carry.
Representing the FA as a 2-stack-symbols PDA is probably the simplest representation for it. In the non-regular case, the finite control part of the PDA is the same as that of the GSM in the proof sketch above. Instead of outputtinga 's and b 's like the GSM, the PDA counts the difference in number with the stack.
quelle