summaryrefslogtreecommitdiffstats
path: root/controle-20170207.tex
diff options
context:
space:
mode:
Diffstat (limited to 'controle-20170207.tex')
-rw-r--r--controle-20170207.tex19
1 files changed, 15 insertions, 4 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex
index e8a0d10..ac9d9ca 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -138,9 +138,16 @@ représenté par la figure suivante :
(0) De quelle sorte d'automate s'agit-il ? (Autrement dit : est-il
déterministe ou non ? avec transitions spontanées ou non ?)
-(1) Décrire brièvement, en français, le langage $L$ reconnu (=accepté)
-par l'automate en question, puis donner une expression rationnelle qui
-le dénote.
+(1a) Décrire brièvement, en français, le langage $L$ reconnu
+(=accepté) par l'automate en question, puis donner une expression
+rationnelle qui le dénote. (On pourra préférer traiter la question
+(1b) d'abord.)
+
+(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
+rapidement les réponses aux questions suivantes et ainsi détecter des
+erreurs lors des transformations des automates.)
(2) Éliminer les transitions spontanées de l'automate, s'il y en a.
(On supprimera les états devenus inutiles.)
@@ -171,7 +178,7 @@ Ne pas hésiter à introduire des notations intermédiaires.)
\smallbreak
-(1) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
+(1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$. Le chemin par
les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
c'est-à-dire le langage dénoté par $a{*}ba{*}$. L'automate dans son
@@ -182,6 +189,10 @@ nombre total d'occurrences de la lettre $x$ dans le mot $w$). C'est
le langage dénoté par l'expression rationnelle $b{*}ab{*} |
a{*}ba{*}$.
+(1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à
+$L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y
+appartiennent pas.
+
\smallbreak
(2) La ε-fermeture de l'état $X$ est $\{X,A,B\}$ ; la ε-fermeture de