«Intégrer» une langue en soi

Question principale / générale

Soit $L$ une langue. Définissez les langues $L_i$ avec $L_0 = L$ et

$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$ pour . Considérez . Donc, nous "incorporons" à plusieurs reprises en lui-même pour obtenir .$i \geq 1$$\hat{L} = \bigcup L_i$$L$$\hat{L}$

A été étudiée? At-il un nom?$\hat{L}$

Exemples / motivation

Comme demandé dans les commentaires, voici quelques exemples pour mieux illustrer ce qu'est . Puis, puisque personne (jusqu'à présent) ne semble avoir vu cette notion, je discuterai de ma motivation pour la regarder.$\hat{L}$

Klaus Draeger m'a battu pour ajouter des exemples. Je vais mettre ces exemples des commentaires ici pour une visibilité accrue car ce sont de bons exemples.

Si est un langage unaire , alors (et est donc régulier).$L$$\hat{L} = L^+$

Si , alors est le langage Dyck .$L = {ab}$$\hat{L}$

Voici une autre façon de penser à . Étant donné une langue sur un alphabet nous jouons le jeu suivant. Nous prenons tout la tentative de réduire la chaîne vide par la suppression à plusieurs reprises en sous - mots qui sont . (Ici, nous devons faire un peu attention à la façon dont nous traitons la chaîne vide elle-même pour nous assurer qu'elle est équivalente à la définition ci-dessus, mais c'est moralement correct.)$\hat{L}$$L$$A$$w \in A^*$$w$$\epsilon$$L$

À l'origine, je suis venu définir en considérant la suppression des pouvoirs dans les mots. Prenez pour être la langue des cubes sur l'alphabet binaire . Alors et nous pouvons considérer la " suppression en " suivante L={w3:w∈A*}A={a,b}aunabaabaabbabab∈ L$\hat{L}$$L = \{w^3 : w \in A^*\}$$A = \{a,b\}$$aaabaabaabbabab \in \hat{L}$$L$

$$a(aabaabaab)babab \to ababab \to \epsilon.$$

Observez que toutes les suppressions ne fonctionneront pas

$$(aaa)baabaabbabab \to baabaabbabab$$

et nous sommes coincés avec un mot sans cube. Donc, il y a une autre notation de « fortement -deletable » qui en général ne coïncidait pas avec L .$L$$\hat{L}$

Un dernier exemple, si dans la langue de carrés sur l'alphabet binaire A = { a , b } , puis L est les cordes à la fois un nombre pair d' un « s et un nombre pair de b » s. De toute évidence, cette condition est nécessaire. Une façon de voir qu'il suffit est d'envisager de supprimer des carrés et de rappeler que chaque mot binaire de longueur 4 ou grand a un carré. Ici , L est régulier.$L$$A = \{a,b\}$$\hat{L}$$a$$b$$\hat{L}$

Pour les alphabets plus gros, ce type d'argument échoue car il y a des mots arbitrairement longs sans carré . Avec alphabets de taille Je peux montrer L n'est pas régulière en utilisant Myhill-Nerode et le fait qu'il ya des mots arbitrairement long carré libre, mais je n'ai pas été en mesure de dire beaucoup plus. J'espérais que le regarder de cette manière plus abstraite pourrait éclairer la situation (et cette définition plus abstraite semble intéressante en soi).$k \geq 3$$\hat{L}$

Cette question est liée aux soi-disant systèmes d'insertion .

Un système d'insertion est un type particulier de système de réécriture dont les règles sont de la forme pour tout r dans une langue donnée R . Écrivons u → R v si u = u ' u " et v = u ' r u " pour certains r ∈ R . Appelons * → R la fermeture transitive réflexive de la relation → R . La fermeture d'une langue L de$1 \rightarrow r$$r$$R$$u \rightarrow_R v$$u = u'u''$$v = u'ru''$$r \in R$$\buildrel{*}\over\rightarrow_R$$\rightarrow_R$$L$ sous ∗ → R est le langage [ L ] ∗ → R = { v ∈ A ∗ ∣  il existe  u ∈ L  tel que  u ∗ → R v } Rappelons qu'unbien quasi-ordresur un ensemble E est un réflexif et relation transitive ⩽ telle que pour toute séquence infinie x 0 , x 1 , … des éléments de$A^*$$\buildrel{*}\over\rightarrow_R$

$$[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}$$ $E$$\leqslant$$x_0, x_1, \ldots$$E$, il y a deux entiers tels que x i ⩽ x j . Le théorème suivant est prouvé dans [1]:$i < j$$x_i \leqslant x_j$

Si est un ensemble fini de mots tel que le langage A ∗ ∖ A ∗ H A ∗ est fini, alors la relation ∗ → R est un bien quasi-ordre sur A ∗ et [ L ] ∗ → R est régulier.$H$$A^* \setminus A^*HA^*$$\buildrel{*}\over\rightarrow_R$$A^*$$[L]_{\buildrel{*}\over\rightarrow_R}$

[1] W. Bucher, A. Ehrenfeucht et D. Haussler, Sur les régulateurs totaux générés par les relations de dérivation, Theor. Comput. Sci. 40 , 2-3 (1985), 131-148.

Comme J.-E. Pin a souligné que ma question porte sur l' insertion . J'ai trouvé une autre source que je posterai ici pour toute personne intéressée.

L.Kari. Sur l'insertion et la suppression dans les langues officielles. doctorat Thèse, Université de Turku, 1991.

Voici les parties I et II de la thèse.

D'après ce que je peux dire, c'est la source originale pour l'étude de l'insertion.