diff options
Diffstat (limited to 'controle-20210618.tex')
| -rw-r--r-- | controle-20210618.tex | 43 |
1 files changed, 21 insertions, 22 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex index 4993f1d..5e9b114 100644 --- a/controle-20210618.tex +++ b/controle-20210618.tex @@ -140,9 +140,9 @@ de justifier les réponses. automates successifs qu'on calculera.} (Par exemple, pour un automate censé reconnaître le langage $L$, on vérifiera qu'il accepte bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux -qu'on a identifiés comme n'appartement pas à $L$.) Les fautes pouvant -être détectées par cette vérification seront plus lourdement -sanctionnées. +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes qui +auraient dû être détectées par cette vérification pourront être plus +lourdement sanctionnées. (1) Traiter l'une \emph{ou} l'autre des questions suivantes : (i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; @@ -160,7 +160,8 @@ $\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici un automate fini \emph{déterministe complet}. (3) Minimiser l'automate $\mathscr{A}_2$. On appellera -$\mathscr{A}_3$ l'automate canonique du langage $L$ ainsi obtenu. +$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du +langage $L$). (4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ @@ -181,11 +182,10 @@ vérifient pas $r$). On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma = \{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles \[ -S \rightarrow \varepsilon \;|\; aSbc \;|\; abSc +S \rightarrow abc \;|\; aSbc \;|\; abSc \] -On appellera « $0$ » la règle $S \rightarrow \varepsilon$, et -« $1$ » la règle $S \rightarrow aSbc$, et enfin « $2$ » la règle $S -\rightarrow abSc$. +On appellera « $0$ » la règle $S \rightarrow abc$, et « $1$ » la règle +$S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$. (1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$ selon cette grammaire $G$. (On pourra d'abord lire les questions @@ -197,22 +197,21 @@ On va maintenant montrer que $G$ est inambiguë. par $G$ a nécessairement $a$ pour préfixe (i.e., commence par la lettre $a$). -(3) Montrer que tout mot de $L$ dérivé en commençant +(3) Montrer que tout mot de $L$ dérivé en démarrant par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation - selon $G$ de la forme $S \Rightarrow aSc \mathrel{\Rightarrow^*} w$ + selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$ où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de - dérivations. Ou, ce qui revient au même (on pourra tenir ce point - pour acquis) : tout mot $w$ possédant un arbre d'analyse dont la - racine a trois fils étiquetés $a,S,b$ dans cet ordre.} la règle $1$ -a nécessairement $aa$ ou $ac$ comme préfixe. Montrer de même que tout -mot de $L$ dérivé en commençant par la règle $2$ a nécessairement $ab$ -comme préfixe. - -(4) En déduire comment, d'après la longueur d'un mot $w$ de $L$ et ses -deux premières lettres, on peut savoir par quelle règle commence -nécessairement une dérivation de $w$ selon $G$ (ou, ce qui revient au -même, quels sont les fils de la racine dans tout arbre d'analyse -de $w$). + dérivations immédiates. Ou, ce qui revient au même (et on pourra + tenir ce point pour acquis) : tout mot $w$ possédant un arbre + d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet + ordre.} la règle $1$ a nécessairement $aa$ comme préfixe. Montrer +de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a +nécessairement $aba$ comme préfixe. + +(4) En déduire comment, d'après les premières lettres d'un mot $w$ +de $L$, on peut savoir par quelle règle démarre nécessairement une +dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont +les fils de la racine dans tout arbre d'analyse de $w$). (5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$, expliquer comment trouver tous les arbres d'analyse du mot $awbc$ |