diff options
| author | David A. Madore <david+git@madore.org> | 2017-01-31 10:55:52 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2017-02-05 12:40:09 +0100 |
| commit | 8f19ff7b553d51917a8bc449ba4cc49f84d20e3f (patch) | |
| tree | 052d277454e9ab91cf06faa027ace9ef2f517e67 | |
| parent | 65e21580733785d662b6ebda4e6b85b9c5b400b8 (diff) | |
| download | inf105-8f19ff7b553d51917a8bc449ba4cc49f84d20e3f.tar.gz inf105-8f19ff7b553d51917a8bc449ba4cc49f84d20e3f.tar.bz2 inf105-8f19ff7b553d51917a8bc449ba4cc49f84d20e3f.zip | |
Offer additional question to allow checking for mistakes.
| -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 |