Exercices

Exercices d'application

Exercice

Si \(L = \{ a \}\) et \(L' = \{ b \}\), déterminer les langages suivants : \(L^*, L'^*, LL', L+L', (LL')^*, (L+L')^*, L^*L'^*, L^*+L'^*\).

Exercice

Déterminer des expressions régulières dénotant les langages suivants.

1. L'ensemble des mots sur \(\{ a,b,c\}\) contenant au moins un a et au moins un b.
2. L'ensemble des mots sur \(\{ a,b\}\) dont la dixième lettre en partant de la fin est un \(b\).
3. L'ensemble des mots sur \(\{a,b\}\) contenant au plus deux b consécutifs.
4. L'ensemble des mots sur \(\{a,b\}\) tels qu'aucun facteur \(aa\) ne soit précédé d'un facteur \(bb\). \(aabaabb\) convient mais pas \(aabbaa\).
5. L'ensemble des mots sur \(\{a,b\}\) dont le nombre de \(a\) est divisible par \(5\).

Exercice

Décrire informellement les langages dénotés par les expressions régulières suivantes.

1. \((a|\epsilon)(aa^*b)^*a^*\)
2. \((a^*b^*)^* aaa (a|b)^*\)
3. \((a|ba)^* b^*\)

Exercice

Montrer qu'il n'existe que deux langages dont l'étoile est finie.

Exercice

Déterminiser les automates suivants :

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Exercice

Pour chacune des expressions régulières suivantes, déterminez un automate fini non déterministe avec transitions spontanées qui reconnaît le langage qu'elle dénote, éliminez les transitions spontanées pour en déduire un automate non déterministe, puis, déterminez un automate directement par Berry-Sethi.

1. \(a b^*\)
2. \((a|b)ab\)
3. \(aa(a|b)^*\)

Exercice

On considère la table de transition :

\[ \begin{array}{rc|cc} & & a & b \\ \rightarrow & q_1 & q_2 & q_1 \\ & q_2 & q_3 & q_1 \\ * & q_3 & q_3 & q_2 \end{array} \]

1. Déterminer la matrice des expressions régulières \(R^{(0)}\).
2. Déterminer la matrice des expressions régulières \(R^{(1)}\) en la simplifiant.
3. Déterminer la matrice des expressions régulières \(R^{(2)}\) en la simplifiant.
4. En déduire une expression régulière dénotant le langage reconnu par l'automate.
5. Appliquer la méthode d'élimination des états pour obtenir une expression régulière.

Exercice

Montrer que les langages suivants ne sont pas réguliers.

1. L'ensemble des expressions bien parenthésées : \(P\) défini par induction avec \(\epsilon \in P\), \(\forall e_1, e_2\in P, e_1 e_2 \in P\) et \(\forall e \in P, (e) \in P\).
2. \(\enscomp{a^n b c^n}{n \ge 1}\).
3. \(\enscomp{a^n b^m c^n}{n, m \in \N}\)
4. \(\enscomp{a^n b^m}{n \le m}\)
5. \(\enscomp{a^n b^{2n}}{n \ge 1}\)

Exercice

Même exercice que le précédent, mais les preuves sont plus délicates.

1. \(\enscomp{a^{n^2}}{n \in \N}\)
2. \(\enscomp{a^{2^n}}{n \in \N}\)
3. \(\enscomp{w \in\Sigma^*}{\exists n \in \N, |w| = n^2}\)
4. \(\enscomp{w^2}{w \in \Sigma^*}\), où \(\Sigma\) contient au moins deux lettres
5. \(\enscomp{w \in \{0,1\}^*} {w\text{ est l'écriture d'un premier en binaire}}\)
6. \(\enscomp{a^i b^j}{ i \wedge j = 1}\).

Lemme d'Arden

Théorème

Soit \(A,B\) deux langages sur \(\Sigma\).

Le langage \(L = A^* B\) est le plus petit langage solution de l'équation

\[ X = A X \cup B \]

De plus, si \(\epsilon \not \in A\), cette solution est unique.

