Langages rationnels et automates

Cours langages rationnels et automates, tutoriel & guide de travaux pratiques en pdf.

Parcours d’un arbre

Ce court chapitre a pour but d’expliciter différentes methodes utilisees pour lister les elements d’un arbre de façcon non ambigaue, de telle sorte qu’on puisse reconstituer sa structure µa l’aide de cette seule liste. On verra que la distinction faite dans les arbres binaires entre feuilles et n¾uds permet de resoudre facilement ce probleme, quand au contraire il faut davantage d’e®ort pour donner une description non ambigaue d’un squelette d’arbre binaire.
Dans ce qui suit, on utilisera comme exemple privilegi celui de l’arbre qui est dessin dans la figure 2.1, a  et dont les feuilles sont des entiers, les n¾uds des caracteres.

Parcours en largeur d’abord

Description de l’ordre militaire

Le premier type de parcours que nous allons ¶ecrire para^³t sans doute le plus naturel, m^eme si ce n’est pas le plus simple µa programmer.
Certains l’appellent le parcours militaire d’un arbre, puisqu’il fait penser aµ l’axiome militaire bien connu qui donne la priorit¶e au plus ancien dans le grade le plus elev¶. Il su±t d’imaginer qu’en descendant dans l’arbre on descend dans la hi¶erarchie, et qu’on dispose les ¯ls du plus ancien au plus jeune, pour faire le rapprochement.
On peut ¶egalement d¶ecrire cet ordre de parcours en disant qu’on liste les n¾uds et feuille par ordre croissant de profondeur, et de gauche aµ droite pour une profondeur donn¶ee. C’est pourquoi d’autres l’appellent le parcours en largeur d’abord.
Dans le cas de notre exemple de la ¯gure 2.1 page pr¶ec¶edente, ce parcours s’¶ecrit donc :
a b c 1 2 3 d e 6 4 5: µ
La rµegle de reconstitution est simple : le premier el¶ement ¶ecrit est la racine de l’arbre. A chaque fois qu’on dessine un n¾ud on dessine les deux ar^etes pendantes qui en proviennent, et au fur et aµ mesure de la lecture, on remplit les trous ainsi constitu¶es, de gauche µa droite. . .
Reste µa programmer ce parcours en Caml.

Programmation Caml
Nous aurons tout d’abord aµ d¶e¯nir le type qui correspond aµ la description de notre arbre. Il s’agira d’une liste d’¶el¶ements qui seront ou bien des feuilles ou bien des n¾uds, ce qui s’¶ecrit par exemple ainsi en Caml :
type (‘f,’n) listing_d’arbre = F of ‘f | N of ‘n ;;
Le programme 2.1 permet alors de parcourir dans l’ordre militaire un arbre donn¶e en argument.
Programme 2.1 Parcours d’un arbre binaire en ordre militaire
let parcours_militaire a = let rec parcours_rec n¾uds_pendants = match n¾uds_pendants with |[]->[] | Feuille(f) :: reste
-> (F f) :: (parcours_rec reste)
| N¾ud(n,g,d) :: reste
-> (N n) :: (parcours_rec (reste @ [ g ; d ]))
in parcours_rec [a] ;;
On peut appliquer ce programme aµ notre arbre exemple, et voici le r¶esultat :
#parcours_militaire exemple ;;
– : (int, char) listing_d’arbre list = En revanche, la reconstruction de l’arbre aµ partir d’une telle liste est un problµeme beaucoup plus ardu. . .

Parcours en profondeur d’abord

Nous envisageons maintenant d’autres m¶ethodes de parcours qui sont plus proches de la structure na-turellement r¶ecursive des arbres, ce qui facilitera la programmation, et qui justi¯e qu’on les pr¶efµerera au parcours militaire.
L’id¶ee des trois parcours qui suivent est la m^eme, et nous fera descendre tout en bas de l’arbre sur sa gauche avant de s’int¶eresser aux feuilles plus aµ droite : c’est ce qu’on appelle un parcours en profondeur d’abord.

