Interrogation écrite

Automates et langages - RICM

23-24 mars 2000

Indication: lire attentivement les titres des exercices

1  Synthèse, déterminisation, minimisation

Pour le langage L qui consiste de tous les mots sur {a,b} contenant un sous-mot aba écrire l'expression régulière et trouver l'automate déterministe minimal acceptant ce langage.

2  Automate ® expression

Trouver l'expression régulière pour le langage de l'automate A = (Q,S,q₀,F,D) avec Q = {p,q,r}, S = {0,1,2}, q₀ = p, F = {q,r}, D = {p1q,p2r,r0q,q0p,r1r}

3  Intersection

Construire un automate qui accepte tous les mots sur {a,b} avec un nombre pair de a et un nombre multiple de 3 de b. (par exemple abbabbbb est de cette forme).

4  L'addition - c'est trop compliqué

Montrer que le langage S = {a^m bⁿ c^m+n| m,n Î N} n'est pas régulier.

File translated from T_EX by T_TH, version 2.25.
On 28 Mar 2000, 19:27.