Ce langage est-il rationnel ?

Champ-Pot-Lion · August 2018

Bonjour,

Sur Wikipédia, on trouve ce contre-exemple à la réciproque du lemme de l'étoile par blocs (ce qu'est le lemme de l'étoile par blocs, ni même le lemme de l'étoile, n'est pas important pour ma question).

Wikipédia a écrit:

Soient $A=\{a,b\}$ et $B=\{a,b,\#\}$ ; soit $K = \{ uu\mid\ u \in \ A^+\}$ et $K' = \{ u\#v \mid\ u,v \in \ A^* \text{ et } u \neq v\}$. Le langage $L$ défini par :
$L=K'\cup A^*KA^*\#A^*\cup A^*\#A^*KA^*$
vérifie la conclusion du lemme de l'étoile par blocs. Cependant, il n'est pas rationnel.

Cependant, le langage donné me semble bien régulier. En effet, les mots du langage sont ceux de la forme $u \# v$ avec $u,v \in A^*$, et tels que :

Soit $u$ a un facteur carré.
Soit $v$ a un facteur carré.
Soit, dans le cas restant, ni $u$, ni $v$ n'ont de facteur carré, mais sont différents. Mais il n'y a qu'un nombre fini de mots sans facteur carré, donc c'est testable avec une mémoire bornée.

Est-ce que j'ai fait une erreur ?

Romyna · August 2018

Les expressions régulières ne sont pas finies.

Champ-Pot-Lion · August 2018

Je vais donner plus de détails. On commence par voir que le complémentaire $\overline{S}$ de $S := A^* K A^*$ est rationnel. En effet, c'est un ensemble fini, explicitement c'est $\{\varepsilon, a, b, ab, ba, aba, bab\}$. Si un mot n'est pas dans cet ensemble, il a obligatoirement comme facteur $aa$, $bb$, $abab$, ou $baba$. C'est dit ici sur wikipédia : https://en.wikipedia.org/wiki/Square-free_word .

Comme c'est un ensemble fini, $K'' := \{x\#y\,|\,x,y\in\overline{S}\text{ et }x\neq y\}$ est rationnel. Le langage donné comme exemple sur Wikipédia est égal à $K'' + S \# A^* + A^* \# S$ et est donc rationnel.

Ce langage est-il rationnel ?

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 36