\documentclass{amsart} \textheight 250mm \textwidth 180mm \hoffset -32mm \voffset -24mm \newtheorem{theo}{Th\'eor\`eme}%[section] \newtheorem{lemm}[theo]{Lemme} \begin{document} \noindent \begin{tabular}{l c r} \hline Institut Galil\'ee - Universit\'e Paris 13 & \hskip 7cm \quad & Th\'eorie des langages \\ DEUG MIAS 2\`eme ann\'ee & \hskip 8cm \quad & 24 mars 2000\\ \hline \end{tabular} \begin{center}{\Huge Corrig\'e du devoir \`a la maison du 24 mars\\} \end{center} Deux questions d\'elicates de TD sont \'egalement trait\'ees en page 4. Un pseudo fascicule de d\'efinitions et de r\'esultats vous a par ailleurs \'et\'e distribu\'e, il couvre surtout le programme de l'examen de juin. \section{Mono\"{\i}des} \subsection{} Un mono\"{\i}de est un ensemble muni d'une loi interne (partout d\'efinie, associative) et d'un \'el\'ement neutre. \subsection{} Un mono\"{\i}de libre est mono\"{\i}de avec une ``base''. C'est-\`a-dire que ce mono\"{\i}de est {\em engendr\'e} par un ensemble d'\'el\'ements {\em ind\'ependants} (=d\'epourvus de relations entre eux). (``Base'' et ``libre'' sont donc \`a rapprocher des notions de base ou de libert\'e dans un espace vectoriel.) On a ainsi une ``factorisation'' (=une d\'ecomposition) de chaque \'el\'ement du mono\"{\i}de libre en \'el\`ements de cette ``base''. On peut de plus alors d\'efinir la longueur d'un \'el\'ement. Parfois, cette base est qualifi\'ee d'{\em alphabet}, les g\'en\'erateurs (= les \'el\'ements de la base) sont appel\'es {\em lettres} et les \'el\'ements du mono\"{\i}de libre sont appel\'es {\em mots}, l'op\'eration associative est appel\'ee {\em concat\'enation} et l'\'el\'ement neutre est appel\' {\em mot vide}. \subsection{} Exemple de mono\"{\i}de libre : les entiers positifs ou nul avec l'addition comme op\'eration (elle est bien associative et 0 est l'\'el\'ement neutre, la base est $\{1\}$). Exemple de mono\"{\i}de non libre : les entiers relatifs avec l'addition comme op\'eration (la base est $\{-1,+1\}$ mais cette base n'est pas ``libre'' car $(+1)+(-1)=0$). Deux autres exemples seraient\\ mono\"{\i}de libre : l'ensemble $E_1$ des mots contenants des $a$ ou des $b$, muni de la concat\'enation comme loi interne et du mot vide comme \'el\'ement neutre. La ``base'' de cet ensemble est $\{a,b\}$, $E$ est alors parfois not\'e $\{a,b\}^*$ ;\\ mono\"{\i}de non libre : l'ensemble $E_2$ des mots contenants des $a$ ou des $b$, muni de la concat\'enation comme loi interne et du mot vide comme \'el\'ement neutre et pour lequel on identifie les mots du type $uabbv$ avec le mot $uv$. Cette fois-ci $\{a,b\}$ n'est plus une base car on a la relation $abb=\epsilon$. \subsection{} Il y avait 143 mots \`a \'enum\'erer (travail fastidieux prenant 30 minutes avec les tr\`es n\'ecessaires v\'erifications). Une pr\'esentation possible de tous ces mots peut se faire sous la forme d'un arbre de possibilit\'es, pour une pr\'esentation plus ``lin\'eaire'', on peut calculer les produits (jusqu'a 10) et faire l'union, mais cela va peut-\^etre un peu plus vite de s'apercevoir que $L^*$ repr\'esente les mots o\`u un $a$ est aussit\^ot suivi d'un $b$ et donc les mots de longueur $<10$ sont {\small \{$\epsilon$, b, ab, bb, bab, bbb, abb, abab, abbb, babb, bbab, bbbb, ababb, abbab, abbbb, babab, babbb, bbabb, bbbab, bbbbb, ababab, ababbb, abbabb, abbbab, abbbbb, bababb, babbab, babbbb, bbabab, bbabbb, bbbabb, bbbbab, bbbbbb, abababb, ababbab, ababbbb, abbabab, abbabbb, abbbabb, abbbbab, abbbbbb, bababab, bababbb, babbabb, babbbab, babbbbb, bbababb, bbabbab, bbabbbb, bbbabab, bbbabbb, bbbbabb, bbbbbab, bbbbbbb, abababab, abababbb, ababbabb, ababbbab, ababbbbb, abbababb, abbabbab, abbabbbb, abbbabab, abbbabbb, abbbbabb, abbbbbab, abbbbbbb, babababb, bababbab, bababbbb, babbabab, babbabbb, babbbabb, babbbbab, babbbbbb, bbababab, bbababbb, bbabbabb, bbabbbab, bbabbbbb, bbbababb, bbbabbab, bbbabbbb, bbbbabab, bbbbabbb, bbbbbabb, bbbbbbab, bbbbbbbb, ababababb, abababbab, abababbbb, ababbabab, ababbabbb, ababbbabb, ababbbbab, ababbbbbb, abbababab, abbababbb, abbabbabb, abbabbbab, abbabbbbb, abbbababb, abbbabbab, abbbabbbb, abbbbabab, abbbbabbb, abbbbbabb, abbbbbbab, abbbbbbbb, babababab, babababbb, bababbabb, bababbbab, bababbbbb, babbababb, babbabbab, babbabbbb, babbbabab, babbbabbb, babbbbabb, babbbbbab, babbbbbbb, bbabababb, bbababbab, bbababbbb, bbabbabab, bbabbabbb, bbabbbabb, bbabbbbab, bbabbbbbb, bbbababab, bbbababbb, bbbabbabb, bbbabbbab, bbbabbbbb, bbbbababb, bbbbabbab, bbbbabbbb, bbbbbabab, bbbbbabbb, bbbbbbabb, bbbbbbbab, bbbbbbbbb\}}. Certains auront peut-\^etre remarqu\'e que le nombre $a_n$ de mots de $L^*$ de longueur $n$ donne une suite $(a_n)$ qui v\'erifie la r\'ecurrence $a_{n+2}=a_{n+1}+a_n$ (les premiers termes sont $(1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...)$), il s'agit l\`a de la suite de Fibonacci. La section 5 (Analyse et th\'eorie des langages) reviendra sur ce type de consid\'erations. \section{Grammaires} \subsection{} $L_1$=\{les mots ne contenant pas deux $a$ cons\'ecutifs\} est engendr\'e par\\ $$S\rightarrow \epsilon |a|B|BaBb|BaBba|, \quad B\rightarrow bB|\epsilon$$ On engendre ainsi le mot vide, le mot $a$, les mots qui ne contiennent que des $b$, puis les mots qui contiennent des $a$ (n\'ecessairement suivi d'un $b$) et qui se terminent, soit par $b$, soit par $a$. $L_2$=\{les mots contenant autant de $a$ que de $b$\} est engendr\'e par\\ $$S\rightarrow aSbS |bSaS| \epsilon$$ On a ainsi ``appari\'e'' les occurences de $a$ et $b$ pour assurer l'\'equilibre. $L_3$ =\{les mots ne contenant que des $a$ (au moins un) puis que des $b$ (au moins un)\} est engendr\'e par\\ $$S\rightarrow aAbB, \quad A\rightarrow aA|\epsilon, \quad B \rightarrow bB|\epsilon $$ $L_4$=\{les mots ne contenant que des $a$ puis que des $b$, avec ``nombre de $b$'' $>$ ``nombre de $a$'' $> 0$\} est engendr\'e par\\ $$ S \rightarrow aSb |bS |\epsilon$$ $L_5$=\{les mots dont la parit\'e du nombre de $a$ \'egale celle du nombre de $b $\} est engendr\'e par\\ $$S\rightarrow aT| bT |\epsilon, \quad T \rightarrow aS| bS $$ L'id\'ee de base consiste \'a partir du mot vide (dont la parit\'e de nombre $a$ \'egale celle du nombre de $b$) et \'a observer que si j'ajoute un $a$ ou un $b$, la parit\'e n'est plus \'egale, et alors si j'ajoute un $a$ ou un $b$, la parit\'e redevient \'egale. On voit ainsi que tous les mots de longueur paire appartiennent \'a $L_5$ (et seulement eux!). \subsection{} $L_1$ peut \^etre engendr\'e par la grammaire r\'eguli\`ere suivante : $$S\rightarrow bB|bA|aA|\epsilon, \quad B\rightarrow bB|\epsilon, \quad A\rightarrow bB|bD, \quad D\rightarrow aA|\epsilon$$ $L_3$ peut \^etre engendr\'e par la grammaire r\'eguli\`ere suivante : $$S\rightarrow aA, \quad A\rightarrow aA|bB, \quad B \rightarrow bB|\epsilon $$ La grammaire de $L_5$ est d\'ej\`a r\'eguli\`iere. (Expressions rationnelles associ\'ees : $L_1=b^*(ab^+)^*(\epsilon+a)$, $L_3=a^+b^+$, $L_5=(aa+ab+ba+bb)^*$) \subsection{} \`A l'aide du lemme de l'\'etoile (voir preuve, page 4), on va prouver que $L_4=\{a^nb^{n+k}, n\geq 1, k>0\}$ n'est pas r\'egulier. Supposons que $L_4$ est r\'egulier, regardons alors la d\'ecomposition $u=u_1vu_2$ (pour $u$ un mot de $L_4$ ``assez long'') qui nous est donn\'ee par application du lemme de l'\'etoile. On devrait avoir $u_1v^i u_2 \in L_4$ pour tout $i\in {\bf N}$. Or ceci est clairement impossible si $v$ ne contient que des $a$, ou si $v$ contient des $a$ et des $b$. Donc les d\'ecompositions fournies ne peuvent donner que des $v$ qui ne contiennent que des $b$. Or il existe dans $L_4$ des mots avec un pr\'efixe contenant autant de $a$ cons\'ecutifs que l'on veut. Ceci implique donc qu'avant m\^eme que l'on commence \`a lire des $b$ dans l'automate, on est d\'ej\`a pass\'e deux fois par le m\^eme \'etat. Ainsi, on a bien l'existence d'un facteur $v$ qui ne contient que des $a$, ce qui contredit le point pr\'ecedent et donc ceci implique que l'on ne pouvait appliquer le lemme de l'\'etoile, et que le langage $L_4$ n'est donc pas r\'egulier. \section{Expressions r\'eguli\`eres} \subsection{} On commence par simplifier un peu l'expression~: $(a^*b^*)$ contient $a$ et $b$, donc $(a^*b^*)^*= \{a, b\}^*$. Ainsi $$(a^*b^*)^*b+(ba)^*= \{a, b\}^*b+(ba)^*$$ et il s'agit donc de reconna\^{\i}tre tous les mots finissants par $b$ et toutes les suites de $ba$. La construction de l'automate ne pose aucun probl\`eme. % \vskip 3cm \subsection{} Enlevons la transition entre l'\'etat 4 et l'\'etat 1 et regardons l'automate $A'$ ainsi d\'efini. Par disjonction des cas, le langage $L'$ reconnu par cet automate est $$L'=a(ba)^*b + a(ba)^*ba +b(ab)^*a+b(ab)^*ab.$$ Il est clair que $$\mathcal L(A)=(L'a)^*L'=((a(ba)^*(b+ba)+b(ab)^*(a+ab))a)^*(a(ba)^*(b+ba)+b(ab)^*(a+ab)).$$ Diverses autres formules \'equivalentes (\`a une factorisation pr\`es, etc.) \'et\'e aussi acceptables. \subsection{}%[20 min] Impossible de donner une telle expression car le langage n'est pas r\'egulier. En effet, c'est une grammaire \'equivalente \`a $$A\rightarrow aAbb|aab|ab^*A |\epsilon$$ qui est identique, \`a des changements de variables prets, \`a $$A\rightarrow cAd|eA |f$$ et si on fait maintenant les substitutions ($e\leftarrow \epsilon$ et $f \leftarrow \epsilon$), on ne modifie pas la r\'egularit\'e du langage; or le langage engendr\'e par $$A\rightarrow cAd|\epsilon A |\epsilon $$ est $\{c^n d^n), n\in {\bf N}\}$, bien connu pour ne pas \^etre r\'egulier (d\'emontr\'e en TD). CQFD~! La transformation suivante a pour trace $aabbb$~: $$A \rightarrow aBb \rightarrow Ab \rightarrow aC \rightarrow bC \rightarrow A \rightarrow \epsilon$$ La grammaire est ambig\"ue car on peut trouver un autre arbre de d\'erivation, celui qui correspond \`a la transformation $$A \rightarrow aC \rightarrow A a\rightarrow C \rightarrow bC \rightarrow bC \rightarrow bC \rightarrow A \rightarrow \epsilon$$ \section{Automates} \subsection{} Il suffit d'enlever l'\'etat 0. \subsection{} [dessin \`a faire] Application de l'algorithme vu en TD. \subsection{} On ne peut pas faire mieux que l'automate donn\'e en 4.1. \section{Analyse et th\'eorie des langages} \subsection{} $$S \rightarrow 0S | 1S | \epsilon \Rightarrow S(z)=\frac{1}{1-2z} $$ Dans le m\^eme genre, la s\'erie g\'en\'eratrice de $(ab,b)^*=\cup_{n \in \bf N} \{a,ab\}^n $ (cf. question 1.4) est $\sum (z+z^2)^n =\frac{1}{1-(z+z^2)}$. \subsection{} La grammaire $S\rightarrow aSbS |\epsilon$ est non ambig\"ue et g\'en\`ere les mots de Dyck. La s\'erie g\'en\'eratrice est donn\'ee par $$S\rightarrow aSbS |\epsilon \Rightarrow S(z)=z^2S(z)^2+1 \Rightarrow L(z)=S(z)=\frac{1-\sqrt {1-4z^2}}{2z^2}$$ La division par $z^2$ n'est pas probl\'ematique en $z=0$, car on a en fait une forme ind\'etermin\'ee $0/0$ qui s'av\`ere \^etre $=1$ (en utilisant des d\'eveloppements limit\'es par exemple). En revanche, la s\'erie a une singularit\'e (du type $\sqrt 0$) quand $1-4z^2=0$ donc quand $z=1/2$ qui est donc le rayon de convergence, on en d\'eduit (formule de Hadamard : rayon de convergence = 1/lim sup $a_n^{1/n}$) que les coefficients de la s\'erie croissent comme $2^n$. C'est-\`a-dire qu'il y a environ $2^n$ mots de Dyck de longueur $n$ (pour $n$ pair, car pour $n$ impair, il y en a bien s\^ur 0). \subsection{} D'apr\`es le th\'eor\`eme de Chomsky-Sch\"utzenberger, $L_2$ n'est pas reconnaissable car il engendr\'e par une grammaire non ambig\"ue et que sa s\'erie g\'en\'eratrice est alg\'ebrique non rationnelle~: $$S\rightarrow aSbS |bSaS| \epsilon \Rightarrow S(z)=2z^2S(z)^2+1 \Rightarrow L(z)=S(z)=\frac{1-\sqrt {1-8z^2}}{4z^2}$$ \section{Automates et cha\^{\i}nes de Markov} \subsection{} [dessin \`a faire] \subsection{} [dessin \`a faire] %[20min +calcul formel] Comme les probabilit\'es d'arriv\'ees dans les diff\'erents \'etats au bout de trois coups sont identiques, tout se joue apr\`es. Soit $M_1$ la matrice donnant les transitions entre les 8 \'etats (apr\`es 3 coups) pour $PPP$ final et $M_2$ la matrice pour $PFP$ final. [dessin \`a faire] Il faut alors utiliser un logiciel de calcul formel pour calculer $\sum M_1^n = (Id-M_1)^{-1}$ et $\sum M_2^n = (Id-M_2)^{-1}$. La somme des \'el\'ements de la $i$-i\`eme ligne de l'inverse de $Id-M$ donne donc le nombre moyen de coups a faire avant d'atteindre l'\'etat correspondant. On reviendra en TD sur cet exercice (dont la derni\`ere question est totalement hors programme). \section{Compilation} Compiler, c'est transformer une ``phrase'' (un programme) d'un certain langage en ``quelque chose'' de compr\'ehensible par le microprocesseur. $\bullet$ L'analyse lexicale (scanning) consiste \`a lire un par un les lettres ($=$ caract\`eres, symboles...) afin de reconna\^{\i}tre des mots du langage, et donc de d\'ecouper la phrase initiale en suite de mots. $\bullet$ L'analyse syntaxique (parsing) r\'epond \`a la question : cette suite de mots ainsi obtenue est-elle ``grammaticalement'' correcte~? C'est-\`a-dire, peut-on trouver une d\'erivation qui conduit \`a cette suite de mots ? $\bullet$ L'analyse s\'emantique s'attache \`a d\'etecter des incoh\'erences de sens. $\bullet$ L'optimisation consiste \`a simplifier l'arbre de d\'erivation ainsi obtenu. $\bullet$ La g\'en\'eration de code consiste \`a associer des mots d'un nouveau langage (traduction en langage machine) aux mots pr\'ec\'edemment reconnus. $\bullet$ L'ex\'ecution est alors l' ``interpr\'etation'' par le micro-processeur du code ainsi g\'en\'er\'e. \section{TD1 Exercice 3. Question c)} On rappelle qu'avec les notions de cette question, $bin(u)$ est le nombre d'op\'eration du mot $u$ et que $D(u)$ est le nombre de ``d\'ecoupage'' du mot $u$. Nous allons faire une r\'ecurrence {\bf forte} sur $bin(u)$. $\bullet$ [initialisation de la r\'ecurrence]\\ Quand $bin(u)=0$, on a donc utilis\'e ni la r\`egle 1 ni la r\`egle 2, on n'a donc aucune ambig\"uit\'e (l'arbre de d\'erivation de $u$ est en fait ``lin\'eaire'') et on a bien $$F(u)=Amb_G(u)=1.$$ $\bullet$ [h\'eridit\'e {\bf forte}] Supposons que $F(u)=Amb_G(u)$ soit v\'erifi\'ee pour les $u$ tels que $bin(u)\leq n$ ({\bf inf\'erieurs} ou \'egal, j'insiste), nous voulons montrer que $F(v)=Amb_G(v)$ pour tous les $v$ tels que $bin(v)=n+1$. Or un tel $v$ peut bien s\^ur s'\'ecrire sous la forme $v=u_1$ {\em op\'erateur} $u_2$, et donc $u_1$ et $u_2$ sont tels que $bin(u_1)\leq n$ et $bin(u_2)\leq n$. Il y a tous les $D(u)$ comme d\'ecoupage possible, ceci r\'efl\`ete tout \`a fait les diff\'erents arbres de d\'erivations possibles~: quand on regarde la racine, on a soit $S_1 \rightarrow S_2\times S_3$ soit $S_1 \rightarrow S_2+S_3$ avec $S_2$ qui va se d\'eriver en $u_1$ et $S_3$ qui va se d\'eriver en $u_2$. Ainsi $$Amb_G(u) = \sum_{(u_1, u_2)\in D(u)} Amb_G(u_1) Amb_G(u_2) =\sum_{(u_1, u_2)\in D(u)} F(u_1) F(u_2)= F(u).$$ (La deuxi\`eme \'egalit\'e \'etant due \`a l'hypoth\`ese de r\'ecurrence forte.) On a bien d\'emontr\'e $F=Amb_G$. \section{TD2 Exercice 2} \begin{lemm}[Lemme de l'\'etoile ou ``pumping lemma''] Si $L$ est un langage r\'egulier (c'est-\`a-dire $L=\mathcal L(G)$ pour une grammaire $G$ r\'eguli\`ere) alors~:\\ il existe un entier naturel $N>0$ tel que, pour tout $u\in L$ v\'erifiant $|u|\geq N$, on ait trois mots $u_1, v, u_2$ satisfaisant les conditions~:\\ 1) $u=u_1vu_2$\\ 2) $|v|\neq 0$\\ 3) pour tout entier naturel $i$~: $u_1v^iu_2\in L$. \end{lemm} \begin{proof} Pour un langage fini $L$ (i.e. qui contient un nombre fini de mots), le lemme de l'\'etoile est ``b\^etement'' v\'erifi\'e (car, en choississant N:=1+``longueur du plus long mot de L'', on a aucun mot de longueur $\geq N$). Pour un langage r\'egulier et infini $L$ (i.e. qui contient un nombre infini de mots), consid\'erons un automate $A$ tel que $L=\mathcal L (A)$ (il existe un tel automate car {\bf Reg=Rec}, tout langage {\bf r\'eg}ulier est {\bf rec}onnu par un certain automate). Notons $m$ le nombre d'\'etats de $A$. Consid\'erons maintenant un mot $u\in L$ de longueur $>m$ (il existe for\c{c}\'ement un tel mot car le langage est infini), il existe donc un chemin dans $A$ qui part d'un \'etat initial, qui passe obligatoirement (au moins) deux fois par le m\^eme \'etat $x$ (car $A$ n'a que $m$ \'etats), et qui termine dans un \'etat final.\\ Notons $u_1$ la trace du chemin entre l'\'etat initial et la premi\`ere fois que l'on est pass\'e par $x$.\\ Notons $u_2$ la trace du chemin entre la derni\`ere fois que l'on est pass\'e par $x$ et l'\'etat final.\\ Notons $v$ la trace du chemin entre la premi\`ere et la derni\`ere fois que l'on est pass\'e par $x$.\\ On a bien $u=u_1vu_2$ et $v\neq \epsilon$. De plus, $\forall i, u_1v^iu_2$ est bien un mot de $L$ car il correspond \`a un chemin partant d'un \'etat initial et finissant dans un \'etat final. %Dessin u_1 v (boucle) u_2 Il suffit donc de prendre $N=m+1$ et on a prouv\'e le lemme de l'\'etoile. \end{proof} \end{document}