diff options
| -rw-r--r-- | exercices2.tex | 8 |
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. |