Bonsoir camarades,
Peut-être pourriez vous m'aider pour la question 2 sur l'image ci-jointe. Prenez note que ''L'ensemble des palindromes'' doit être lu comme ''l'ensemble des facteurs palindromiques''
https://ibb.co/y0zWF5s
Pour le 2a), j'ai fait une preuve par récurrence.
Je suppose que Pal(L) = {eps, a, b, c}
Initialisation:
Je teste n=0 => u^0 = epsilon
Je teste n=1 => u^1 = epsilon, a,b,c
Hérétité
On a : u^(n+1)= (u^n) u
Par l'hypothèse de recurrence u^n possède {eps, a, b, c} comme facteurs palindromiques et pareillement pour u.
J'en conclue que l'hypothèse de départ est vraie.
Est-ce correct?
La question 2b) me pose plus de soucis, quel est le complémentaire de {aba, cbc, bab, cac, aca, bcb, aa, bb, cc} ?
Peut-on séparer le complément de la concaténation? Ainsi les Σ∗ deviendraient des Epsilon et le problème serait légèrement simplifié.
Avez vous des pistes de solution?
Merci beaucoup de prendre de votre temps!
Bonne soirée à vous