Können wir eine nicht reguläre Sprache durch Konzentration regulieren?

Meine Frage besteht im Wesentlichen aus drei Sprachen A, B und L, wobei L A und B miteinander verkettet sind und B nachweislich nicht regulär ist. Ist es möglich, ein A zu finden, das L regulär macht?

Wenn wir zulassen, dass die leere Sprache ist, die regulär ist, dann haben wir L = { w 1 w 2 | w 1 ∈ A , w 2 ∈ B } = ∅ = A .$A$$L = \{w_1w_2 | w_1 \in A, w_2 \in B\} = \emptyset = A$

Für das etwas interessantere Problem, bei dem A eine nicht leere reguläre Sprache sein muss, können wir ein so konstruieren, dass kein nicht leeres A zu einem regulären $B$$A$$L$

Sei . Sei A eine beliebige reguläre Sprache und betrachte L = { w 1 w 2 | w 1 ∈ A , w 2 ∈ B } . Beachten Sie, dass entgegen der Annahme in J.-E. Pins Antwort: B ist unregelmäßig, enthält aber kein leeres Wort.$B=\{bc^nd^n | n > 0\}$$A$$L=\{w_1w_2 | w_1 \in A, w_2 \in B\}$$B$

Angenommen, S ' ist die Menge von Zuständen, die in allen möglichen akzeptierenden Durchquerungen irgendwann nach dem letzten b besucht wurden . Konstruiere M $L$ ist regulär. Es gibt einige DFA, , die L akzeptieren . Unabhängig davon, wie A aufgebaut ist, wissen wir, dass jedes Wort in L das letzte Vorkommen von b haben muss . Sei Q die Menge von Zuständen, die unmittelbar nach dem letzten b in allen möglichen akzeptierenden Durchquerungen gereist sind . Man beachte , daß Q nicht leer sein kann, da die kürzeste Zeichenfolge in B ist , b c d . Lassen$M=(S,\Sigma,\delta,q_0,F)$$L$$A$$L$$b$$Q$$b$$Q$$B$$bcd$$S'$$b$ , wobei sich δ ' identisch zu δ verhält, mit derAusnahme, dass δ ' ( q 0 , ε ) = Q ist .$M'=(S',\Sigma,\delta',q_0',F)$$\delta'$$\delta$$\delta'(q_0, \varepsilon)=Q$

Ich behaupte, dass diese NFA die Sprache . Für jedes w ' ∈ C muss es eine gewisse Durchquerung von einem Element von Q zu einem Element von F geben , da M eine Zeichenfolge mit diesem als Suffix akzeptieren muss. Für jeden w ' ∈ & Sigma; * ∖ C , können wir eine Pick w ∈ A und das Wort bilden , w b w ' . Wenn M ' akzeptiert n > akzeptiert w $C=\{c^nd^n| n > 0\}$$w' \in C$$Q$$F$$M$$w' \in \Sigma^{*} \setminus C$$w \in A$$wbw'$$M'$$w'$ , dann muss es der Fall sein, dass w b w ' akzeptiert , da es eine Überquerung von einem Zustand in Q nach F gegeben haben muss, der auch für M gilt . Aufgrund unserer Wahl von w ' kann es jedoch nicht sein, dass w b w ' ∈ L ist , so dass M ' w ' ablehnen muss .$M$$wbw'$$Q$$F$$M$$w'$$wbw' \in L$$M'$$w'$

Also akzeptiert C , aber diese Sprache ist nicht regulär, was zu einem Widerspruch führt.$M'$$C$

Wenn also nicht leer ist, kann L nicht regulär sein.$A$$L$

Ja das ist möglich. Betrachten Sie das folgende Beispiel:

Sei wobei p eine Primzahl ist. Dies ist nicht regelmäßig. Sei A = 1 n, wobei n ∈ N ist . Das ist regelmäßig.$B = 1^p$$p$$A = 1^n$$n \in \mathbb{N}$

