diff options
Diffstat (limited to 'controle-20180206.tex')
| -rw-r--r-- | controle-20180206.tex | 40 |
1 files changed, 21 insertions, 19 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex index 4503e0a..8ab48c3 100644 --- a/controle-20180206.tex +++ b/controle-20180206.tex @@ -107,7 +107,7 @@ L'usage des appareils électroniques est interdit. Durée : 1h30 -Barème \emph{indicatif} : 7 points par exercices +Barème \emph{indicatif} : 7 points par exercice \ifcorrige Ce corrigé comporte 8 pages (page de garde incluse) @@ -215,9 +215,10 @@ On part bien d'un automate $\mathscr{A}_3$ déterministe complet sans état inaccessible. La première étape de l'algorithme de minimisation sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et $SAT,SBT$ de l'autre. Ensuite on sépare $S$ et $SA$ et $SB$ (car le -premier ne conduit qu'à des états non finaux, le second conduit à des -états finaux par la transition étiquetée $a$, et le troisième conduit -à des états finaux par la transition étiquetée $b$). On obtient +premier ne conduit qu'à des états non finaux, le deuxième conduit à un +état final par la transition étiquetée $a$, et le troisième conduit à +un état final par la transition étiquetée $b$). Les étapes suivantes +ne conduisent pas à d'autres séparations d'états. On obtient finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ : \begin{center} @@ -334,13 +335,13 @@ V &\rightarrow x \;|\; y \;|\; z\\ \end{aligned} \] (On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les -parenthèses servent comme on s'y attend, et $x,y,z$ sont trois choses +parenthèses servent comme on s'y attend, et $x,y,z$ sont trois opérandes auxquelles on peut vouloir appliquer ces opérations.) La grammaire en question est inambiguë (on ne demande pas de le démontrer). -(1) Donner les arbres d'analyse des mots suivants : +(1) Donner les arbres d'analyse (=de dérivation) des mots suivants : (a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$, (c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$, (e) $(x\mathbin{\#}y)\mathbin{@}z$. @@ -454,17 +455,18 @@ On obtient les arbres d'analyse suivants : \end{corrige} (2) En considérant que $(w)$ a le même effet / la même valeur -que $w$ : (a) Quelle opération parmi $\#$ et $@$ est +que $w$ : (a) L'une des deux opérations $\#$ et $@$ est-elle prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » et « $u\boxplus v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».} -sur l'autre ?\quad (b) L'opération $\#$ s'associe-t-elle\footnote{On dit - qu'une opération binaire $\boxdot$ \emph{s'associe à gauche} lorsque - « $u\boxdot v\boxdot w$ » se comprend comme « $(u\boxdot v)\boxdot - w$ », et \emph{s'associe à droite} lorsque « $u\boxdot v\boxdot w$ » - se comprend comme « $u\boxdot (v\boxdot w)$ ».} à gauche ou à -droite ?\quad (c) L'opération $@$ s'associe-t-elle à gauche ou à droite ? +sur l'autre ? Laquelle ?\quad (b) L'opération $\#$ +s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$ + \emph{s'associe à gauche} lorsque « $u\boxdot v\boxdot w$ » se + comprend comme « $(u\boxdot v)\boxdot w$ », et \emph{s'associe à + droite} lorsque « $u\boxdot v\boxdot w$ » se comprend comme + « $u\boxdot (v\boxdot w)$ ».} à gauche ou à droite ?\quad +(c) L'opération $@$ s'associe-t-elle à gauche ou à droite ? \begin{corrige} (a) Les arbres d'analyse (b) et (c) de la question (1) montrent que @@ -487,13 +489,13 @@ exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$ Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$ (cf. le paragraphe précédent). On dira que deux langages $L,M$ disjoints (c'est-à-dire $L\cap M = \varnothing$) sont -\emph{calculablement séparables} lorsqu'il existe un $E$ décidable tel -que $L \subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où -$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le -cas contraire, on les dit \emph{calculablement inséparables}. +\emph{calculablement séparables} lorsqu'il existe un langage $E$ +décidable tel que $L \subseteq E$ et $M \subseteq (\mathbb{N}\setminus +E)$ (où $\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; +dans le cas contraire, on les dit \emph{calculablement inséparables}. (1) Expliquer pourquoi deux langages $L,M$ disjoints sont -calculablement séparables si et seulement si il existe un algorithme +calculablement séparables si et seulement s'il existe un algorithme qui, prenant en entrée un élément $x$ de $\mathbb{N}$ : \begin{itemize} \item termine toujours en temps fini, @@ -527,7 +529,7 @@ que $M$ est disjoint de $E=L$). On cherche maintenant à montrer qu'il existe deux langages $L,M$ \emph{semi-décidables} disjoints et calculablement inséparables. -Pour cela, appelle $L$ l'ensemble des couples\footnote{Pour être +Pour cela, on appelle $L$ l'ensemble des couples\footnote{Pour être rigoureux, on a fixé un codage permettant de représenter les programmes $e$, les entrées $x$ à ces programmes, et les couples $(e,x)$ comme des éléments de $\mathbb{N}$. Il n'est pas nécessaire |