diff options
| -rw-r--r-- | controle-20190205.tex | 45 |
1 files changed, 25 insertions, 20 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex index 3802f51..a3e6f08 100644 --- a/controle-20190205.tex +++ b/controle-20190205.tex @@ -411,37 +411,42 @@ suivantes : inférieur ou égal au nombre de $a$, et pour le mot $w$ tout entier il y a égalité). -(2) Expliquer \emph{brièvement} pourquoi, si $w,w',w'' \in \Sigma^*$, -alors tout préfixe du mot $waw'bw''$ est d'une des trois formes -suivantes : (i) $u$ pour $u$ un préfixe de $w$, (ii) $wau'$ pour -$u'$ un préfixe de $w'$, ou (iii) $waw'bu''$ pour $u''$ un préfixe -de $w''$. (On rappelle que le mot vide et le mot tout entier comptent -pour préfixes d'un mot.) - -(3) Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la -propriété (A) ci-dessus, montrer que c'est encore le cas -de $waw'bw''$. Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la -propriété (B) ci-dessus, montrer que c'est encore le cas -de $waw'bw''$ (on utilisera pour cela la question (2)). - -(4) Déduire de la question (3) que tout mot de $L$ vérifie (A) et (B). -(Autrement dit, on vient de montrer : $L \subseteq M$.) - -(5) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer +(2) Expliquer pourquoi un mot $w \in \Sigma^*$ appartient à $L$ si et +seulement si $w = \varepsilon$ \emph{ou bien} $w$ s'écrit sous la +forme $w_1 a w_2 b w_3$ où $w_1,w_2,w_3$ appartiennent à $L$. (On +pourra, par exemple, raisonner sur les arbres d'analyse.) + +(3) Expliquer \emph{brièvement} pourquoi, si $w_1, w_2, w_3 \in +\Sigma^*$, alors tout préfixe du mot $w_1 a w_2 b w_3$ est d'une des +trois formes suivantes : (i) $u_1$ pour $u_1$ un préfixe de $w_1$, +(ii) $w_1 a u_2$ pour $u_2$ un préfixe de $w_2$, ou (iii) $w_1 a w_2 b +u_3$ pour $u_3$ un préfixe de $w_3$. (On rappelle que le mot vide et +le mot tout entier comptent pour préfixes d'un mot.) + +(4) Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la +propriété (A) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2 +b w_3$. Si $w_1, w_2, w_3 \in \Sigma^*$ vérifient tous les trois la +propriété (B) ci-dessus, montrer que c'est encore le cas de $w_1 a w_2 +b w_3$ (on utilisera pour cela la question (3)). + +(5) Déduire des questions (2) et (4) que tout mot de $L$ vérifie +(A) et (B). (Autrement dit, on vient de montrer : $L \subseteq M$.) + +(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer qu'on peut écrire $w = av$ pour un certain $v \in \Sigma^*$ ; si $w'$ est le plus long préfixe de $v$ vérifiant (B), montrer que $w = aw'bw''$ où $w'$ et $w''$ vérifient tous les deux (A) et (B). -(6) Déduire de la question (5) que tout mot vérifiant (A) et (B) +(7) Déduire des questions (2) et (6) que tout mot vérifiant (A) et (B) appartient à $L$. (Autrement dit, on vient de montrer : $M \subseteq L$. On a donc $L = M$.) -(7) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini +(8) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini par l'expression rationnelle $a{*}b{*}$, et en utilisant la description qu'on vient de trouver pour $L$ (comme l'ensemble des mots vérifiant (A) et (B)), déterminer $L \cap N$. Est-il rationnel ? -(8) Le langage $L$ est-il rationnel ? +(9) Le langage $L$ est-il rationnel ? % |