From 7ffc7b960b4e67232f767562032a25a198e2723d Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 2 Nov 2017 16:37:52 +0100
Subject: More clarifications.

---
 notes-inf105.tex | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

(limited to 'notes-inf105.tex')

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
-- 
cgit v1.2.3