Eléments d’Informatique Théorique

Série 5 Expressions Régulières

Exercice 5.1 Construire les AF correspondant aux expressions régulières qui suivent :

1. 10 + (0 + 11) 0^{∗}1

2. 01(((10)^{∗} + 111)^{∗} + 0)^{∗}1

3. ((0 + 1)(0 + 1))^{∗} + ((0 + 1)(0 + 1)(0 + 1))^{∗} Exercice 5.2 Donner les expressions régulières correspondant aux AF suivants :

0  0 1  1  1 0 q_{1}  q_{2}  q_{3}

0  0  0 1 1 1 q_{1} q_{2}  q_{3}

Exercice 5.3 Soient r, s et t des expressions régulières. Démontrez les égalités suivantes:

a) r + s = s + r  b) (r + s) + t = r + (s + t) c) (rs)t = r(st)
d) r(s + t) = rs + rt e) (r + s)t = rt + st  f) ∅^{∗} = ϵ
g) (r^{∗})^{∗} = r^{∗}  h) (ϵ + r)^{∗} = r^{∗}  i) (r^{∗}s^{∗})^{∗} = (r + s)^{∗}

Exercice 5.4 Confirmer ou infirmer les égalités suivantes

\begin{matrix}a) & (rs + r)^{∗}r = r(sr + r)^{∗} \\ b) & s(rs + s)^{∗} = rr^{∗}s(rr^{∗}s)^{∗} \\ c) & (r + s)^{∗} = r^{∗} + s^{∗} \end{matrix}

Exercice 5.5 Donnez les grammaires régulières pour les langages exprimés par les expressions régulières :

1. (0 + 1)^{∗}00(0 + 1)^{∗}

2. 0^{∗}(1(0 + 1))^{∗}

3. (((01 + 10)^{∗}11)^{∗}00)^{∗}