Exercice

Démontrer ce théorème.

Explosion exponentielle de la déterminisation

Exercice

On va montrer dans cet exercice qu'il est possible de trouver un automate à \(n+1\) états dont le déterminisé par l'automate des parties, même émondé, contient au moins \(2^n\) états.

1. Soit \(n \in \N^*\), définir un automate fini non-déterministe à \(n+1\) états sur l'alphabet \(\{a,b\}\) qui reconnaît les mots de la forme \(waw'\) avec \(|w'|=n-1\), c'est-à-dire les mots qui ont un \(a\) en \(n\)-ième position en partant de la fin.
2. Montrer que le déterminisé de cet automate contient au moins \(2^n\) états.

Miroir d'un langage

Exercice

Soit \(\Sigma\) un alphabet fini.

Si \(w = a_1 \dots a_n \in \Sigma^*\) est un mot non vide, on note \(w^R = a_n \dots a_1\) le mot \(w\) lu à l'envers, et on pose \(\epsilon^R = \epsilon\). On l'appelle le miroir de \(w\).

Soit \(L \subset \Sigma^*\) un langage. On note \(L^R = \enscomp{w^R}{w \in L}\) le miroir de \(L\).

1. On suppose que \(\Sigma\) contient au moins deux lettres. Montrer que le langage des palindromes

   \[P = \enscomp{w\in \Sigma^*}{w = w^R}\]

   n'est pas régulier. Que se passe-t-il si \(\Sigma\) ne contient qu'une lettre ?

2. On va donner deux preuves du fait que les langages réguliers sont stables par miroir.

   1. Soit \(L\) un langage régulier et \(A\) un automate reconnaissant \(L\), en déduire un automate non déterministe avec transitions spontanées \(A^R\), en renversant les transitions, permettant de reconnaître \(L^R\).
   2. Soit \(e\) une expression régulière, déterminer par induction une expression régulière \(e^R\) dénotant \(\mathop{lang}(e)^R\).

Exercices de colle

Moitié d'un langage

Exercice

Soit \(L \subset \Sigma^*\), on note

\[ \frac{1}{2} L = \enscomp{ u \in \Sigma^* } { \exists v \in \Sigma^*, |u| = |v| \text{ et } uv \in L} \]

Montrer que si \(L\) est régulier, alors \(\frac{1}{2} L\) est régulier.

Preuve

Soit \(A = (Q,\Sigma,\delta,i,F)\) un automate déterministe reconnaissant \(L\). L'idée ici est que si \(u \in \frac{1}{2} L\) et que \(\delta^*(i,u) = q\), unique car \(A\) est déterministe, alors il existe un chemin de longueur \(|u|\) tel que \(q \leadsto q'\in F\).

Donc, pour déterminer un automate reconnaissant \(\frac{1}{2} L\), on peut simuler tous les chemins possibles depuis tous les états en même temps qu'on lit \(u\). Quand on a fini de lire, on n'a qu'à vérifier si dans les chemins énumérés il y en a un issu de \(q\) qui aboutit sur un état dans \(F\).

On va ainsi noter \(Q = \{q_1,\dots,q_n\}\) et supposer que \(i = q_1\). On suppose de plus que \(A\) est complet, quitte à ajouter un état puits.

On pose l'automate non déterministe

