diff options
| -rw-r--r-- | controle-20190205.tex | 45 |
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 |