Théorie des langages (récurrence)

leeween

Bonjour, j'ai une question à propos d'un exercice, je dois démontrer la question suivante.

 On définit le miroir d’un mot w ∈ Σ ∗ par récurrence sur la longueur de w de la manière suivante :
si w = e, alors w^R = e; sinon, il existe σ ∈ Σ et v ∈ Σ ∗ tels que w = σv et w^R = (v^R)σ.
Démontrer que cette définition est équivalente à la définition suivante :
si w = e, alors w^R = e; sinon, il existe σ ∈ Σ et v ∈ Σ ∗ tels que w = vσ et w^R = (σv)^R

Je pense que je dois faire un récurrence mais je suis pas sûre >.<

Thierry Poma

leeween : bonjour. Le début de ton énoncé est faux. Le miroir ou transposé d'un mot est mal défini. Sinon, comment faire autrement ?

Thierry Poma

Ta définition est juste. J'avais mal lu.

Thierry Poma

Soit $\Sigma$ un alphabet et $\Sigma^*=\mathrm{Mo}(\Sigma)$ le monoïde libre construit sur $\Sigma$ de neutre $e$. Soit $w\in\Sigma^*$. Si $w=e$, alors $w^R=e$. Si $w\in\Sigma$, alors $w^R=w$. Sinon, $w\in\Sigma^*$ pour lequel il existe $b\in\Sigma$ et $w'\in\Sigma^*$ tel que $w=bw'$, et $w^R=w'^Rb$.

GaBuZoMeu

Bonjour,

Pour ta récurrence, elle se fait bien en commençant par examiner  les cas des mots de longueur inférieure ou égale à 2, puis par hérédité.

[Utilisateur supprimé]

La deuxième définition n'est pas bonne, c'est probablement juste un problème de parenthesage.
Aussi, le monoïde libre étant muni d'une relation ensembliste bien fondé ($<$ := $\{ (a,b)\vert longueur(a)<longueur(b)\}$), la première définition en est une par recursion transfinie (c'est aussi ce qu'on veut pour la deuxième définition), et pour montrer le résultat voulu (que les deux fonctions définies sont égales) après correction de l'énoncé, on utilise le théorème d'induction.

NB. J'évitais ce fil parce que je pensais que c'était un spam comme le précédent fil de @leeween qui ne s'est toujours pas excusé pour avoir spammé le forum.

NB. Pour éviter les problèmes de parenthesage on peut travailler totalement sans parenthèses en utilisant des écritures préfixes : $\star Rv\sigma$, $\star \sigma Rv$, $R\star \sigma v$

NB. Ce serait bien de ne pas noter les deux fonctions définies avec le même nom avant d'avoir montré leur égalité. L'énoncé de l'exercice est assez mal rédigé.

[Utilisateur supprimé]

Bon, j'ai mis des tas de remarques, en espérant que c'est utile et que ce fil n'est pas un autre spam.

Edit1. Une façon archi simple de prouver que les deux fonctions définies sont égales est de remarquer que les deux fonctions sont des morphisme d'un monoïde libre vers son opposé, il suffit ensuite de remarquer que les restrictions des deux fonctions sur la base sont la même chose. CQFD.

Edit2. Une meilleure façon c'est d'abord de définir la fonction miroir comme l'unique prolongement de l'identité de la base du monoïde en morphisme du monoïde sur son opposé. Ensuite, on vérifie que la fonction miroir vérifie les définitions par recursion transfini des deux fonctions de l'exercice. CQFD.