diff options
| -rw-r--r-- | exercices1.tex | 20 |
1 files changed, 11 insertions, 9 deletions
diff --git a/exercices1.tex b/exercices1.tex index 60fef33..b0595a7 100644 --- a/exercices1.tex +++ b/exercices1.tex @@ -226,7 +226,8 @@ Supposons par l'absurde que $L$ soit rationnel. D'après le lemme de pompage, il existe un certain $k$ tel que tout mot de $L$ de longueur $\geq k$ se factorise sous la forme $uvw$ avec (i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$. Soit -$p$ un nombre premier supérieur ou égal à $k$ : le mot $a^p \in L$ +$p$ un nombre premier supérieur ou égal à $k$ (qui existe car +l'ensemble des nombres premiers est infini) : le mot $a^p \in L$ admet une factorisation comme on vient de dire. Posons $|u| =: m$ et $|v| =: n$, si bien que $|w| = p-m-n$. On a alors $n\geq 1$ d'après (i), et $|uv^iw| = m + in + (p-m-n) = p+(i-1)n$ est premier @@ -396,14 +397,15 @@ le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to 0$, $0\to 5$, $3\to 7$ et $7\to 7$. Tous les états contenant l'un des symboles $3,6,7$ sont finaux.) -(2) On a affaire à un DFA dont tous les états sont accessibles, on -peut donc appliquer directement l'algorithme de Moore. Une première -partition sépare les états finaux, soit $023, 0237, 027, 056, 0567, -057$ des non-finaux, soit $0, 02, 05$. L'étape suivante distingue -$02$ parce que sa $a$-transition conduit à une classe différente que -celles de $0$ et $05$, et $05$ parce que sa $b$-transition conduit à -une classe différente de $0$ et $02$. Les étapes suivantes ne -changent rien. Finalement, on arrive à un automate à quatre états : +(2) On a affaire à un DFA (sous-entendu : \emph{complet}) dont tous +les états sont accessibles, on peut donc appliquer directement +l'algorithme de Moore. Une première partition sépare les états +finaux, soit $023, 0237, 027, 056, 0567, 057$ des non-finaux, soit $0, +02, 05$. L'étape suivante distingue $02$ parce que sa $a$-transition +conduit à une classe différente que celles de $0$ et $05$, et $05$ +parce que sa $b$-transition conduit à une classe différente de $0$ et +$02$. Les étapes suivantes ne changent rien. Finalement, on arrive à +un automate à quatre états : \begin{center} %%% begin ex1p2d %%% |