TD6 - Automates et Langages - RICM

Propriétés des langages réguliers

Exercice 1. Préfixes, suffixes, infixes...

L'ensemble des préfixes du mot abb est pref(abb) = {epsilon, a, ab, abb}. On peut généraliser l'opération pref sur les langages :

On peut aussi définir les suffixes et les infixes d'une façon similaire :

suf(abb) = {epsilon, b, bb, abb},
suf({aba, ac}) = {epsilon, a, ba, aba, c, ac},
inf(abb) = {epsilon, a, b, ab, bb, abb},
inf({aba, ac}) = {epsilon, a, b, c, ab, ba, ac, aba}.

• Construisez les automates et les expressions régulières pour pref(L), suf(L) et inf(L) où L=(a+bc)*c* (le langage de l'exercice 4 du TD5).
• Prouvez que si L est régulier alors pref(L), suf(L) et inf(L) sont réguliers aussi.

Lemme de gonflement

Exercice 2. Preuve de non-régularité

Prouver que le langage P de tous les palindromes sur {a,b} n'est pas régulier (w est un palindromes si w=w^R).

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 palindromes
• déduire la contradiction et terminer la preuve

Exercice 3. 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 syntactiquement correctes en ADA
• les variables d'ADA
• les expressions booléennes d'ADA

TD1 TD2 TD3 TD4

Retour