Aspects Algébriques

Les automates finis déterministes

1.

Déterminiser les automates suivants :

[]

[]

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 :

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

avec

• $\Sigma=\{a,b\}$,
• ${\cal Q}_n=\{0,1,\ldots,n-1\}$,
• $I=T=\{0\}$,
• $\delta(\{q\},a)=\{q+1 \bmod n\}$, $\forall\, 0\leq q\leq n-1$,
• $\delta(\{0\},b)=\phi$,
• $\delta(\{q\},b)=\{0,q\}$, $\forall\, 1\leq q\leq n-1$,

Dessiner ${\cal A}_3$, et ${\cal A}_4$. Puis montrer que le déterminisé de ${\cal A}_n$ a toujours 2ⁿ é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)\}$