Est-il décidable si une langue décrite par nombre d'occurrences est régulière?

On sait que la langue des mots contenant un nombre égal de 0 et 1 n'est pas régulière, tandis que la langue des mots contenant un nombre égal de 001 et 100 est régulière ( voir ici ).

Étant donné deux mots $w_1,w_2$ , est-il décidable si la langue des mots contenant un nombre égal de $w_1$ et $w_2$ est régulière?

Étant donné deux mots , w 2 , est-il décidable si la langue L de mots contenant un nombre égal de w 1 et w 2 est régulière?$w_1$$w_2$$L$$w_1$$w_2$

D'abord quelques définitions:
elles pourraient être rendues plus concises, et les notations pourraient être améliorées si elles devaient être utilisées dans des épreuves. Ce n'est qu'un premier projet.

Étant donné deux mots et w 2 , nous disons que: $w_1$$w_2$

• se produit toujoursavec w 2 , noté w 1 ◃ w 2 , ssi $w_1$ $w_2$$w_1\triangleleft w_2$

  1. pour toute chaîne telle que s = x w 2 y avec ∣ x ∣ $s$$s=xw_2y$ et | x | 0 , | x | 1 | , | y | 0 , | y | 1 | ≥ 1 il y a une autre décomposition s = x ′ w 1 y ′ . Remarque: La condition que x et$\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$$|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$$s=x'w_1y'$
     $x$$y$contiennent chacun au moins un 0 et un 1 est requis par un cas pathologique (trouvé par @sdcvvc): , w 2 = v 1 i + j et y ∈ 1 ∗ , et ses variantes symétriques.$w_1=1^i0$$w_2=v1^{i+j}$$y\in1^*$
  2. il y a une chaîne avec ∣ x ∣ $s=xw_2y$ telle qu'il y ait au plus une décomposition s = x ′ w 1 y $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$$s=x'w_1y'$

• coïncide toujoursavec w 2 , noté w 1 ◃ $w_1$ $w_2$ , si chacun se produit toujours avec l'autre,$w_1\triangleleft \triangleright\,w_2$

• et w 2 se produisent indépendamment, noté w 1 ▹ $w_1$$w_2$ , si aucun ne se produit toujours avec l'autre,$w_1\triangleright \triangleleft\,w_2$

• apparaît toujours m fois ou plusque w 2 , noté w 1 ◃ m w 2 , ssi pour toute chaîne s telle que s = x w 2 y avec ∣ x ∣ , ∣ y ∣ | ≥ ∣ w 1 ∣ + ∣ w 2 ∣ il existe m autres décompositions s = x i w 1 y $w_1$ $m$$w_2$$w_1\triangleleft_m w_2$$s$$s=xw_2y$$\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid w_2\mid$$m$$s=x_iw_1y_i$pour tel que i ≠ j implique x i ≠ x j .$i\in[1,m]$$i\neq j$$x_i\neq x_j$

