summaryrefslogtreecommitdiffstats
path: root/controle-20210618.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-06-15 23:27:26 +0200
committerDavid A. Madore <david+git@madore.org>2021-06-15 23:27:26 +0200
commit1534fd4cf5530801af78a819a563912bee16c70b (patch)
tree577ff4b73ef1192cec85604ed77265e11af236b5 /controle-20210618.tex
parent4fcb3c312b48d1c725993cd87898582b9007c7fb (diff)
downloadinf105-1534fd4cf5530801af78a819a563912bee16c70b.tar.gz
inf105-1534fd4cf5530801af78a819a563912bee16c70b.tar.bz2
inf105-1534fd4cf5530801af78a819a563912bee16c70b.zip
Re-read test and fix some problems.
Diffstat (limited to 'controle-20210618.tex')
-rw-r--r--controle-20210618.tex43
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$