MP/MP*: Option Informatique
DS du jeudi 17 février 2005
Étude d'un opérateur conservant le caractère rationnel



Choisissons comme alphabet {a,b}. Notons L l'ensemble des mots qui contiennent le facteur ab, et définissons sur L une fonction f comme suit: f(u) se déduit de u en remplaçant la première occurrence du facteur ab par ba.

La question centrale de ce problème consiste à prouver que si M est un langage rationnel contenu dans L, alors f(M) est lui aussi rationnel.