Aspects Algébriques

Les automates finis déterministes

1.
Déterminiser les automates suivants :
[] \psfig{file=auto8.1.eps} [] \psfig{file=auto8.2.eps}
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 $\{0,1\}$ qui contiennent trois fois le symbole 1.
(b)
L'ensemble des mots sur l'alphabet $\{0,1\}$ qui comportent au moins un 1.
(c)
$(a\vert b)^\star ab$
(d)
$(a\vert b)^\star ab(a\vert b)^\star$
(e)
$(ab\vert abc)^\star$
(f)
$(ab\vert a)^\star ba$
3.
On définit la famille d'automates suivants :

\begin{displaymath}{\cal A}_n=<\Sigma,{\cal Q}_n,I,T,\delta>,\, n\geq 1\end{displaymath}

avec Dessiner ${\cal A}_3$, et ${\cal A}_4$. Puis montrer que le déterminisé de ${\cal A}_n$ a toujours 2n états.
4.
Donner un automate déterministe reconnaissant les langages :
(a)
${\cal L}_1=\{w/\vert w\vert=2p\,\vee\,w
\mbox{ ne contient pas }bb\}$
(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)\}$


Jean-Baptiste Yunes
2000-02-18