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:

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)*

Exercice 3. Les homomorphismes

TD1 TD2 TD3 TD4

Retour