Aspects Algébriques
- 1.
- Déterminiser les automates suivants :
[]
![\psfig{file=auto8.1.eps}](img1.gif) |
[]
![\psfig{file=auto8.2.eps}](img2.gif) |
- 2.
- Construire des automates déterministes qui reconnaissent les
langages suivants. En déduire des automates déterministes
qui reconnaissent les complémentaires de ces langages :
- (a)
- L'ensemble des mots sur l'alphabet
qui
contiennent trois fois le symbole 1.
- (b)
- L'ensemble des mots sur l'alphabet
qui
comportent au moins un 1.
- (c)
-
- (d)
-
- (e)
-
- (f)
-
![$(ab\vert a)^\star ba$](img7.gif)
- 3.
- On définit la famille d'automates suivants :
avec
Dessiner
,
et
.
Puis montrer que le
déterminisé de
a toujours 2n états.
- 4.
- Donner un automate déterministe reconnaissant les langages :
- (a)
-
- (b)
-
![${\cal L}_2=\{w/(\vert w\vert=2p\,\wedge\,w
\mbox{ ne contient pas }bb)\,
\bigvee\,(\vert w\vert=2p+1\,\wedge\,w\mbox{ contient }bb)\}$](img22.gif)
Jean-Baptiste Yunes
2000-02-18