\[A' = (Q \times Q^n, \Sigma, \delta', \{(q_1,(q_1,\dots,q_n))\}, F')\]

avec

\[\forall (q,(s_1,\dots,s_n)) \in Q \times Q^n, \forall a \in \Sigma, \delta'( (q,(s_1,\dots,s_n)), a) = \enscomp{ (\delta(q,a), (\delta(s_1,b), \dots, \delta(s_n,b))) }{b \in \Sigma}\]

ce qui revient à faire exactement comme \(A\) sur la première composante et à faire tous les chemins possibles sur la seconde de manière non déterministe. On remarque, par une récurrence immédiate sur \(|u|\), que

\[ \delta'^*((q_1,(q_1,\dots,q_n)), u) = \enscomp{ (\delta^*(q_1,u), (\delta^*(q_1,v), \dots, \delta^*(q_n,v)))}{v \in \Sigma^*, |v| = |u|} \]

Pour les états finaux, on pose

\[ F' = \enscomp{ (q_j,(s_1, \dots, s_n)) }{ j \in \range{1}{n}, s_j \in F} \]

ce sont les états tels qu'on puisse atteindre un état final depuis ceux-ci en prenant le même temps que pour arriver sur l'état.

Soit \(u \in \Sigma^*\),

\[ \begin{array}{rcl} u \in \mathop{lang}(A') & \iff & \delta'^*( (q_1,(q_1,\dots,q_n)), u) \cap F' \neq \emptyset \\ & \iff & \exists v \in \Sigma^*, |v| = |u|\text{ et } (\delta^*(q_1,u), (\delta^*(q_1,v), \dots, \delta^*(q_n,v))) \in F' \\ & \iff & \exists v \in \Sigma^*, |v| = |u|\text{ et } \delta^*(\delta^*(q_1,u),v) \in F \\ & \iff & \exists v \in \Sigma^*, |v| = |u|\text{ et } \delta^*(q_1,uv) \in F \\ & \iff & \exists v \in \Sigma^*, |v| = |u|\text{ et } uv \in L \\ & \iff & u \in \frac{1}{2} L \end{array} \]

Exercice

Soit \(L, L' \subset \Sigma^*\), on note

\[ L : L' = \enscomp{ u \in L}{\exists v \in L', |u|=|v| } \]

Montrer que si \(L\) et \(L'\) sont réguliers, alors \(L:L'\) est régulier.

Preuve

C'est un peu comme l'exercice précédent, on va considérer \(A = (Q, \Sigma, \delta, i, F)\) et \(A' = (Q', \Sigma, \delta', i', F')\) déterministes et complets reconnaissant respectivement \(L\) et \(L'\), et simuler tous les chemins possibles dans \(A'\) pendant qu'on lit un mot dans \(A\). Si on peut aboutir en même temps sur deux états finaux, on aura reconnu le mot.

On pose donc l'automate non déterministe \(A'' = (Q \times Q', \Sigma, \delta'', \{(i,i')\}, F \times F')\) et

\[ \delta''( (q,q'), a ) = \enscomp{ (\delta(q,a), \delta'(q',b)) }{b \in \Sigma } \]

On a ainsi, par une récurrence immédiate sur \(|u|\), \(\delta''^*((i,i'),u) = \enscomp{ (\delta^*(i,u), \delta'^*(i',v)) }{v \in \Sigma^*, |v| = |u| }\), d'où

\[ \begin{array}{rcl} u \in \mathop{lang}(A'') & \iff & \delta''^*((i,i'),u) \cap F \times F' \neq \emptyset \\ & \iff & \enscomp{ (\delta^*(i,u), \delta'^*(i',v)) }{v \in \Sigma^*, |v| = |u| } \cap F \times F' \neq \emptyset \\ & \iff & \exists v \in \Sigma^*, |v| = |u| \text{ et } \delta^*(i,u) \in F, \delta'^*(i',v) \in F' \\ & \iff & u \in L \text{ et }\exists v \in L', |u| = |v| \\ & \iff & u \in L : L' \end{array} \]

Exercice

Soit \(L \subset \Sigma^*\).

1. Soit \(a \in \Sigma\), on pose \(L \backslash a = \enscomp{w \in \Sigma^*}{wa \in L}\).
2. \(\min(L) = \enscomp{w \in L}{\forall w = uv, v \neq \epsilon \Rightarrow u \not\in L}\) les mots de \(L\) dont aucun préfixe propre n'est dans \(L\).
3. \(\max(L) = \enscomp{w \in L}{\forall u \in \Sigma^*, u \neq \epsilon \Rightarrow w u \not\in L}\) les mots de \(L\) qui ne sont préfixes propres d'aucun mot de \(L\).

Montrer que si \(L\) est régulier, alors \(L\backslash a, \min(L)\) et \(\max(L)\) sont réguliers.

Preuve

Dans tous les cas, on va procéder de la même manière : on part d'un AFD complet \(A\) reconnaissant \(L\) et on en déduit un AFD \(A'\) reconnaissant le langage qui nous intéresse.

Soit \(A = (Q, \Sigma, \delta, i,F)\) reconnaissant \(L\).

Construction 1 On pose \(A' = (Q, \Sigma, \delta, i, F')\) où

\[ F' = \enscomp{q\in Q}{\delta(q,a) \in F} \]

Montrons que \(\mathop{lang}(A') = L \backslash a\) :

Soit \(w \in \Sigma^*\),

\[ \begin{array}{rcl} w \in \mathop{lang}(A') & \iff & \delta^*(i,w) \in F' \\ & \iff& \delta(\delta^*(i,w),a) = \delta^*(i,wa) \in F \\ & \iff & wa \in L\\ & \iff & w \in L \backslash a \end{array} \]

On a bien \(\mathop{lang}(A') = L \backslash a\) donc ce langage est régulier.

Construction 2 On pose \(A' = (Q, \Sigma, \delta', i, F)\) où

\[\forall q \in Q \backslash F, \forall a \in \Sigma, \delta'(q,a) = \delta(q,a)\]

et \(\delta'(q,a)\) n'est pas défini pour \(q \in F\). On supprime ainsi les transitions issues d'un état final.

Comme \(q \rightarrow q'\) dans \(A'\) entraîne \(q \not \in F\), on remarque qu'un chemin dans \(A'\) passe au plus par un état final, et nécessairement comme dernier état du chemin. Ainsi, \(\delta'^*(i,w)\) est défini et dans \(F\) si et seulement si \(\delta^*(i,w) \in F\) et aucun état \(\delta^*(i,u)\), pour \(u\) préfixe propre de \(w\), n'est dans \(F\).

Soit \(w \in \Sigma^*\),

\[ \begin{array}{rcl} w \in \mathop{lang}(A') & \iff & \delta'^*(i,w) \in F \\ & \iff & \delta^*(i,w) \in F \text{ et } \forall w = uv, v \neq \epsilon \Rightarrow \delta^*(i,u) \not \in F \\ & \iff & w\in L \text{ et } \forall w = uv, v \neq \epsilon \Rightarrow u \not \in L \\ & \iff & w \in \min(L) \end{array} \]

On a bien \(\mathop{lang}(A') = \min(L)\) donc ce langage est régulier.

Construction 3 On pose \(A' = (Q,\Sigma,\delta,i,F')\) où

\[F' = \enscomp{q \in F}{\forall u \in \Sigma^*, u \neq \epsilon \Rightarrow \delta^*(q,u) \not\in F}\]

les états finaux depuis lesquels aucun chemin non vide ne mène à un état final (y compris \(q\) lui-même : un état final sur un cycle n'est pas dans \(F'\)).

Soit \(w \in \Sigma^*\), on va noter \(q = \delta^*(i,w)\).

Supposons \(q \in F'\) et soit \(u \in \Sigma^*\) tel que \(u \neq \epsilon\). Par définition de \(F'\), \(\delta^*(q,u) = \delta^*(i,wu) \not\in F\) donc \(wu \not \in L\). Comme de plus \(q \in F\), on a \(w \in L\) et ainsi \(w \in \max(L)\).

Réciproquement, si \(w \in \max(L)\), on a \(q \in F\) car \(w \in L\). Soit \(u \in \Sigma^*\) tel que \(u \neq \epsilon\) : on a \(\delta^*(q,u) = \delta^*(i,wu)\) or \(wu \not \in L\) par hypothèse sur \(w\). Donc \(\delta^*(q,u) \not\in F\). On vient de montrer que \(q \in F'\).

On a donc,

\[w \in \mathop{lang}(A') \iff q \in F' \iff w \in \max(L)\]

On a bien \(\mathop{lang}(A') = \max(L)\) donc ce langage est régulier.