TP Automates et Langages MP*1
TP OCaml — Automates et Langages
On cherche à implémenter les automates déterministes en OCaml, puis à vérifier des propriétés : un mot
est-il reconnu par un automate ? Deux automates sont-ils équivalents ?
On définit le type suivant :
type afd = {finaux : bool array; delta : int array array};;
Soit A = (Q, Σ, δ, q0 , F ) un AFD, on représente :
– l’état initial par l’état 0 ;
– la fonction de transition : on assimile Σ à [[0, |Σ|−1]], par un tableau de tableaux, de type int array array,
où si delta est un tel tableau, q ∈ Q et a ∈ Σ, alors delta.(q).(a) est égal à δ(q, a) s’il est défini et
−1 sinon.
Exemple 0.1
L’automate représenté par :
q0 a q1 q2
a
admet pour représentation en Caml :
let aut = {finaux = [|false; false; true|];
delta = [| [|1; -1|]; [|1; 2|]; [|1; -1|] |]};;
1 Reconnaissance d’un mot par un automate
On représente un mot comme une chaîne de caractères de type ‘string‘, et on dispose d’une fonction
num (a: char) : int qui associe, à un caractère a, un entier entre 0 et |Σ| − 1 :
let num a = [Link] a - [Link] 'a'
1. Définir l’automate a3 qui reconnaît le langage des mots qui contiennent au moins un a, et l’automate a4
qui reconnaît le language des mots qui contiennent au moins un b.
2. Écrire une fonction delta_etoile (aut: afd) (q: int) (u: string) : int qui calcule δ ∗ (q, u). La
fonction renverra −1 s’il y a un blocage dans le calcul.
3. En déduire une fonction reconnu (aut: afd) (u: string) : bool qui détermine si un mot est reconnu
par un automate.
4. Vérifier que sur l’exemple ci-dessus, le mot aabab est reconnu alors que le mot aabb n’est pas reconnu.
2 Opérations algébriques
On cherche à construire les opérations algébriques classiques pour les automates : union, intersection,
complémentaire, (étoile de Kleene).
5. Écrire une fonction taille_etats (aut: afd) : int qui renvoie le nombre d’état de l’automate aut.
6. Écrire une fonction taille_alphabet (aut: afd) : int qui renvoie le cardinal de l’alphabet de l’au-
tomate aut.
T. Lopez Page 1 Louis-le-Grand
TP Automates et Langages MP*1
2.1 Complémentaire
Un AFD est complet si il n’y a jamais de blocage, c.-à-d. si pour tout état q et pour toute lettre a, δ(q, a)
est bien défini.
7. Écrire une fonction is_complete (aut : afd) : bool qui vérifie si l’automate est complet.
8. Écrire une fonction complete (aut : afd) : aut qui complète l’automate en ajoutant un état puit. Si
l’automate est déjà complet, il n’est pas modifié.
9. Écrire une fonction complement (aut : afd) : aut qui calcule l’automate du complémentaire.
10. Définir l’automate a6 avec deux états qui reconnaît les mots qui contiennent au plus un a. L’automate
obtenu n’est pas complet. Tester les fonctions précédentes sur l’automate a6.
2.2 Union, intersection : Automate Produit
Pour construire un automate pour l’union et l’intersection, on définit l’automate produit. Il consiste à
effectuer les exécutions des deux automates en parallèle.
À partir de deux automates A = (P, Σ, δA , p0 , FA ) et B = (R, Σ, δB , r0 , FB ), on définit l’automate produit
A × B = (Q, Σ, δ, q0 , F ) avec :
– Q=P ×R
– q0 = (p0 , r0 )
– La relation de transition δ est défini pour p ∈ P , r ∈ R et a ∈ Σ :
a a a
→ (p′ , r′ ) si et seulement si (p −
(p, r) − → p′ par δA et r −
→ r′ par δB
– F est défini en fonction de FA et de FB selon l’opération qu’on cherche à implémenter :
* Pour l’union, on choisit F = (FA × R) ∪ (P × FB ) (au moins un des deux état est final).
* Pour l’intersection, on choisit F = FA × FB (les deux états sont finaux).
Pour implémenter l’automate produit, il faut transposer les pairs d’états (p, r) (représentés en Caml par
une pair d’entiers) en un entier. On définit la bijection
f: J0, |P | − 1K × J0, |R| − 1K −→ J0, |P ||R| − 1K
(p, r) 7−→ r|P | + p
On dispose alors de deux fonction Caml :
let comp_produit (n1 : int) (q1: int) (q2: int) : int =
if q1 = -1 || q2 = -1 then -1
else q2 * n1 + q1
let dec_produit (n1 : int) (k : int) : int * int =
k mod n1, k / n1
La fonction comp_produit prend en paramètre le nombre d’états de A l’état p et l’état r et renvoie l’état
du produit. La fonction dec_produit prend en paramètre le nombre d’états de A et un état k du produit et
renvoie les deux états p et r
11. Écrire une fonction delta_produit (aut1: afd) (aut2: afd) : int array array qui calcule la fonc-
tion de transition de l’automate produit. On supposera que aut1 et aut2 ont le même alphabet.
12. Écrire une fonction union (aut1: afd) (aut2: afd) : aut qui calcule l’automate de l’union.
13. Écrire une fonction union (aut1: afd) (aut2: afd) : aut qui calcule l’automate de l’intersection.
On pourrait s’intéresser à retirer les états inutiles, ceux qui sont non accessibles ou non co-accessibles.
T. Lopez Page 2 Louis-le-Grand
TP Automates et Langages MP*1
3 Tests sur les langages
On a déjà vu l’appartenance avec reconnu.
let dfs (aut: afd) (start: int) (f: int -> 'a) =
let rec rdfs (visited: int list) (q: int) =
if not ([Link] q visited) then
begin
f q;
let successors = [Link].(q) in
Array.fold_left rdfs (q::visited) successors
end
else visited
(*On part du principe qu'on a déjà visiter l'état -1 de blocage*)
in rdfs [-1] start ;;
14. Écrire une fonction language_is_empty (aut1: afd) (aut2: afd) : aut qui vérifie si le langage de
l’automate est vide. On utilisera le fait que L(A) ̸= ∅ si et seulement si dans A il existe un chemin de
l’état initial vers un état final.
15. Écrire une fonction language_is_included (aut1: afd) (aut2: afd) : aut qui vérifie si L(A1 ) ⊆
L(A2 ). On utilisera le fait que L ⊆ M si et seulement si L ∩ M = ∅.
16. Écrire une fonction are_equivalent (aut1: afd) (aut2: afd) : bool qui vérifie si les deux auto-
mates sont équivalent, c.-à-d. ils reconnaissent le même langage.
17. On définit deux automates qui reconnaissent les mots qui contiennent exactement un a :
let a8 = {finaux = [|false; true|];
delta = [| [|1; 0|]; [|-1; 1|]|]};;
let a9 = intersection a3 a6;;
Vérifier que ces deux automates sont équivalents.
T. Lopez Page 3 Louis-le-Grand