Parcours pr¶e¯xe, in¯xe, su±xe
Ces trois parcours s’appuient sur la structure r¶ecursive des arbres : on applique r¶ecursivement le parcours aux sous-arbres gauche et droit, et c’est le moment oµu on liste le n¾ud-pµere qui caract¶erise ces trois di®¶erents parcours.
Dans le parcours pr¶e¯xe d’un n¾ud (n; g; d), on commence par lister n, puis on parcourt le sous-arbre g et en¯n le sous-arbre d.
On obtient ainsi, dans le cas de notre arbre exemple, la s¶equence a b 1 2 c 3 d e 4 5 6:
Dans le parcours in¯xe d’un n¾ud (n; g; d), on commence par parcourir le sous-arbre gauche, puis on liste n, et on termine par le sous-arbre d.
On obtient pour notre exemple la s¶equence 1 b 2 a 3 c 4 e 5 d 6:
Dans le parcours su±xe (on dit aussi post¯xe), en¯n, on commence par parcourir les deux sous-arbres g et d et on termine en listant n, ce qui, pour notre exemple, fournit la s¶equence 1 2 b 3 4 5 e 5 d c a:

Programmation en Caml
Ces trois parcours se pr^etent tout aµ fait bien aµ une programmation r¶ecursive, et on obtient imm¶ediatement le programme 2.2, qui met d’ailleurs en ¶evidence la ressemblance de ces trois algorithmes de parcours.
Programme 2.2 Parcours d’un arbre binaire en ordres pr¶e¯xe, in¯xe et su±xe
let rec parcours_pr¶efixe = function
| Feuille(f) -> [F f]
| N¾ud(n,g,d) -> [N n] @ (parcours_pr¶efixe g) @ (parcours_pr¶efixe d) ;;
let rec parcours_infixe = function
| Feuille(f) -> [F f]
| N¾ud(n,g,d) -> (parcours_infixe g) @ [N n] @ (parcours_infixe d) ;;
let rec parcours_suffixe = function
| Feuille(f) -> [F f]
| N¾ud(n,g,d) -> (parcours_suffixe g) @ (parcours_suffixe d) @ [N n] ;;

Problµeme inverse
µ A la di®¶erence du parcours en largeur d’abord, il n’est pas trµes di±cile de proc¶eder µa la reconstitution de l’arbre initial aµ partir de sa description pr¶e¯xe, comme le montre le programme 2.3.
Programme 2.3 Reconstitution d’un arbre binaire aµ partir de sa description en ordre pr¶e¯xe
let recompose_pr¶efixe l =
let rec recompose = function
| (F f) :: reste -> Feuille(f), reste
| (N n) :: reste -> let g, reste = recompose reste in
let d, reste = recompose reste in
N¾ud(n,g,d),reste
| [] -> failwith « Description pr¶efixe incorrecte »
in match recompose l with | a,[] -> a
| _ -> failwith « Description pr¶efixe incorrecte » ;;
Contrairement µa ce que certains s’imaginent parfois, le parcours su±xe d’un arbre ne fournit pas la description sym¶etrique du parcours in¯xe, et il ne su±t pas d’appliquer recompose pr¶efixe au miroir d’une liste pour obtenir recompose suffixe.
Mais une approche directe conduit aµ la solution, qui consiste aµ construire l’arbre ¯nal en faisant pousser petit aµ petit l’arbre aµ partir de ses feuilles les plus basses µa gauche. C’est ce que fait le programme 2.4 page suivante.
Programme 2.4 Reconstitution d’un arbre binaire aµ partir de sa description en ordre su±xe
let recompose_suffixe l =
let rec recompose ss_arbres liste = match ss_arbres,liste with | a,(F f) :: reste
-> recompose (Feuille(f) :: a) reste
| d :: g :: a,(N n) :: reste
-> recompose (N¾ud(n,g,d) :: a) reste
| [ arbre ],[]
-> arbre
| _ -> failwith « Description suffixe incorrecte » in recompose [] l ;;
Il nous reste le problµeme de la reconstitution d’un arbre binaire aµ partir de sa description en ordre in¯xe. Et lµa, surprise ! on s’aper»coit que des trois m¶ethodes de parcours d’arbre que nous venons de d¶ecrire, c’est la seule qui soit ambigÄue ! C’est-µa-dire qu’on peut trµes bien trouver un autre arbre que celui qui a et¶ propos¶e dans la ¯gure 2.1 page 27 avec pourtant le m^eme parcours in¯xe, µa savoir 1 b 2 a 3 c 4 e 5 d 6.
Par exemple, on v¶eri¯era que l’arbre de la ¯gure 2.2 a aussi ce parcours in¯xe.

