Pouvons-nous rendre une langue non régulière régulière par concatentation?

Ma question porte essentiellement sur trois langues A, B et L, où L est A et B concaténés ensemble et B se révèle non régulier, est-il possible de trouver un A qui rend L régulier?

Si nous permettons $A$ être la langue vide, qui est régulière, alors nous avons cette $L = \{w_1w_2 | w_1 \in A, w_2 \in B\} = \emptyset = A$.

Pour le problème légèrement plus intéressant dans lequel A doit être un langage régulier non vide, alors nous pouvons construire un $B$ de telle sorte qu'aucun non vide $A$ entraîne une $L$

Laisser $B=\{bc^nd^n | n > 0\}$. Laisser$A$ être une langue régulière et considérer $L=\{w_1w_2 | w_1 \in A, w_2 \in B\}$. Notez que, contrairement à l'hypothèse de J.-E. Réponse de Pin,$B$ est irrégulier mais ne contient pas le mot vide.

Supposer $L$est régulier. Il existe des DFA,$M=(S,\Sigma,\delta,q_0,F)$, qui accepte $L$. Peu importe comment$A$ est construit, nous savons que chaque mot $L$ doit avoir une dernière occurrence de $b$. Laisser$Q$ être l'ensemble des États parcourus immédiatement après la dernière $b$dans toutes les traversées acceptables possibles. Notez que$Q$ ne peut pas être vide, car la chaîne la plus courte de $B$ est $bcd$. Laisser$S'$ être l'ensemble des états visités dans toutes les traversées acceptables possibles à un moment donné après la dernière $b$. Construction$M'=(S',\Sigma,\delta',q_0',F)$, où $\delta'$ se comporte de façon identique à $\delta$, sauf pour le fait que $\delta'(q_0, \varepsilon)=Q$.

Je déclare que ce NFA accepte la langue $C=\{c^nd^n| n > 0\}$. Pour toute$w' \in C$, nous devons avoir qu'il y a une certaine traversée d'un élément de $Q$ à un élément de $F$, depuis $M$doit accepter une chaîne avec ceci comme suffixe. Pour toute$w' \in \Sigma^{*} \setminus C$, nous pouvons choisir un $w \in A$ et former le mot $wbw'$. Si$M'$ accepte $w'$, il faut alors que $M$ accepte $wbw'$, car il doit y avoir eu une traversée d'un état dans $Q$ à $F$ qui est également valable pour $M$. Cependant, en raison de notre choix de$w'$, il ne peut pas être le cas $wbw' \in L$, donc $M'$ doit rejeter $w'$.

Donc $M'$ accepte $C$, mais ce langage n'est pas régulier, ce qui conduit à une contradiction.

Par conséquent, si $A$ n'est pas vide, alors $L$ ne peut pas être régulier.

Oui c'est possible. Prenons l'exemple donné ci-dessous:

Laisser $B = 1^p$ où $p$est premier. Ce n'est pas régulier. Laisser$A = 1^n$ où $n \in \mathbb{N}$. C'est régulier.

$AB$ nous donnera simplement $1^n$ avec $n > 2$ et cela est régulier car tout nombre supérieur à $2$ peut être représenté comme $2+x$ où $x > 0$

Laisser $\Sigma$être un alphabet non vide. Laisser$B$être une langue non régulière sur$\Sigma$ contenant le mot vide et laissez $A = \Sigma^*$. alors$L = AB = A$ est régulier.

Étant donné une langue $B$, la langue $\varnothing B = \varnothing$est régulier. En dehors de cette solution triviale, il n'est pas toujours possible de trouver une langue non vide$A$ tel que $AB = \{uv \mid u \in A \wedge v \in B\}$est régulier. Il est possible pour de nombreux non réguliers$B$(par exemple, si$B$contient le mot vide , ou si$B$est sur un alphabet unaire ) mais pas pour tous$B$.

Prendre $B = \{ca^n \mid n\in\mathbb{P}\}$ où $\mathbb{P}$est l'ensemble des nombres premiers. Peu importe$A$ est, si $A$ n'est pas vide alors $AB$ n'est pas régulier, car pour tester l'appartenance à $AB$, il est nécessaire (en raison du symbole «bouchon» $c$) pour utiliser une mémoire potentiellement illimitée pour tester la primauté du nombre de $a$est à la fin.

Pour le prouver, laissez $u \in A$ (puisque nous avons supposé que $A$n'est pas vide). Si$AB$ est régulier, alors $L_1 = AB \cap uca^*$, tout comme le quotient gauche de$L_1$ par le singleton $\{uc\}$ lequel est $L_2 = \{w \mid ucw \in AB \wedge ucw \in uca^*\} = \{w \in a^* \mid ucw \in AB\}$. Cette langue est juste$L_3 = \{a^n \mid n\in\mathbb{P}\}$ (si $w \in L_2$ alors il existe $v\in A$ et $k\in\mathbb{N}$ tel que $ucw = vca^k$, et depuis $w$ contient b ^ kno $c$, Cela implique que $w = a^k \in L_3$; inversement, si$w \in L_3$ puis $cw \in B$ donc $ucw \in AB$). $L_3$ est une langue non régulière bien connue, nous avons une contradiction.

Alors que votre question demande une preuve existentielle, elle me rappelle la branche de comp. sci. appelé Approximations régulières.

L'idée est de prendre une langue non régulière $L$ puis trouver une langue régulière $A$ tel que $L \ominus A \rightarrow 0$ sous une certaine condition / sous-ensemble de $L$ (où $\ominus$est la différence symétrique ), c'est-à-dire trouver un langage régulier qui est "arbitrairement proche" de$L$pour un sous-ensemble qui vous tient à cœur. Souvent, vous accomplissez cela en prenant un sous-ensemble fini de$L$ avec une grande mesure sur votre sous-ensemble d'intérêt, puis concaténer avec une langue régulière soigneusement choisie.

Vous pouvez trouver de nombreuses lectures intéressantes sur Google Scholar si vous recherchez quelque chose comme "approximation du langage normal sans contexte".