TD 1 - Langages réguliers

exercice 1. Langages réguliers

Montrer que les langages suivants sont réguliers.

1. \( \setcompr{w \in\set{\tt a, b}^\star}{w\text{ commence par }{\tt ab}\text{ et finit par }{\tt bb}}\)
   Solutions :
   • non-déterministe :
   • déterministe :
2. \(\setcompr{w \in\set{\tt a, b}^\star}{w\text{ a (au moins) une occurence de }{\tt bb}}\)
   Solutions :
   • non-déterministe :
   • déterministe :
3. \(\setcompr{w \in \set{\tt a, b}^\star}{w\text{ a exactement une occurence de }{\tt bb}}\)
   Solution :
4. \(\setcompr{w \in \set{\tt a, b}^\star}{w\text{ ne contient pas 3 occurences successives de la même lettre}}\)
   Solution :
5. \(\setcompr{w \in \set{\tt a, b}^\star}{w\text{ contient un nombre impair de }{\tt a}}\)
   Solution :
6. \(\setcompr{w \in \set{\tt a, b}^\star}{w\text{ ne contient pas la lettre }{\tt b}}\)
   Solutions :
   • déterministe :
   • complet :