diff options
Diffstat (limited to 'controle-20190205.tex')
| -rw-r--r-- | controle-20190205.tex | 19 |
1 files changed, 12 insertions, 7 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex index 18e7e50..5c0d78f 100644 --- a/controle-20190205.tex +++ b/controle-20190205.tex @@ -163,7 +163,7 @@ l'automate ainsi obtenu. $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. À défaut de donner l'automate de Glushkov ou de Thompson, donner un -NFA reconnaissant $L$ apportera une partie des points.) +NFA reconnaissant $L$ pourra apporter une partie des points.) \begin{corrige} L'automate $\mathscr{A}_1$ obtenu est le suivant : @@ -262,7 +262,8 @@ $\mathscr{A}_3$ l'automate canonique ainsi obtenu. \begin{corrige} L'algorithme de minimisation identifie les trois états finaux ($0,3,4$) de l'automate $\mathscr{A}_2$, ce qui donne -l'automate $\mathscr{A}_3$ suivant : +l'automate $\mathscr{A}_3$ suivant (on note $0$ pour l'état résultant +de l'identification de $0,3,4$) : \begin{center} \begin{tikzpicture}[>=latex,line join=bevel,automaton] \node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$}; @@ -440,6 +441,8 @@ d'autre part\\ La grammaire $G$ est donc ambiguë. \end{corrige} +\medbreak + \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 analogue $|w|_b$ le nombre total d'occurrences de la lettre $b$ (on a @@ -447,17 +450,19 @@ bien sûr $|w| = |w|_a + |w|_b$ puisque $\Sigma = \{a,b\}$ ; on a par ailleurs $|vv'|_a = |v|_a + |v'|_a$ et $|vv'|_b = |v|_b + |v'|_b$ pour tous mots $v,v' \in \Sigma^*$). +\medbreak + On se propose, dans les quelques questions suivantes, de montrer que -le langage $L := L(G)$ engendré par la grammaire $G$ est l'ensemble -$M$ des mots $w \in \Sigma^*$ vérifiant les deux propriétés +le langage $L := L(G)$ engendré par la grammaire $G$ coïncide avec +l'ensemble $M$ des mots $w \in \Sigma^*$ vérifiant les deux propriétés suivantes : \begin{itemize} \item[\quad(A)] $|w|_b = |w|_a$, et \item[\quad(B)] $|u|_b \leq |u|_a$ pour tout préfixe $u$ de $w$ \end{itemize} (autrement dit, le nombre de $b$ de n'importe quel préfixe de $w$ est -inférieur ou égal au nombre de $a$, et pour le mot $w$ tout entier il -y a égalité). +inférieur ou égal à son nombre de $a$, et pour le mot $w$ tout entier +il y a égalité). (2) Expliquer pourquoi un mot $w \in \Sigma^*$ appartient à $L$ si et seulement si $w = \varepsilon$ \emph{ou bien} $w$ s'écrit sous la @@ -526,7 +531,7 @@ Si $w_1, w_2, w_3$ vérifient (B) (c'est-à-dire $|u|_b \leq |u|_a$ pour tout préfixe $u$ d'un des $w_i$), alors en notant $u_i$ un préfixe quelconque du $w_i$ correspondant, on a (i) $|u_1|_b \leq |u_1|_a$, (ii) $|w_1 a u_2|_b = |w_1|_b + |u_2|_b + 1 \leq |w_1|_a + |u_2|_a + 1 -= |w_1 a u_2|_a$ et (iii) $|w_1 a w_2 b u_3|_b \leq |w_1|_b + |w_2|_b += |w_1 a u_2|_a$ et (iii) $|w_1 a w_2 b u_3|_b = |w_1|_b + |w_2|_b + |u_3|_b + 1 \leq |w_1|_a + |w_2|_a + |u_3|_a + 1 = |w_1 a w_2 b u_3|_a$. D'après la question (3), on peut en conclure que tout préfixe $u$ de $w_1 a w_2 b w_3$ vérifie $|u|_b \leq |u|_a$, |