summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20190205.tex45
1 files changed, 25 insertions, 20 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex
index 6574119..c975ab4 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -161,7 +161,7 @@ l'automate ainsi obtenu.
(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
$5$ états. La suite de l'exercice dépendant de cette question, on
-conseille vérifier très soigneusement que $\mathscr{A}_1$ est correct.
+conseille de vérifier très soigneusement que $\mathscr{A}_1$ est correct.
À défaut de donner l'automate de Glushkov ou de Thompson, donner un
NFA reconnaissant $L$ pourra apporter une partie des points.)
@@ -222,9 +222,9 @@ qu'on a tracé au-dessus (les seuls états qui subsistent après
quatre états auxquels aboutissent une transition non spontanée).
\end{corrige}
-(2) Déterminiser l'automate $\mathscr{A}_1$ obtenu en (1). On demande
-un automate fini déterministe \emph{complet}. On appellera
-$\mathscr{A}_2$ l'automate déterministe en question.
+(2) À partir de $\mathscr{A}_1$, construire un automate fini
+déterministe complet reconnaissant $L$. On appellera $\mathscr{A}_2$
+l'automate en question.
\begin{corrige}
L'automate $\mathscr{A}_1$ est déterministe incomplet : il s'agit donc
@@ -394,8 +394,8 @@ S &\rightarrow \varepsilon\\
(1) Montrer que cette grammaire $G$ est ambiguë : pour cela, on
exhibera deux arbres d'analyse différents du mot $abab$.
-\begin{corrige}
+\begin{corrige}
On peut proposer les arbres d'analyse suivants :\\
% S<S<e.>a.S<e.>b.S<S<e.>a.S<e.>b.S<e.>>>
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
@@ -441,7 +441,7 @@ d'autre part\\
La grammaire $G$ est donc ambiguë.
\end{corrige}
-\medbreak
+\bigbreak
\emph{Notation :} Si $w \in \Sigma^*$, on notera $|w|_a$ le nombre
total d'occurrences de la lettre $a$ dans le mot $w$, et de façon
@@ -551,23 +551,24 @@ que $w$, d'après l'hypothèse de récurrence ils vérifient (A) et (B),
si bien que $w$ vérifie aussi (A) et (B) d'après la question (4).
\end{corrige}
-(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer
-qu'on peut écrire $w = av$ pour un certain $v \in \Sigma^*$ ; si $w'$
-est le plus long préfixe de $v$ vérifiant (B)\footnote{Autrement dit,
- le plus long préfixe $w'$ de $v$ tel que pour tout préfixe $u'$
- de $w'$ (y compris $w'$ lui-même) on ait $|u'|_b\leq |u'|_a$.},
-montrer qu'on a $w = aw'bw''$ pour un certain $w'' \in \Sigma^*$ ;
-puis montrer que $w'$ vérifie (B), puis qu'il vérifie (A), et enfin
-que $w''$ vérifie (A) et (B).
+(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B).
+(6.1) Montrer qu'on peut écrire $w = av$ pour un certain $v \in
+\Sigma^*$. (6.2) Si $w'$ est le plus long préfixe de $v$
+vérifiant (B)\footnote{Autrement dit, le plus long préfixe $w'$ de $v$
+ tel que pour tout préfixe $u'$ de $w'$ (y compris $w'$ lui-même) on
+ ait $|u'|_b\leq |u'|_a$.}, montrer qu'on a $w = aw'bw''$ pour un
+certain $w'' \in \Sigma^*$. (6.3) Montrer que $w'$ vérifie (B).
+(6.4) Montrer que $w'$ vérifie (A). (6.5) Montrer que $w''$ vérifie
+(A) et (B).
\begin{corrige}
-Comme $w$ est un mot non vide, on peut parler de sa première
+(6.1) Comme $w$ est un mot non vide, on peut parler de sa première
lettre $x$, qui en est un préfixe (de longueur $1$), et qui doit
vérifier $|x|_b \leq |x|_a$ d'après (B), ce qui n'est évidemment
possible que pour $x=a$. On a donc $w = av$ où $v$ est le suffixe
correspondant à $a$.
-Remarquons que $|v|_b = |w|_b = |w|_a = 1 + |v|_a$ donc $|v|_b >
+(6.2) Remarquons que $|v|_b = |w|_b = |w|_a = 1 + |v|_a$ donc $|v|_b >
|v|_a$, et en particulier, $v$ \emph{ne} vérifie \emph{pas} (B). Si
maintenant $w'$ est le plus long préfixe de $v$ vérifiant (B), la
remarque qu'on vient de faire montre que $w' \neq v$, donc il y a au
@@ -578,14 +579,14 @@ vérifie $|va|_b = |v|_b \leq |v|_a < |va|_a$) : on peut donc écrire $v
= w'bw''$ pour un certain $w''\in\Sigma^*$, c'est-à-dire $w =
aw'bw''$.
-Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors
+(6.3) Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors
$au'$ en est un de $w$, et on a $|u'|_b = |au'|_b \leq |au'|_a =
-1+|u'|_a$. Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est
+1+|u'|_a$. (6.4) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est
pas le cas, comme $|w'|_b \leq |w'|_a$ (par (B), qu'on vient de
montrer), on a $|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1
\leq |w'|_a = |w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit
le fait que $w'$ était \emph{le plus long} préfixe de $v$
-vérifiant (B). Le mot $w''$ vérifie (A) : en effet, on a $|w|_b =
+vérifiant (B). (6.5) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b =
|w|_a$ (puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 =
|w'|_a + |w''|_a + 1$, et comme on vient de voir que $|w'|_b =
|w'|_a$, on a aussi $|w''|_b = |w''|_a$. Enfin, le mot $w''$
@@ -640,9 +641,13 @@ On sait (comme application vue en cours du lemme de pompage) que le
langage $\{a^k b^k : k\in\mathbb{N}\}$ n'est pas rationnel.
\end{corrige}
-(9) Le langage $L$ est-il rationnel ?
+(9) Le langage $L$ est-il rationnel ? (On ne cherchera pas à
+appliquer le lemme de pompage pour cette question.)
\begin{corrige}
+Rappelons que le langage $N$ est rationnel (puisque dénoté par une
+expression rationnelle).
+
Si le langage $L$ était rationnel, alors son intersection $L\cap N$
avec le langage rationnel $N$ serait aussi rationnelle, mais on vient
de voir que $L\cap N$ n'est pas rationnel ; c'est donc que $L$ n'est