Ces définitions sont construites de sorte que nous pouvons ignorer ce qui se passe aux extrémités de la chaîne où et w 2 sont censés se produire. Les effets de frontière à la fin de la chaîne doivent être analysés séparément, mais ils représentent un nombre fini de cas (en fait, je pense que j'ai oublié un ou deux de ces sous-cas de frontière dans ma première analyse ci-dessous, mais cela n'a pas vraiment d'importance). Les définitions sont compatibles avec le chevauchement des occurrences.$w_1$$w_2$

Il y a 4 cas principaux à considérer (en ignorant la symétrie entre et w 2 ):$w_1$$w_2$

1. Les deux mots se rejoignent nécessairement, sauf éventuellement aux extrémités de la chaîne. Cela ne concerne que les paires de la forme 1 i 0 et 01 i , ou 0 i 1 et 10 i . Ceci est facilement reconnu par unautomate finiqui vérifie uniquement les occurrences isolées aux deux extrémités de la chaîne à reconnaître, pour s'assurer qu'il existe une occurrence isolée aux deux extrémités ou à aucune extrémité. Il y a aussi le cas dégénéré quand w 1 = w 2 : alors le langage L est évidemment régulier.$w_1\triangleleft \triangleright\,w_2$
   $1^i0$$01^i$$0^i1$$10^i$$w_1=w_2$

2. , mais pas w 2 ◃ w 1 L'un des 2 mots ne peut pas se produire sans l'autre, mais l'inverse n'est pas vrai (sauf éventuellement aux extrémités de la chaîne). Cela se produit lorsque:$w_1\triangleleft w_2$$w_2\triangleleft w_1$
   

   • est une sous-chaîne de w 2 : alors un automate fini peut simplement vérifier que w 1 ne se produit pas en dehors d'une instance de w 2 .$w_1$$w_2$$w_1$$w_2$

   • et w 2 = v 1 j pour un mot v ∈ { 0 , 1 } ∗ , v ≠ 01 i : puis un automate fini vérifie comme dans le cas précédent que w 1 ne se produit pas séparé de w 2 . Cependant, l'automate permet de compter une instance supplémentaire de w 1 qui permettra l'acceptation si w $w_1=1^i0$$w_2=v1^j$$v\in\{0,1\}^*$$v\neq01^i$$w_1$$w_2$$w_1$$w_2$est un suffixe de la chaîne. Il existe trois autres cas symétriques (symétrie 1-0 et symétrie gauche-droite).

3. L'un des 2 mots apparaît deux fois dans l'autre. Cela peut être reconnu par une automatisation finie qui vérifie que le plus petit mot ne se produit jamais dans la chaîne. C'est aussi une variante légèrement plus complexe qui combine les deux variantes du cas 2. Dans ce cas, l'automate vérifie que la plus petite chaîne 1 i 0 ne se produit jamais, sauf éventuellement dans le cadre de v dans la plus grande v 1 j venant comme suffixe de la chaîne (et 3 autres cas par symétrie).$w_1\triangleleft_2 w_2$
   $1^i0$$v$$v1^j$

4. Les 2 mots peuvent apparaître indépendamment l'un de l'autre. Nous construisons une machine séquentielle généralisée (gsm) G qui génère a lorsqu'elle reconnaît une occurrence de w 1 et b lors de la reconnaissance d'une occurrence de w 2 , et oublie tout le reste. La langue L n'est régulière que si la langue G ( L ) est régulière. Mais G ( L ) = { w ∈ { a , b } ∗ ∣ ∣ w ∣ $w_1\triangleright \triangleleft\,w_2$
   $G$$a$$w_1$$b$$w_2$$L$$G(L)$ qui est clairement hors contexte et non régulier. Par conséquent, L n'est pas régulier. En fait, nous avons L = G - 1 ( G ( L ) ) . Puisque les langages réguliers et les langages sans contexte sont fermés sous mappage gsm et mappage gsm inverse, nous savons également que L est sans contexte.$G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$$L$
   $L=G^{-1}(G(L))$$L$

Une façon d'organiser une preuve formelle pourrait être la suivante. Construisez d'abord un PDA qui reconnaît la langue. En fait, cela peut être fait avec une machine à 1 compteur, mais il est plus facile d'avoir deux symboles de pile pour éviter de dupliquer le contrôle fini. Ensuite, pour les cas où il doit s'agir d'une FA, montrez que le compteur peut être délimité par une constante qui ne dépend que des deux mots. Pour les autres cas, montrer que le compteur peut atteindre n'importe quelle valeur arbitraire. Bien entendu, le PDA doit être organisé de manière à ce que les preuves soient assez faciles à transporter.

Représenter le FA comme un PDA à 2 symboles de pile est probablement la représentation la plus simple pour lui. Dans le cas non régulier, la partie de contrôle fini du PDA est la même que celle du GSM dans l'esquisse de preuve ci-dessus. Au lieu de produire et un b comme le GSM, le PDA compte la différence de nombre avec la pile.$a$$b$