Bonjour à tous, j'ai besoin d'aide pour un exercice d'informatique théorique. Voici l'énoncé :

Soit l'alphabet {a, b} et définissons la relation "~" sur les mots de {a, b}* de la manière suivante : u ~ v si et seulement si u et v contiennent le même nombre de "a" et le même nombre de "b". Par exemple, "abaa" ~ "baaa" et "ababb" ~ "bbaab".

Si M est un langage sur l'alphabet {a, b}, on définit maintenant :

K_M = { w | il existe un v tel que w ~ v et v appartient à M }.

Autrement dit, un mot w appartient à K_M si ses lettres peuvent être réordonnées pour former un mot de M.

L'exercice demande de montrer que, si M est un langage régulier, alors K_M est toujours un langage non-contextuel.

De mon côté, j'ai essayé de partir avec des exemples simples, comme M = (ab)^*. Dans ce cas, K_M devient un langage non-contextuel car il doit accepter les mots de la forme aⁿbⁿ, avec n appartenant aux entiers naturels. J'observe aussi que la définition de "~" implique de devoir compter le nombre de "a" et de "b", ce qui est possible avec un langage non-contextuel, mais je n'arrive pas à fournir une preuve concrète.

Merci de votre aide !