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
- 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 ferméture de langages réguliers
par rapport aux 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:
- supposer le contraire
- prendre un mot w concret assez long dans P
- montrer que la version gonflée de ce mot est dans P
(par "pumping lemma")
- montrer que cette même version gonflée n'est pas un
palyndrome
- déduire la contradiction et términer la preuve
Exercice 4. Le bon grain et l'ivraie
Lesquels des langages suivants sont réguliers? Justifiez
votre réponse.
- les mots sur {a,b} sans trois a consécutifs
- les mots sur {a,b} avec autant de a que de b
- les mots sur {a,b} dont la longueur est impaire
- les mots sur {a,b} dont la longueur est un nombre premier
- les mots sur {a,b} de longueur 1000000
- les programmes syntactiqument correctes en ADA
- les variables d'ADA
- les expressions booléennes d'ADA
TD1 TD2 TD3 TD4 TD5 TD7
Retour