TD7 - Automates et Langages - RICM

Lemme de gonflement

Exercice 1. 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 palindrome
• déduire la contradiction et terminer la preuve

Exercice 2. 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 variables d'ADA
• les expressions arithmétiques de ADA
• les programmes syntactiquement correctes en ADA
• les expressions booléennes d'ADA
• .....