$ L= $ {W $ \ in (a, b) ^ * $ |Für jeden U-Teilstring von W, $ -5 \ le | u | _A- | u | _b \ le5 \} $ ist regelmäßig

Question

Ich versuche zu zeigen, dass diese Sprache regelmäßig ist:

$ l= $ {w $ \ in \ (a, b) ^ * $ | |Für jeden U-Teilstring von W, $ - 5 \ le | u | _A- | u | _b \ le5 \} $

Wenn ich einen NFA baue und jedes Mal, wenn ich jedes Mal, wenn ich andere Buchstaben überspringe) - und nur, wenn sie alle akzeptiert werden (folgt dem Zustand), dann akzeptieren Sie w. Ist es in NFA möglich?Gibt es eine andere Möglichkeit, die Regelmäßigkeit der Sprache zu zeigen?

Answer 1

Schöne Frage! Dies ist ein sehr nichtriviales Problem, das regelmäßige Sprachen beteiligt ist.

Zunächst einmal: Nein, Sie können auf jedem Teilzeichen einer Zeichenfolge andere Buchstaben mit anderen Buchstaben ausführen. Sie sollen den Automaton nur einmal auf der Zielzeichenfolge ausführen.

In diesem Fall ist es einfacher, auf die komplementäre der gegebenen Sprache zu greifen, nämlich auf

$$ l ^ c={w \ in (a, b) ^ * \ Mid \ Text {Es gibt ein Teilstring} \ text {von} w \ text {so, dass} |} | _A- | u | _b> 5 \ text {oder} | u | _A- | u | _b <-5 \} $$

Die Sprache $ l ^ C $ ist regelmäßig, da es von den folgenden NFA erkannt wird:

(Jeder Zustandsname ist der Unterschied $ | U | _A- | u | _b $ , der erste Buchstabe des Substring- $ u $ ist" fand "dombleminministisch vom NFA).

so, wie $ l ^ c $ regelmäßig ist, auch $ l= (l ^ c) ^ c $ ist.

---

Nach dem Vorschlag von Hendrick versuchte ich, das NFA zu erkennen und seine Ergänzung zu zeichnen, und ich bekomme diese nette DFA, die $ L $ :

Jeder Name eines Annahme-Statusnamens ist ein Intervall: Wenn, wenn der Automaton ausgeführt wird, sind wir in staatlicher $ [x_1, x_2] $ und wir haben das gelesen string $ Z $ Dies bedeutet, dass für alle $ X \ in [x_1, x_2] $ es gibt Suffix $ u $ von $ Z $ so, dass $ | u | _A- | u | _b= x $ . Ansonsten gesagt, nach dem Vorschlag von Dmitrys, berechnet der Automaton den Restsatz von $ Z $ .

In gewisser Weise, wie Hendrick sagt, es ist, als ob wir den Automaton auf jedem Teilstring ausführen, aber dies bedeutet nicht, dass wir ein DFA direkt verwenden können, der Saiten erkennen, dass der Unterschied zwischen der $ A $ s und der $ B $ s ist in $ [- 5,5 ] $ (was leicht realisieren würde) und leiten Sie diesen Automaton auf jedem Teilstring eines bestimmten, und beweisen auf diese Weise, dass die Sprache regelmäßig ist.

---

Schließlich würde ich eine triviale Verallgemeinerung des Ergebnisses schreiben (ich denke, dass dies Folklore ist, aber ich konnte keine Referenz finden).

lass $ t $ Seien Sie eine normale Sprache in einem Alphabet $ \ Sigma $ und lassen Sie $ L $ Seien Sie die Sprache, die wie folgt definiert ist:

$$ L={W \ in \ Sigma ^ * \ MID \ Text {für jeden Teilzeichen} \ text {von} w, \ u \ in t \} $$

dann auch $ l $ ist regelmäßig.

in der Tat, wie oben, in Betracht ziehen $ l ^ C $ , die Ergänzung von $ L $ , nämlich

$$ l ^ c={w \ in \ sigma ^ * \ mid \ text {Es gibt einen Teilstring} u \ text {von} w \ text {so } u \ nicht \ in t \} $$

dann $ l ^ c \ \ Sigma ^ * t ^ c \ sigma ^ * $ , und deshalb $ l= (\ Sigma ^ * t ^ c \ sigma ^ *) ^ C \ Sigma ^ *) ^ C $ ist regelmäßig, da die Familie der regulären Sprachen unter Verkettung und Komplementierung geschlossen ist.

cleary Das Ergebnis stimmt immer noch für jede in der Verkettung und Ergänzung geschlossene Familie der Sprachen, aber dies ist kein notwendiger Zustand. In der Tat ist die Familie von Finite-Sprachen, die es nicht unter Komplementierung geschlossen ist, aber eindeutig, wenn $ T $ endlich ist, dann auch $ L $ ist (wie es immer der Fall ist, dass $ l \ Subseteq T $ ). Auf der anderen Seite trifft dies nicht für alle Sprachenkursen zu. Betrachten Sie die Familie nr von nicht-regulären Sprachen, dann $ T={1 ^ p \ mid p \ text {is prime} \ \ \ in \ $ nr, In diesem Fall haben wir jedoch $ l=varnothing $ , was regelmäßig ist.