La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

LA-resume-cours-CB-040928

9 pages
LANGAGES ET AUTOMATES :PLAN DES COURS (L3INFO)Ch. BoitetUniversité Joseph Fourier (Grenoble 1)UFR d’Informatique et de Mathématiques Appliquées23/9/04Cours 0 (24/9/04)I. IntroductionI.1 MotivationsModélisation de nombreux ensembles et processus complexes par des automates et des grammaires. Exemple d’unautomate décrivant les identificateurs de C.Utilisation de grammaires pour définir des langages (langages de commandes, petits langages spécialisés) et deplus 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 compilationdu M1.I.2 Objectifs théoriques et pratiques de cet enseignementComprendre, modéliser, appliquer.Seulement 20 séances (cours et TD), pas de cours HARMO ("harmonisation" mathématique cette année), ethoraires 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 historiqueEtude des langues et des langages: Panini en Inde, Aristote, Port Royal… de la rhétorique à la logique et à lalinguistique, en passant par la philologie.Grammaires formelles : de la ...
Voir plus Voir moins

Vous aimerez aussi

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'—F) si A' = Comp(A).0
Stabilité de EF par intersection : construction d’un automate A = A1xA2 « pr oduit cartésien » associé à
L(A1)∩L(A2). On en déduit la stabilité par l'union (complémentaire de l'intersection des complémentaires).
Illustration : construction du A3 (cours 2) en combinant deux automates simples (chaînes commençant par ab, bc
ou ca et chaînes ne finissant pas par abc).
3.3 Limitations de la puissance d'un AEFdet.
n nOn ne peut pas reconnaître le langage des parenthèses P = {a b | n∈ N} avec un AEFdet. Démonstration par
nl’absurde : il existerait un état r tel que δ*(q , a ) = r pour une infinité de n, et donc pour un couple (i, j) on aurait0
i j i j j j j j ji≠j et δ*(q , a ) = δ*(q , a ) = r, donc δ*(q , a b ) = δ*(r, b ) = δ*(δ*(q , a ), b ) = δ*(q ,a b ) ∈ F, et l’automate0 0 0 0 0
i jaccepterait aussi a b .
Théorème de l’étoile (« théorème uvw »), forme usuelle (faible) : Si L est EF, soit k le nombre d’états d’un AEFdet
reconnaissant L. Alors tout mot z de L assez long (|z|≥k) peut se décomposer en z=uvw avec 0<|v|≤k de telle façon
p pque, pour tout p, z = uv w soit dans L. Forme "forte" (Hopcroft) : idem, avec 0<|uv|≤k et v≠ε.
A-t-on stabilité de EF par produit (de concaténation) et par inversion (opération « m iroir ») ? C'est apparemment
très difficile à montrer avec ce modèle d’automates déterministes. On y reviendra avec les AEFndet dont on
prouvera qu’ils sont équivalents (décrivent les mêmes langages).
III.4 Complétion et minimisation d’un AEFdet
4.1 Notions préliminaires
Accessibilité d’un état depuis un autre : Acc(q, r) ssi (∃w∈V*)[δ*(q, w) = r]. Algorithme de calcul de la matrice
d'accessibilité.
Simulation d’un AEFdet par un autre.
3/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
Equivalence de 2 états : q≈r ssi D(q) = D(r). Si A est complet, on peut définir récursivement cette équivalence
[k] [k] nd'états via les langages D (q)=D(q) ∩V avec V =∪ V .k 0≤n≤k
4.2 Minimisation d’un AEFdet complet
Algorithme de minimisation (feuille séparée). Exemple.
Preuve de l'équivalence (Min(A)≈A) en cours, et de la minimalité en TD.
Test d'équivalence de deux AEFdet A et B : Min(A) = Min(B) à un renommage près des états.
Cours 3 (11/10/04)
Exemple complet.
IV. AEFndet et déterminisation
IV.1 Définitions
Automates d’états finis non-déterministes (AEFndet ou NFSA en anglais). A = (Q, Σ, I, δ, F) avec δ :
Q x Σ∪{ε}→P(Q). Exemple : automate pour les mots contenant abb.
Configuration et dérivation dans A : (q, xw) |— (r,w) ssi r ∈ δ(q, x).
Extension de la fonction de transition aux mots et aux ensembles d’états.
Langage associé (accepté, engendré) : L(A) = {w | δ*(I, w) ∩ F ≠ ∅}
Applications :
• Recherche de mots dans un texte (ex : reconnaissance de mots-clefs),
• Recherche de motifs dans un texte (ex : certaines erreurs d’orthographe).
Exemples (pris dans la feuille de TD).
Cours 4 (18/10/04)
IV.2 Élimination des transitions vides
Accessibilité d’un état depuis un autre par ε-transitions. E(q) = {r | (q, ε) |—* (r, ε)}
Simulation pour les AEFndet.
IV.3 Déterminisation
Automate des parties (construction dite « des sous-ensembles » ou subset construction).
kComplexité exponentielle de la procédure de déterminisation : un "pire" cas, (a+b)*a(a+b) .
Conséquences: stabilité de EF par union, miroir, et homomorphisme (sur les lettres).
Partie optionnelle (selon avancement)
(Fin du cours 4 si pas assez de temps, et dans ce cas réduction de cette partie.)
V. Transducteurs d’états finis (« sans mémoire »)
La seule mémoire est l’état courant (pas de pile ni de file ou de liste auxiliaire).
Il s’agit souvent de produire un résultat, et pas seulement d’accepter ou de refuser.
V.1 Modèle de Moore
On ajoute à un AEFdet une fonction de sortie qui produit un symbole d’un alphabet Ω par état, soit A = (Q, Σ, Ω,
q , δ, F, λ) avec λ : Q→Ω totale (application). La valeur produite par A sur un mot w à partir d’un état q est la suite0
des symboles produits par les états atteints, état de départ exclus ou inclus. Définissons Val(q,w) par Val(q, ε)=ε
(état de départ exclus) ou Val(q, ε)=λ(q) (état de départ inclus) et Val(q, wa) = Val(q, w).λ(δ(δ*(q, w), a))). Alors
A(w)=Val(q , w).0
4/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
V.2 Modèle de Mealy
On ajoute à un AEFdet une fonction de sortie qui produit un symbole d’un alphabet Ω par transition, soit A = (Q,
Σ, Ω, q , σ = (δ, λ), F) avec σ : Qx(ΣxΩ)→Q, avec δ : QxΣ→Q et λ : QxΣ→Ω de même domaine. On note souvent0
(q, a:b, r) pour σ(q, a, b) = r.
Les machines de Mealy sont appelées aujourd’hui « transducteurs d’états finis déterministes » (TEFdet ou DFSM)
et sont très utilisées pour écrire des « filtres » (transformation de formats simples, par exemple transcription d’un
système de codage à un autre, correction orthographique).
V.3 Modèles non-déterministes (sur le modèle de Mealy)
Définition en étendant à (Σ∪{ε}xΩ∪{ε}) puis à (Σ*xΩ*). Langages associés. Transduction associée (d’une chaîne
vers un langage).
Pas de cours les 25-26/10 ni le 1/11 (A)
Cours 5 (2/11/04) — pour A et B
Remarques complémentaires : les techniques vues sur les AEFndet peuvent être reprises telles quelles. Attention,
pour l’interprétation en transduction, il n’y a pas stabilité par l’intersection.
VI. Langages rationnels et expressions régulières
VI.1 Définitions et équivalence
Langages rationnels : si V={a } , Rat(V) = < {∅, {ε}, {a } }, {∪, •, *}>i 1≤i≤p i 1≤i≤p
Expressions régulières : on suppose V∩{∅, ε, (, ), +, *}=∅ et on pose V =V∪{∅, ε}, V = {(, ), +, *}, V’ =ext pnc
V ∪V . On utilise parfois « | » à la place de « + », et on ajoute parfois le point « • » pour la concaténation.ext pnc
Reg(V) ⊆ V’* est alors défini par Reg(V) = <V ,{R  : u → (u), R  : u,v → u+v, R  : u,v → uv,ext par plus conc
R  : u → u*}>, les règles s’appliquant sur des « facteurs », i. e. des éléments de la base ou de forme (w). Aveceto
cette restriction, le schéma est libre (non ambigu).
Langages réguliers. On définit L : Reg(V) → P(V*) en suivant le schéma précédent.
M est régulier s’il existe une ER e telle que L(e)=M. Attention, on n'a pas en général L(e)=M => L(e*)=M* (ex.
avec e=a+b), donc on doit être plus précis et il faut exiger que e soit un facteur, ou donner des règles permettant de
lever les ambiguïtés éventuelles, en convenant de priorités (*, puis la concaténation, puis +), et d’associativité. On
parlera d'ER "strictes" si elles ont "au moins les parenthèses nécessaires" dans le système précédent, et "allégées"
sinon.
Cours 6 (8-9/11/04)
1. Transformation d'ER "allégées" en ER "strictes" en deux temps: transformation en un arbre d'opérateurs (arbre
abstrait) grâce à un automate à pile réalisant une "analyse de précédence", puis écriture de l'arbre obtenu grâce à
une procédure récursive de parcours infixé.
2. Equivalence entre réguliers et rationnels : L(Reg(V)) = Rat(V).
Démonstration par IS (induction structurelle) dans les deux sens.
Démonstration que Rat(V) ⊆ EF(V) par IS: à partir d'une ER, construction de Thomson d’un AEFndet
« normalisé » (un seul état initial dans lequel rien n'entre, un seul état final d'où rien ne sort, et pas d'état avec plus
de 2 arcs entrants ou plus de 2 arcs sortants).
VI.2 Propriétés
2.1 Règles algébriques sur les expressions régulières
Identités remarquables. Démonstration de (u*)* = u*.
Cours 7 (15/11/04)
Résolution de l'équation X = AX + B avec A, B ⊆ V*. La plus petite solution est A*B, elle est unique si ε∉A, et
sinon A*(B+C) est solution pour tout C ⊆ V*.
5/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
2.2 Équivalence entre rationnels et EF : Rat(V) = EF(V)
Consistance par induction structurelle : déjà vue (construction de Thomson).
Complétude par l'algorithme d'élimination des états utilisant des ER sur les arcs. Soit A = (Q, V, I, δ, F) un
AEFndet, on considère A' = (Q', V, {i}, δ', {f}) où Q' = Q ∪ {i, f}, i et f étant deux nouveaux états, et δ' est formée
des transitions δ de A, auxquelles on ajoute les transitions {(i, ε, q) | q ∈ I} et {(q, ε, f) | f ∈ F}.
Avant chaque étape, on remplace tous les "faisceaux" de transition d'un état p à un état q, {(p, L , q)} par unek kKpq
seule transition, (p, Σ L , q). À chaque étape, on élimine un état q de Q. Pour cela, on considère tous les couples (p,k k
2r) de (Q'-{q}) , p=r étant possible, tels qu'on ait dans l'AEF étendu courant (p, E , q), (q, E , r), et éventuellementpq qr
(q, E , q), sinon on considère que E = ∅. On élimine q et toutes les transitions qui le contiennent, et on ajoute laqq qq
transition (p, E .E *.E ,, r) en se souvenant que ∅*=ε. Après la |Q|-ième étape, il reste une seule transition, (i, E,pq qq qr
f), et E est une ER pour L(A).
Exemple sur A reconnaissant les mots sur {a, b} ayant un nombre impair de a et pair de b.
Il est aussi possible de montrer la complétude par un calcul des chemins d'acceptation d’un AEF A par
"programmation dynamique". Soit Q={q } . On calcule les langages rationnels R représentant les chemins de qi 1≤i≤n ijk i
à q ne passant par aucun état q avec m>k. On a R ={x | δ(qi, x) = qj} [∪{ε} si i=j], R = R ∪j m ij0 ij(k+1) ijk
R .R *.R , et L(A) = ∪ R . L'algoritthme correspondant pourra être fait en TD.i(k+1)k (k+1)(k+1)k (k+1)jk {j | q ∈ F} 0j(n+1)j
Cours 8 (22-23/11/04)
2.3 Dérivées
Définition : L\u = {v | uv ∈ L}. Conséquences directes : L\vide = vide, L\ε = L, vide\u = vide, L\uv = (L\u)\v, donc
L\xv = (L\x)\v si x est une lettre.
Propriétés pour la base, avec x, y 2 lettres : x\vide = vide, x\ε = x, x\y = vide si x≠y, ε sinon.
Propriétés pour les règles : (L+M)\x = L\x + M\x, (LM)\x = (L\x)M+M\x si ε ∈ L, (L\x)M sinon, et (L*)\x =
(L\x)L*.
Exemple : calcul de ((ab*c)*+a(b*ca)*)\ab = b*c(ab*c)+b*ca(b*ca)*.
Théorème : tout langage ER a un nombre fini de dérivées distinctes. (Preuve en cours par interprétation dans
l’AEFmin équivalent, et en TD par IS).
Du coup, on peut calculer directement un automate pour L=L(E) en calculant sous forme d'ER toutes les dérivées
distinctes de L. L’état initial est L\ε=L, tout état contenant ε est final, et δ(M, x) = M\x pour toute lettre x.
Nécessairement, on ne peut produire qu’un nombre fini d’états, et il s’agit d’un AEFdet. Cependant, il peut arriver
qu’on ne voie pas que deux états sont équivalents, i. e. que les ER associées dénotent le même langage (la même
dérivée), et donc qu’on ne produise pas l’AEFmin. Si on veut l'obtenir, on minimise.
VII. Définition équivalente des ER par des grammaires
VII.1 Notion générale de grammaire syntagmatique et types de grammaires
Introduction à la notion de grammaire (analyse d'une phrase française par un arbre, grammaire).
Types principaux de grammaires syntagmatiques. Voir feuille synthétique donnée à part.
Grammaires linéaires droites et gauches (strictes, étendues, généralisées).
Langages associés : notion de dérivation et de forme sententielle. Exemple de grammaire générant
n n nM={a b c  | n> 0}. Définitions : S(G) = {σ | S |—* σ}, L(G)= S(G)∩T*. Ou encore : L(G, A) =
{w∈T* | A |—* w}, et L(G) = L(G, S).
kRemarque sur la définition par induction structurelle : une règle peut être une relation binaire sur U xU et pas
kseulement une fonction de U dans U, et tous les résultats restent valides, y compris le principe de démonstration
par induction structurelle.
Méthode de preuve que L(G)=M. Consistance : trouver une propriété Q(α) sur V* telle que w∈T* & Q(w) ⇒
w∈M, et démontrer Q sur S(G) par IS.
Complétude : soit, pour tout w∈M on donne directement une dérivation de w dans G, soit on fait une induction
(structurelle si M est défini par IS, nœthérienne sinon).
6/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
Cours 9 (29-30/11/04)
VII.2 Equivalences (par transformations effectives)
2.1 AEFndet → GlinD, GlinG
N = Q ∪{S} où S ∉ Q.
GLinD : {S→i | i∈I}∪{p→xr | (p, x, r)∈δ}∪{p→x | (p, x, f)∈δ et f∈F} (1ère forme)
ou {S→i | i∈I}∪{p→xr | (p, x, r)∈δ}∪{f→ε | f∈F} (2ème forme)
GLinG : {S→f | f∈F}∪{r→px | (p, x, r)∈δ}∪{r→x | (i, x, r)∈δ et i∈I} (1ère forme)
ou {S→f | f∈F}∪{r→px | (p, x, r)∈δ}∪{i→ε | i∈I} (2ème forme)
Illustration : automate reconnaissant les mots sur {a, b, c} contenant ab ssi ils ont un nombre pair de c.
2.2 GlinD/G → système d'équations (SElinD/G)
Soit N={X ,…, X } où X est l’axiome. On regroupe les règles de même partie gauche et on remplacei n i
X→γi  | … | γi par l’équation X =γi  + … + γi . On obtient un système linéaire droit ou gauche.i 1 pi i 1 pi
2.3 Système d'équations (SElinD/G) → ER
Résolution par la méthode de Gauss. Pour i de n à 1, on résout en X l’équation i, mise sous forme X =AX +Bi i i
(GlinD) ou X =X A+B (GlinG), et, pour j de i-1 àemplace X par sa valeur.i i i
Cours 10 (6-7/12/04) — Révisions, et
introduction aux langages hors-contexte et
automates à pile
2.4 ER → AEFdet (dérivées)
Rappel : on a vu au VI.2.2 le passage ER → AEFndet (Thomson), qui donne beaucoup d’arcs vides ; on a vu aussi
au VI.2.3 le passage direct ER → AEFdet par les dérivées.
2.5 ER → AEFdet (à partir de l'arbre abstrait de l'ER)
Il existe une méthode de passage direct ER → AEFdet très proche de celle des dérivées, mais travaillant sur l'arbre
abstrait de l'ER, correspondant à un arbre de construction du langage rationnel associé (éléments de base sur les
feuilles, symboles +, • et * sur les nœuds internes). Exemple (si temps).
2.6 Conseils pratiques pour passer d'une caractérisation à l'autre
Par exemple, pour AEF → ER, faire AEF → GlinD → SE → ER et surtout pas le calcul de tous les chemins pour
tout couple (p, q) d'états.
Diagramme général des passages étudiés.
VII.3 Comment montrer qu’un langage n’est pas rationnel
3.1 Par une caractérisation (CNS) de Rat(V)
Théorème de Myhill-Nerode (résumé des équivalences vues).
Raisonnement par l’absurde sur un AEF.
Démonstration de l’existence d’une infinité de dérivées distinctes.
3.2 Par une condition nécessaire mais pas suffisante
Rappel du lemme de l’itération et exemple de raisonnement par l’absurde.
Utilisation de la stabilité par diverses opérations, en particulier par homomorphisme. Exemple :
{wcw | w∈(a+b)*} ∉ Rat(a,b,c) est facile à montrer, d’où {ww | w∈(a+b)*} ∉ Rat(a,b), plus difficile directement,
par effacement des c.
Mention d’un résultat sur les longueurs des mots d’un rationnel : elles forment un ensemble « ultimement
périodique », i. e. périodique à partir d’un certain rang. Ainsi, {w | |w| premier} n’est jamais rationnel.
7/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
Introduction aux hors-contexte
VIII. Grammaires et langages hors-contexte
VIII.1 Grammaires Hctxt (strictes, étendues, généralisées)
On note G = (N, T, P, S) et V = N∪T.
Passage d’une grammaire Hctxt généralisée (ε permis en partie droite) à une grammaire étendue équivalente (S→ε
permise si S n’apparaît jamais en partie droite).
Relations entre les langages associés. Exemples.
VIII.2 Arbres syntaxiques et arbres d'analyse (parse trees)
2.1 Définitions des arbres associés à une grammaire Hctxt
Définition « statique » des arbres syntaxiques : les nœuds sont étiquetés sur V∪{ε}, et à tout sous-arbre de hauteur
1 correspond une règle.
Définition inductive : <{arbres élémentaires des règles}, {substitution}>
Arbres d’analyse : arbres syntaxiques de racine étiquetée S et de feuilles étiquetées sur T∪{ε}.
Définition des « arbres sententiels » par <{S}, {développement d’une feuille par une règle}>
2.2 Coupes et dérivations associées à un arbre d’analyse
Notion de « coupe » d’un arbre syntaxique
Inférences (bottom-up) comme coupes « montant vers la racine ».
Dérivations (top-down) comme coupes « descendant vers les feuilles ».
Dérivations canoniques associées à un arbre d’analyse et interprétation.
VIII.3 Définition du langage associé
3.1 Définition quasi-inductive usuelle, descendante
L(G) = Sent (G) ∩ T* avec Sent(G) = <{S}, {γAδ→γαδ | A→α ∈ P}
Exemple d’utilisation pour établir qu’un langage M est engendré par G.
Lemme des dérivations pour les hors-contexte.
3.2 Définition par les arbres syntaxiques
L(G) = {w | w est le mot associé à la frontière d'un arbre syntaxique de racine S}.
VIII.4 Propriétés
4.1 Ambiguïté d’une grammaire hors-contexte
G est ambiguë si au moins une chaîne a au moins 2 arbres d’analyse différents.
Degré d’ambiguïté d’une chaîne w : k si w a k arbres d’analyse différents. k=∞ est possible.
Résultat annoncé sans démonstration : il existe des langages Hctxt intrinsèquement ambigus.
Pourquoi l’ambiguïté est-elle un mal parfois nécessaire ?
4.2 Equivalence de deux grammaires hors-contexte
Equivalence faible (G~G') : L(G) = L(G’).
Equivalence forte (G≈G') : idem et arbres identiques modulo une bijection de N dans N’.
Exemple de transformation préservant l’équivalence faible : suppression des epsilon.
X. Références
Sur la théorie des ensembles et les bases mathématiques et logiques, voir le site de l’UJF : http://www.ujf-
grenoble.fr/UEL/mathematiques/logique1
[1] Nguyen Huy Xuong (1991) Mathématiques discrètes et informatique. Masson, 412 p.
[2] Claude Benzaken (1991) Systèmes formels. Introduction aux à la logique et à la théorie des langages. Masson, 166 p.
8/9Langages et automates : plan du cours, version de travail le 28/09/04 à 15:05
[3] John C. Martin (1997) Introduction to languages and computation. Mc Graw Hill, 450 p.
[4] John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (2000) Introduction to automata theory, languages and
computation (second edition) (très différente de la première de 1979, il existe une version francaise de 2001). Addison-
Wesley.
[5] Patrice Séébold (1999). Théorie des automates. Méthodes et exercices corrigés. Classes préparatoires, 1er et 2ème cycles
universitaires. Vuibert, Paris, 198 p.
[6] Pierre Wolper (1991). Introduction à la calculabilité. Paris, InterEditions, 268 p.
-o-o-o-o-o-o-o-o-o-o-o-
9/9