diff options
-rw-r--r-- | controle-20170207.tex | 19 |
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 |