summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-16 15:32:50 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-16 15:32:50 +0100
commitb58c7150c57b62c3fed7b705ff38b26487a5b3c1 (patch)
tree857312ded848c6a41f8e1f2109e8c2d074a18079
parent2883d38b37cbec4937891186dd5468666c6ad00f (diff)
downloadinf105-b58c7150c57b62c3fed7b705ff38b26487a5b3c1.tar.gz
inf105-b58c7150c57b62c3fed7b705ff38b26487a5b3c1.tar.bz2
inf105-b58c7150c57b62c3fed7b705ff38b26487a5b3c1.zip
Various small mistakes (thanks, Olivier).
-rw-r--r--exercices2.tex8
1 files changed, 4 insertions, 4 deletions
diff --git a/exercices2.tex b/exercices2.tex
index bfcb023..8fe0e79 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -437,8 +437,8 @@ $x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)
L(G)$.
(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de
- longueur impaire. Un mot $t$ de $L(G)$ de longueur paire dérive
- donc forcément de $AB$ ou de $BA$. Sans perte de généralité,
+ longueur impaire. Un mot $t$ de $L(G)$ de longueur paire $2n$
+ dérive donc forcément de $AB$ ou de $BA$. Sans perte de généralité,
supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient
à $M$. Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le
facteur de $t$ qui dérive de $B$ : on sait alors (toujours
@@ -446,7 +446,7 @@ $x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)
la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme
(quitte à continuer la numérotation des indices) $x_{2i}\cdots
x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$. Alors $x_{n+i}
- \neq x_i$ donc le mot $t$ n'est pas dans $L$ d'après (0).
+ \neq x_i$ donc le mot $t$ est dans $M$ d'après (0).
(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de
longueur impaire est dans les deux et qu'un mot de longueur paire
@@ -465,7 +465,7 @@ Soit $\Sigma = \{a,b\}$. Montrer que le langage $Q := \{ww :
w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit,
des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou
encore $aabbaabb$ sont dans $Q$) n'est pas algébrique. On pourra pour
-considérer son intersection avec le langage $L_0$ dénoté par
+cela considérer son intersection avec le langage $L_0$ dénoté par
l'expression rationnelle $a{*}b{*}a{*}b{*}$ et appliquer le lemme de
pompage.