TD7 - Automates et Langages - RICM

Propriétés des langages réguliers

Exercice 1. Intersection des langages et produit des automates.

Construire l'automate pour (a+ab)*b* ^ ((a+b)(a+b))*.

Exercice 2. Les homomorphismes


Lemme de gonflement

Exercice 3. Preuve de non-régularité

Prouver que le langage P de tous les palyndromes sur {a,b} n'est pas régulier (w est un palyndrome si w=wR). Indication:

Exercice 4. Le bon grain et l'ivraie

Lesquels des langages suivants sont réguliers? Justifiez votre réponse.

TD1 TD2 TD3 TD4 TD5 TD7

Retour