summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-02-01 16:33:15 +0100
committerDavid A. Madore <david+git@madore.org>2017-02-05 12:40:09 +0100
commitaac882346c69c3576e7e2ebc230bf89fde67f0e6 (patch)
tree6bbaf77287115a39c419d8f16e43c8bd195c050e
parent87d7cac42f7477cebc2670e3dda57deffb23f2c9 (diff)
downloadinf105-aac882346c69c3576e7e2ebc230bf89fde67f0e6.tar.gz
inf105-aac882346c69c3576e7e2ebc230bf89fde67f0e6.tar.bz2
inf105-aac882346c69c3576e7e2ebc230bf89fde67f0e6.zip
More re-reading and discussion with Bertrand.
-rw-r--r--controle-20170207.tex28
1 files changed, 16 insertions, 12 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex
index a3637f6..7d6a2bc 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -93,9 +93,8 @@ très visible dans les copies où commence chaque exercice.
\medbreak
-Le sujet étant délibérément trop long pour le temps imparti, il sera
-possible d'obtenir la totalité des points en ne traitant qu'une partie
-des exercices.
+Le sujet étant long pour le temps imparti, il ne sera nécessaire de
+traiter toutes les questions pour obtenir la totalité des points.
\medbreak
@@ -108,6 +107,8 @@ L'usage des calculatrices électroniques est interdit.
Durée : 1h30
+L'énoncé comporte 4 pages.
+
\pagebreak
@@ -150,7 +151,7 @@ rationnelle qui le dénote. (On pourra préférer traiter la question
(1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
$\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
-(Note : il est conseillé de réutiliser ces mots pour vérifier
+(Note : il est recommandé de réutiliser ces mots pour vérifier
rapidement les réponses aux questions suivantes et ainsi détecter
d'éventuelles erreurs lors des transformations des automates.)
@@ -172,9 +173,10 @@ langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.
(6) Décrire brièvement, en français, le langage ce langage
complémentaire $\overline{L}$.
-(7) Donner une expression rationnelle qui reconnaît ce langage
-complémentaire $\overline{L}$. (Cette question est plus difficile.
-Ne pas hésiter à introduire des notations intermédiaires.)
+(7) (Question bonus, plus longue, à ne traiter qu'en dernier.) Donner
+une expression rationnelle qui dénote ce langage
+complémentaire $\overline{L}$. (Ne pas hésiter à introduire des
+notations intermédiaires.)
\begin{corrige}
(0) Il s'agit d'un automate non-déterministe à transitions spontanées,
@@ -441,8 +443,8 @@ $w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
si $L_G = \Sigma^*$.) Indication : on peut tester tous les mots
possibles.
-(3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui
-fournit en entrée un algorithme $T$ qui décide un langage $L_T
+(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on
+lui fournit en entrée un algorithme $T$ qui décide un langage $L_T
\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
« faux », et $L_T$ est le langage des mots sur lesquels il répond
@@ -563,7 +565,8 @@ langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère le
langage engendré par la grammaire identique à $G$ mais ayant $T$ pour
axiome).
-(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,T)$.
+(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,T)$ (au
+moins deux de chaque).
(1) Expliquer brièvement pourquoi $L(G)$ est l'ensemble des mots de la
forme $u_1\cdots u_k$ avec $u_i \in L(G,T)$, et pourquoi $L(G,T)$ est
@@ -572,8 +575,9 @@ conséquent, $L(G,T)$ est l'ensemble des mots de la forme $a u_1 \cdots
u_k b u'_1\cdots u'_{\ell} c$ avec
$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(G,T)$.)
-(2) Comment décrire $L(G)$ de manière simple en fonction de $L(G,T)$ ?
-Y a-t-il inclusion de l'un dans l'autre ?
+(2) Comment décrire $L(G)$ de en fonction de $L(G,T)$ au moyen des
+opérations rationnelles\footnote{C'est-à-dire : union, concaténation,
+ étoile de Kleene.} ? Y a-t-il inclusion de l'un dans l'autre ?
(3) Montrer que tout mot $w$ de $L(G)$ a le même nombre de $a$, de $b$
et de $c$, c'est-à-dire $|w|_a = |w|_b = |w|_c$ où $|w|_x$ désigne le