Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Feuille d'exercices 5

Des automates aux expressions

Élimination d'états dans différents ordres, résolution d'équations par le lemme d'Arden, et une expression pour les multiples de 3 en binaire. Chapitre 5.

Sauf mention contraire, $\Sigma = \{a, b\}$.

Corrigé
  1. On ajoute $I_0 \xrightarrow{\varepsilon} P$ et $P \xrightarrow{\varepsilon} F$ (on appelle $I_0$ le nouvel initial pour ne pas le confondre avec l'état I).
  2. Supprimer I : prédécesseur P, successeur P, boucle $b$. Déviation $(P, P)$ : $b + ab^*a$, une boucle sur P. Supprimer P : prédécesseur $I_0$, successeur $F$, boucle $b + ab^*a$. Déviation : $\varepsilon\,(b + ab^*a)^*\,\varepsilon$. L'expression est $(b + ab^*a)^*$.
  3. Un mot ayant un nombre pair de $a$ se découpe en morceaux : chaque $b$ lu hors d'une paire de $a$ est un morceau $b$ ; chaque paire de $a$ consécutifs (dans l'ordre des $a$ du mot), avec les $b$ qui les séparent, est un morceau $ab^*a$.
Corrigé

On normalise avec $I \xrightarrow{\varepsilon} 0$ et $2 \xrightarrow{\varepsilon} F$.

  1. Supprimer 1 : prédécesseurs 0 et 2 (par $a$), successeur 2 (par $b$), boucle $a$. $(0, 2)$ : $aa^*b = a^+b$ ; $(2, 2)$ : $a^+b$, une boucle sur 2. Supprimer 2 : prédécesseur 0 ; successeurs 0 (par $b$) et $F$ ; boucle $a^+b$. $(0, 0)$ : $b + a^+b(a^+b)^*b$ ; $(0, F)$ : $a^+b(a^+b)^*$. Supprimer 0 : $(I, F)$ :
$$\big(b + a^+b(a^+b)^*b\big)^*\,a^+b(a^+b)^*$$
  1. Supprimer 2 : prédécesseur 1 (par $b$) ; successeurs 1 (par $a$), 0 (par $b$), $F$. $(1, 1)$ : $a + ba$ ; $(1, 0)$ : $bb$ ; $(1, F)$ : $b$. Supprimer 0 : prédécesseurs $I$ (par $\varepsilon$) et 1 (par $bb$) ; successeur 1 (par $a$) ; boucle $b$. $(I, 1)$ : $b^*a$ ; $(1, 1)$ : $a + ba + bbb^*a$. Supprimer 1 : $(I, F)$ :
$$b^*a\,(a + ba + bbb^*a)^*\,b$$
  1. Les deux dénotent le même langage, mais ne se ressemblent pas. Dans la seconde, $a + ba + bbb^*a = (\varepsilon + b + bbb^*)a = b^*a$. Elle devient $b^*a(b^*a)^*b = (b^*a)^+b$, et comme $(b^*a)^+$ dénote les mots qui finissent par $a$, c'est $(a + b)^*ab$.
Corrigé
  1. $X_P = bX_P + aX_I + \varepsilon$ (P est final) et $X_I = bX_I + aX_P$.
  2. Arden sur la seconde, avec $K = b$ et $L = aX_P$ : $X_I = b^*aX_P$. On substitue : $X_P = bX_P + ab^*aX_P + \varepsilon = (b + ab^*a)X_P + \varepsilon$. Arden : $X_P = (b + ab^*a)^*$. C'est le même résultat.
  3. Avec $K = a + \varepsilon$, $X = K^*b = a^*b$ est solution, mais $X = (a + b)^*$ aussi : $(a + \varepsilon)(a + b)^* + b = (a + b)^*$, car $\varepsilon \cdot (a + b)^*$ contient déjà tout. L'unicité est perdue : quand $\varepsilon \in K$, l'équation « laisse passer » n'importe quel mot en le préfixant par $\varepsilon$.
Corrigé
  1. Transitions : $0 \xrightarrow{0} 0$, $0 \xrightarrow{1} 1$, $1 \xrightarrow{0} 2$, $1 \xrightarrow{1} 0$, $2 \xrightarrow{0} 1$, $2 \xrightarrow{1} 2$. Supprimer 2 : prédécesseur 1, successeur 1, boucle $1$ : boucle $01^*0$ sur 1. Supprimer 1 : prédécesseur 0, successeur 0, boucle $01^*0$ : boucle $1(01^*0)^*1$ sur 0. Avec la boucle $0$ déjà présente, et 0 initial et final :
$$\big(0 + 1(01^*0)^*1\big)^*$$
  1. $11$ : $1 \cdot 1$, avec $(01^*0)^*$ vide, accepté. $110$ : $11$ puis $0$, accepté. $1001$ : $1 \cdot (00) \cdot 1$, avec $01^*0 = 00$, accepté. $101$ : il faudrait lire $1$, puis un morceau de $(01^*0)^*$, puis $1$ ; le milieu serait $0$ seul, qui n'est pas de la forme $01^*0$. Refusé, et $5$ n'est pas un multiple de 3.