diff options
Diffstat (limited to 'controle-20170207.tex')
| -rw-r--r-- | controle-20170207.tex | 28 |
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 |