Exercices 2

• Le mot vide e est une expression régulière.
• Chaque élément a dans A est une expression régulière.
• Si R et S sont des expressions régulières, alors RS (concaténation), R|S (choix) et {R} sont des expressions régulières.

Exercice 5

• Donnez une grammaire régulière décrivant le même langage.

Exercice 6

• Quel langage est décrit par l'expression régulière ab { ab } a?
• Donnez une grammaire régulière décrivant le même langage.

Exercice 7

• Quel langage est décrit par la grammaire suivante?

           S  -->  A { B | C }
           A  -->  a
           B  -->  b
           C  -->  c
        

• Transformez-la en une grammaire régulière décrivant le même langage.
• Donnez une expression régulière décrivant le même langage.