gibt uns einfach 1 n mit n > 2 und dies ist regulär, da jede Zahl größer als 2 als 2 + x dargestellt werden kann, wobei x > $AB$$1^n$$n > 2$$2$$2+x$$x > 0$

Sei ein nicht leeres Alphabet. Sei $\Sigma$$B$ seine jede irreguläre Sprache auf das leere Wort enthalten und lassen A = Σ * . Dann ist L = A B = A regulär.$\Sigma$$A = \Sigma^*$$L = AB = A$

Bei einer Sprache ist die Sprache ∅ B = ∅ regulär. Abgesehen von dieser trivialen Lösung ist es nicht immer möglich, eine nicht leere Sprache A zu finden, so dass A B = { u v ∣ u ∈ A ∧ v ∈ B } regulär ist. Es ist für viele nicht reguläre $B$$\varnothing B = \varnothing$$A$$AB = \{uv \mid u \in A \wedge v \in B\}$$B$ (zB wenn das leere Wort enthält$B$ , oder wenn auf ein einstelliges Alphabet ist$B$ ) , aber nicht für all .$B$

Nehmen Sie wobei P die Menge der Primzahlen ist. Was auch immer A ist, wenn A nicht leer ist, dann $B = \{ca^n \mid n\in\mathbb{P}\}$$\mathbb{P}$$A$$A$ nicht regulär, da zum Testen der Mitgliedschaft in A B (aufgrund des Stoppersymbols c ) ein potenziell unbegrenzter Speicher verwendet werden muss, um die Primalität der Anzahl von zu testen a ist am Ende.$AB$$AB$$c$$a$

Um dies zu beweisen, sei (da wir angenommen haben, dass A nicht leer ist). Wenn A B regulär ist, ist L 1 = A B ∩ u c a ∗ , ebenso wie der linke Quotient von L 1 durch den Singleton { u c }, der L 2 = { w ∣ u c w ∈ A B ist ∧ u c w ∈ u c $u \in A$$A$$AB$$L_1 = AB \cap uca^*$$L_1$$\{uc\}$ w = v c a k ist , und da w b ^ kno c enthält . Diese Sprache ist nur L 3 = { a n ∣ n ∈ P } (wenn w ∈ L 2 ist, dann gibt es v ∈ A und k ∈ N, so dass u $L_2 = \{w \mid ucw \in AB \wedge ucw \in uca^*\} = \{w \in a^* \mid ucw \in AB\}$$L_3 = \{a^n \mid n\in\mathbb{P}\}$$w \in L_2$$v\in A$$k\in\mathbb{N}$$ucw = vca^k$$w$$c$dies impliziert, dass ; umgekehrt, wenn w ∈ L 3 ist, dann ist c w ∈ B, also u c w ∈ A B ). L 3 ist eine bekannte nicht reguläre Sprache, wir haben einen Widerspruch.$w = a^k \in L_3$$w \in L_3$$cw \in B$$ucw \in AB$$L_3$

Während Ihre Frage nach einem existenziellen Beweis fragt, erinnert sie mich an den Zweig von comp. sci. genannt Regelmäßige Annäherungen.

Die Idee ist, eine nicht reguläre Sprache und dann eine reguläre Sprache A zu finden, so dass L ⊖ A → 0 unter einer Bedingung / Teilmenge von L (wobei ⊖ die symmetrische Differenz ist ), dh eine reguläre Sprache zu finden, die "willkürlich" ist nah "an $L$$A$$L \ominus A \rightarrow 0$$L$$\ominus$$L$ für eine Teilmenge, die Sie interessiert. Oft erreichen Sie dies, indem Sie eine endliche Teilmenge von mit einem großen Maß über Ihre interessierende Teilmenge nehmen und sie dann mit einer sorgfältig ausgewählten regulären Sprache verketten.$L$

Sie können viele interessante Lesungen in Google Scholar finden, wenn Sie nach "regulärer Sprachnäherung ohne Kontext" suchen.