LA-resume-cours-CB-040928

Informations

• Publié par: Rupev
• Nombre de lectures: 39
• Langue: Français

Extrait

LANGAGES ET AUTOMATES :
PLAN DES COURS (L3INFO)
Ch. Boitet
Université Joseph Fourier (Grenoble 1)
UFR d’Informatique et de Mathématiques Appliquées
23/9/04
Cours 0 (24/9/04)
I. Introduction
I.1 Motivations
Modélisation de nombreux ensembles et processus complexes par des automates et des grammaires. Exemple d’un
automate décrivant les identificateurs de C.
Utilisation de grammaires pour définir des langages (langages de commandes, petits langages spécialisés) et de
plus en plus des classes de documents (DTD XML).
Paradigmes de programmation par automates et programmation par grammaires (lex, yacc, XSLT).
Le cours de LA et le cours d'AS visent à donner des connaissances de base pour préparer au cours de compilation
du M1.
I.2 Objectifs théoriques et pratiques de cet enseignement
Comprendre, modéliser, appliquer.
Seulement 20 séances (cours et TD), pas de cours HARMO ("harmonisation" mathématique cette année), et
horaires beaucoup trop chargés (24-26h+APNEE):
• des compléments seront donnés en cours et éventuellement en TD selon la nécessité;
• nécessité de travailler activement en cours ;
• pas d'exigence de savoir refaire les preuves, mais il faudra les comprendre, et
• très bien savoir les notions de base (définitions, résultats), et les algorithmes.
I.3 Motivation et bref historique
Etude des langues et des langages: Panini en Inde, Aristote, Port Royal… de la rhétorique à la logique et à la
linguistique, en passant par la philologie.
Grammaires formelles : de la linguistique à l’informatique. Harris, Chomsky…
Exemple d'une grammaire ad hoc pour {Alain dit bonjour à Annie, Bertrand dit « Alain dit bonjour à Bérénice » à
Bérénice,…}. Arbres syntaxiques (comme ceux de XML, sans attributs). Impossibilité d'interdire les répétitions.
<phrase> ::= <homme> dit <qqch> à <femme> .
<qqch> ::= bonjour | " <phrase> "
<homme> ::= Alain | Bertrand | Corentin |… (tous les saints du calendrier)
<femme> ::= Annie | Bérénice | Caroline |… (toutes les saintes…)
Avec l'informatique sont nés des langages artificiels, devant être traités par des programmes.
Automates : Turing, puis Arbib, Buci, etc. Liens avec la logique. Les automates sont des modèles de calcul et
forment un pont entre les définitions grammaticales, ou algébriques, et les programmes.
I.4 Plan du cours de LA
Contenu : automates d'états finis et langages EF, langages rationnels, expressions régulières, grammaires linéaires à
droite ou à gauche: notions équivalentes en théorie et utiles chacune à sa manière pour construire des analyseurs
lexicaux.
1/1Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
On parle d'abord des automates d'états finis, déterministes ou non avec différentes techniques (opérations
implémentant celles sur les langages, plus déterminisation et minimisation). On montre qu'ils définissent
exactement les langages "rationnels", descriptibles par des expressions régulières. Enfin, on revient aux
grammaires et on complète les techniques de passage entre toutes ces définitions possibles d'un langage EF.
II. Mots et langages
II.1 Vocabulaires, alphabets, mots
Différence entre vocabulaire (potentiellement infini) comme les idf de C et un alphabet fini.
En pratique, on utilise des vocabulaires infinis pour définir des langages.
Mais on montre qu’on peut, à l’aide d’une définition en 2 temps, se restreindre à un alphabet, {0,1} par exemple.
Un alphabet (fini) est formé de symboles (ou caractères, lettres) distinguables.
Définition d’un mot (ou chaîne) w comme une suite finie sur V. Mot vide ε. Ensemble V*.
Longueur |w|. Nombre d'occurrences de a∈V dans w (longueur relative à a) : #(w,a) ou |w| .a
Relations sur les mots : préfixe, infixe, suffixe.
Opérations sur les mots : concaténation (u.v), division à gauche (u\v), à droite (u/v).
Autre définition possible des mots par induction structurelle : V* = <V∪{ε}, {.}> = <{ε}, {D : u→ux | x∈V}>x
Définition de cette notion: E = <Base, Règles>. Principe d'une démonstration par IS. [Feuille]
II.2 Langages en général
Définition d’un langage formel L sur V : L ⊆ V*.
n nTypes de définition : extensionnelle (liste finie ou notation algébrique comme {a b | n≥0}), intentionnelle (par
propriété), inductive, grammaticale, par expressions (on verra les expressions régulières), par automate, et par
programmes (d'analyse ou de génération).
On veut bien sûr qu'un langage, même infini, soit défini de façon finie… cette définition étant elle-même formelle
et écrite dans un autre langage, dit métalangage.
Nombre des langages possibles : puissance du continu (autant que de réels). On ne pourra donc en caractériser
qu’un « petit » sous-ensemble par des descriptions finies.
Cours 1 (27-28/9/04)
Opérations sur les langages : ensemblistes (union, intersection, différence, complémentaire) et spécifiques (produit,
itération, miroir, division à gauche, à droite). Définitions et exemples.
III. Automates finis déterministes
III.1 Définitions
Illustration 1 : automate A1 reconnaissant les chaînes sur {a, b} à nombre impair de a et pair de b.
Automates d’états finis déterministes (AEFdet ou DFSA en anglais). A = (Q, Σ, q , δ, F).0
Extension de la fonction de transition aux mots: δ*(q, ε)=q, et   δ*(q, wa)= δ(δ*(q, w), a)
δ* n'est totale que si δ est totale.
Langages gauche et droit associés à un état : G(q) = {w | δ*(q , w) = q}, D(q) = {w | δ*(q, w) ∈ F}.0
Le langage associé (accepté, engendré) à A est L(A) = ∪ G(f). On a aussi : L(A) = D(q ).f∈ F 0
Cours 2 (4-5/10/04)
Configuration et dérivation dans A : (q, aw) |— (r,w) ssi δ (q, a) = r. Fermeture |—* : (q, w) |—* (r, v) ssi
(q, w) = (r, v) ou [w=uav et (q, w) = (q, uav) |—* (p, av) |— (r, v)].
Langage associé (accepté, engendré) à un AEFdet A : L(A) = {w | (q ,w) |—*(r,ε) et r ∈ F}.0
Exemple d'exécution, ou "trace d'acceptation".
2/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
Illustration 2 : automate A2 reconnaissant les chaînes sur {a, b, c} commençant par ab et finissant par abc.
Complétude de A : A est complet ssi δ est une application ssi A peut « avaler » tout mot w.
Équivalence : A~B ssi L(A)=L(B).
Revue des notions de relation binaire, relation d'équivalence, fonction, application, injection, surjection.
III.2 Construction raisonnée mais "à la main" d'automates à partir de définitions
Exemple : automate des identificateurs de C.
Possibilité de construire directement un programme de reconnaissance à partir d’un AEFdet.
Illustration 2 (en TD) : automate (complet) A2 reconnaissant {a, b} à nombre de a et de b chacun égal à 2 (mod 3).
Association d'une propriété aux chaînes arrivant à chaque état q (ensemble G(q)).
(Cours) Séquence d’acceptation (dérivation) de w = aabbbabab. Dessin d'un chemin d'acceptation (états entre les
symboles de w). Changement d’état(s) final(s) et du langage associé.
Illustration 3 (en cours) : construction directe d'un automate (incomplet) A3 reconnaissant les mots sur {a, b, c}
commençant par ab, bc ou ca et ne finissant pas pas abc, en créant des états q associés à des propriétés sur les
langages G(q).
III.3 Définitions et premières propriétés des « langages d’états finis »
3.1 Extension de la fonction de transition aux mots et aux ensembles d’états
δ*(q, ε)=q, et   δ*(q, wa)= δ(δ*(q, w), a)
δ*(H, w)={δ*(q, w) | q∈H} = {r | (∃q∈H)[(q,w)|—*(r, ε)]}.
δ* n'est totale que si δ est totale.
3.2 Définition et démonstration de propriétés intéressantes par les automates
Classe « EF(V) » « EF » ou des langages « d’états finis » sur V.
Tout langage fini est d’états finis (arbre des préfixes). Le langage total V* est d’états finis.
La complétion d’un AEFdet est toujours possible : algorithme de construction de A'=Comp(A)≈A. Donc tout EF
est reconnaissable par un AEFdet complet.
Stabilité de EF par complémentation : construction de Bar(A) = (Q', V, q , δ', Q'—