Langage rationnel et miroir

[LeCaRiBoU]

Bonjour,

J'ai un petit problème : si j'ai un langage L rationnel, comment puis-je prouver que le langage miroir de L est rationnel ?
Merci d'avance.

En prépa, ce genre de problème se résout presque toujours de la même façon.
Soit L le langage initial:
1) D'après Kleene, il existe un automate A qui reconnaît L.
2) Tu fabriques "à la main" un automate A' qui reconnaît le miroir des mots que reconnaît A.
3) Donc d'après Kleene, le langage miroir de L est reconnaissable.

Je te laisse faire la partie 2, c'est la seule partie qui change d'un problème à l'autre (Dans le cas présent, on aurait pu aussi répondre par récurrence en construisant "à la main" l'expression rationnelle du langage miroir, mais je trouve plus pratique de travailler avec des automates, et au moins la méthode est relativement générale).

[sunmat]

Il doit y avoir une méthode par induction sur les expressions rationnelles, aussi.
Soit E une expression rationnelle, soit m(E) le miroir de cette expression (i.e., l'expression représentant le langage miroir du langage généré par E). On peut définir m de la manière suivante :

• 1) $ m(a) = a $ si a est un symbol de l'alphabet considéré

• 2) $ m(E_1.E_2) = m(E_2).m(E_1) $

• 3) $ m(E_1+E_2) = m(E_1)+m(E_2) $

• 4) $ m(E*) = m(E)* $

Bon il reste à prouver qu'on définit bien le miroir de cette façon...

EDIT: je pense qu'on peut dire que 1) et 3) sont triviaux, et 4) découle de 2). 2) est moins trivial. On peut dire que si le mot u appartient à $ E_1.E_2 $ alors il s'écrit forcément $ u = v.w $ (pas forcément de manière unique) avec v appartenant à $ E_1 $et w appartenant à $ E_2 $. Le miroir de u peut s'écrire $ u' = w'.v' $ avec w' le miroir de w et v' le miroir de v. Par induction, w' appartient à $ m(E_2) $ et v' appartient à $ m(E_1) $ donc u' appartient à $ m(E_2).m(E_1) $.

[LeCaRiBoU]

Oui c'est ce que j'entendais par "répondre par récurrence en construisant "à la main" l'expression rationnelle du miroir", faire une induction structurelle quoi

Pour la demo du 2), c'est le genre de truc qui est évident "avec les mains" mais horrible à formaliser ^^ (À vrai dire je pense que j'aurais tenté un "Il est évident que 2) est vrai" aux concours, même si c'est mal...)

[sunmat]

Oui, je me demande d'ailleurs comment on avait prouvé ça quand j'étais en prépa...

EDIT: Je viens de jeter un oeil dans le Sakarovitch ("Elements de théorie des automates"). Page 64, on trouve :

On appelle automate transposé de A l'automate obtenu en "renversant" toutes les flèches dans $ A $ - i.e., en échangeant l'origine et l'extrémité de chaque transition, et en échangeant les états initiaux et finals; on le note $ A^t $.

Puis plus loin:

L'étiquette d'un calcul de $ A^t $ est, à l'évidence, l'image miroir de l'étiquette du calcul correspondant dans $ A $;

Pas de preuve autre que celle-ci. Cela dit la preuve est relativement simple, quand on y réfléchit. Il suffit de poser $ u=a_1a_2...a_n $ reconnu par $ A $, donc il existe une succession d'états $ e_1e_2...e_{n+1} $ tels que $ e_1 $ est un état initial, $ e_{n+1} $ est final et pour tout k, $ (e_k,e_{k+1}) $ est une transition valide dans $ A $. On conclut ensuite en inversant la séquence d'état, en montrant que cette nouvelle séquence est valide dans $ A^t $ et qu'elle calcule le mot $ a_n...a_1 $, miroir de u.