Automate
exercice :
soient $A$ un alphabet et $L \subseteq A^{*}$ un langage. l'équivalence syntaxique $\approx_{L}$ est définie, pour tout $u,v \in A^{*}$, par $u \approx_{L} v$ si $$
\forall w,w' \in A^{*},\quad wuw' \in L \iff wvw'\in L
$$ Montrer que $\approx_{L}$ a un nombre fini de classes d'équivalence ssi $L$ est reconnaissable.
Note: j'arrive à faire la première implication, j'ai un souci avec la réciproque, si quelqu'un pouvait m'aider, merci.
soient $A$ un alphabet et $L \subseteq A^{*}$ un langage. l'équivalence syntaxique $\approx_{L}$ est définie, pour tout $u,v \in A^{*}$, par $u \approx_{L} v$ si $$
\forall w,w' \in A^{*},\quad wuw' \in L \iff wvw'\in L
$$ Montrer que $\approx_{L}$ a un nombre fini de classes d'équivalence ssi $L$ est reconnaissable.
Note: j'arrive à faire la première implication, j'ai un souci avec la réciproque, si quelqu'un pouvait m'aider, merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses