diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 33 |
1 files changed, 20 insertions, 13 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 3cd099e..8612eb7 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -3712,7 +3712,7 @@ procédant par l'absurde). \begin{prop}[lemme de pompage pour les langages rationnels]\label{pumping-lemma}\index{pompage (lemme de)} Soit $L$ un langage rationnel. Il existe alors un entier $k$ tel que tout mot de $t \in L$ de longueur $|t| \geq k$ admette une -factorisation $t = uvw$ en trois facteurs $u,v,w$ où : +factorisation $t = uvw$ en trois facteurs $u,v,w \in \Sigma^*$ où : \begin{itemize} \item[(i)] $|v| \geq 1$ (c'est-à-dire $v\neq\varepsilon$), \item[(ii)] $|uv| \leq k$, @@ -5008,8 +5008,9 @@ T &\rightarrow aSb\\ \end{aligned} \] -L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ -(c'est même le seul possible) : +L'arbre d'analyse suivant est un arbre d'analyse du mot $aabbab$ (et +on verra en \ref{inambiguity-of-well-parenthesized-expressions} que +c'est le seul possible) : \begin{center} \tikzstyle{automaton}=[scale=0.5] %%% begin parsetree1 %%% @@ -5249,7 +5250,8 @@ S\; \rightarrow\; aS \;|\; a fois la règle $S \rightarrow a$ (il y a donc une unique dérivation du mot, et \textit{a fortiori} un unique arbre d'analyse). -\thingy La grammaire $G$ des expressions bien-parenthésées +\thingy\label{inambiguity-of-well-parenthesized-expressions} La +grammaire $G$ des expressions bien-parenthésées \[ \begin{aligned} S &\rightarrow TS \;|\; \varepsilon\\ @@ -5306,7 +5308,8 @@ l'intersection des deux, et ce sont ces mots qui forcent ce langage à \begin{prop}[lemme de pompage pour les langages algébriques]\label{pumping-lemma-for-algebraic-languages}\index{pompage (lemme de)} Soit $L$ un langage algébrique. Il existe alors un entier $k$ tel que tout mot de $t \in L$ de longueur $|t| \geq k$ admette une -factorisation $t = uvwxy$ en cinq facteurs $u,v,w,x,y$ où : +factorisation $t = uvwxy$ en cinq facteurs $u,v,w,x,y \in \Sigma^*$ +où : \begin{itemize} \item[(i)] $|vx| \geq 1$ (c'est-à-dire $v\neq\varepsilon$ \emph{ou bien} $x\neq\varepsilon$), @@ -5340,14 +5343,18 @@ est différent (d'après (i)), on a une contradiction. \end{proof} \thingy La proposition \ref{intersection-of-algebraic-and-rational} -peut s'avérer utile pour montrer qu'un langage n'est pas algébrique. -Par exemple, le langage $L$ formé des mots sur $\{a,b,c\}$ ayant le -même nombre total de $a$, de $b$ et de $c$ (autrement dit $\{w \in -\{a,b,c\}^* : |w|_a = |w|_b = |w|_c\}$ où $|w|_x$ désigne le nombre -d'occurrences de la lettre $x$ dans le mot $w$) n'est pas algébrique : -le plus simple pour le voir est de l'intersecter avec le langage -rationnel $M := \{a^i b^j c^k : i,j,k\in\mathbb{N}\}$ (dénoté par -l'expression rationnelle $a{*}b{*}c{*}$) : si $L$ était algébrique +peut s'avérer utile pour montrer qu'un langage n'est pas algébrique, +en permettant de simplifier le langage auquel on va appliquer le lemme +de pompage. + +À titre d'exemple, montrons que le langage $L$ formé des mots sur +$\{a,b,c\}$ ayant le même nombre total de $a$, de $b$ et de $c$ +(autrement dit $\{w \in \{a,b,c\}^* : |w|_a = |w|_b = |w|_c\}$ où +$|w|_x$ désigne le nombre d'occurrences de la lettre $x$ dans le +mot $w$, cf. \ref{number-of-occurrences-of-letter}) n'est pas +algébrique ; le plus simple pour le voir est de l'intersecter avec le +langage rationnel $M := \{a^i b^j c^k : i,j,k\in\mathbb{N}\}$ (dénoté +par l'expression rationnelle $a{*}b{*}c{*}$) : si $L$ était algébrique alors d'après \ref{intersection-of-algebraic-and-rational}, le langage $L\cap M$ le serait aussi ; mais $L\cap M = \{a^i b^i c^i : i\in\mathbb{N}\}$, et on vient de voir |