Exercices pour le chapitre 2

Exercice 2.1 Reconstitution µa partir de l’ordre militaire
¶ Ecrire une fonction Caml
recompose_militaire : (‘f,’n) listing_d’arbre list -> (‘f, ‘n) arbre_binaire
qui reconstitue un arbre binaire aµ partir de sa description en ordre militaire.
Exercice 2.2 Conversions pr¶e¯xe/su±xe
¶ Ecrire une fonction Caml qui aµ partir de la description pr¶e¯xe d’un arbre produit la description su±xe (sans reconstruire l’arbre, bien s^ur). Que pensez-vous de la fonction inverse ?

I Arbres 
1 Arbres binaires 
1.1 Définitions et notations
1.1.1 Définitions formelle d’un arbre binaire
1.1.2 Définitions des arbres binaires en Caml
1.1.3 Une indexation des ¶el¶ements constitutifs d’un arbre
1.2 Notion de profondeur dans un arbre
1.3 Squelette d’un arbre binaire
1.4 Combinatoire des arbres et squelettes binaires
1.4.1 N¾uds et feuilles
1.4.2 Profondeur et taille
1.4.3 Denombrement des squelettes binaires
1.5 Exercices pour le chapitre 1
2 Parcours d’un arbre 
2.2 Parcours en profondeur d’abord
2.2.1 Parcours pr¶e¯xe, in¯xe, su±xe
2.2.2 Programmation en Caml
2.2.3 Problµeme inverse
2.3 Exercices pour le chapitre 2
3 Arbres de recherche 
3.1 D¶e¯nition d’un arbre binaire de recherche
3.2 Recherche d’un ¶el¶ement
3.3 Structure dynamique de recherche
3.3.1 Ajout d’un ¶el¶ement
3.3.2 Suppression d’un ¶el¶ement
3.3.3 Application au tri
4 Tri et tas 
4.1 G¶en¶eralit¶es
4.1.1 Files de priorit¶e
4.1.2 Tas
4.1.3 Impl¶ementation des tas µa l’aide de tableaux
4.2 Percolation
4.3 Le tri par les tas
4.3.1 Programmation
4.3.2 ¶Evaluation
5 Arbres n-aires et expressions arithmetiques 
5.1 Arbres n-aires
5.2 Expressions arithm¶etiques
5.2.1 Une d¶e¯nition
5.2.2 Syntaxe concrµete et syntaxe abstraite
5.2.3 Expressions et arbres
5.3 D¶erivation formelle
5.4 Exercices pour le chapitre 5
II Automates 
6 Automates ¯nis deterministes ou non deterministes 
6.1 Automates ¯nis d¶eterministes
6.2 Impl¶ementation en Caml d’un afd
6.3 Automates ¯nis non d¶eterministes
6.3.1 Pr¶esentation informelle
6.3.2 D¶e¯nition math¶ematique
6.4 Impl¶ementation en Caml d’un afnd
6.5 D¶eterminisation d’un afnd
6.5.1 Algorithme de d¶eterminisation
6.5.2 Programmation en Caml
6.6 Exercices pour le chapitre 6
7 Langages rationnels et automates 
7.1 Langages rationnels et expressions r¶eguliµeres
7.2 Le th¶eorµeme de Kleene
7.2.1 Des langages rationnels aux automates
7.2.2 Des automates aux langages rationnels
7.3 Langages non rationnels
7.4 Exercices pour le chapitre 7
III Corrig¶e de tous les exercices 
1 Exercices sur Arbres binaires
2 Exercices sur Parcours d’un arbre
3 Exercices sur Arbres de recherche
5 Exercices sur Arbres n-aires
6 Exercices sur Automates ¯nis
7 Exercices sur Langages rationnels et automates