TD5 - Automates et Langages - RICM
Opérations sur des langages réguliers
Exercice 1. Opérations booléennes et régulières.
1. Soient L = b(a+b)*b et M= (a+b)*ab - deux langages sur {a,b}. Pour commencer construisez les automates qui reconnaissent L et M.
Trouvez les expressions et/ou les automates pour les langages suivants:
- L U M, LM, L*
- ¬L (complément), ¬M
- LÇM (a) en passant par les compléments; (b) en construisant l'automate produit
- L-M
2. Construisez l'automate et l'expression régulière pour le langage de tous les mots ne contenant pas aba (exercice 2, TD3, vous vous rappelez ?).
3. Construisez l'automate pour (a+ab)*b* Ç ((a+b)(a+b))*.
Exercice 2. Le miroir.
On utilise la notation wR pour le mot w "renversé". Par exemple, papaR=apap. Cette opération peut être étendue sur les langages - par exemple ((ab)*)R=(ba)*
- Trouvez l'expression régulière pour ((ab)*(a+bbba)+a*b*)R
- Trouvez les automates pour les langages de l'exercice 1 renversés
- Prouvez que si L est régulier, alors LR est aussi régulier (les langages réguliers sont fermés par rapport au renversement)
Exercice 3. Les homomorphismes
- Construire l'automate pour le langage L=(a+bc)*c*
- l'homomorphisme f est défini comme suit: f(a)=0, f(b)=0, f(c)=1
- calculer f(abbacb) (il faut le définir d'abord)
- écrire l'expression pour f(L)
- construire l'automate pour f(L)
- mêmes questions pour g(a)=0, g(b)=00, g(c)=000
- formuler le théorème de fermeture de langages réguliers par rapport aux homomorphismes
TD1 TD2 TD3 TD4
Retour