cours-info-theo

Description

Université Paris SudLicence d’InformatiqueInformatique Théorique :Théorie des Langages,Analyse Lexicale, SyntaxiqueJean Pierre JouannaudProfesseurAdresse de l’auteur :LIXÉcole PolytechniqueF 91128 Palaiseau CEDEXURL :http://www.lix.polytechnique.fr/ii Table des matièresTable des matières1 Introduction 22 Langages formels 33 Automates de mots finis 43.1 Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.2 non déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Déterminisation d’un automate non déterministe . . . . . . . . . . . 63.3 Automates non déterministes avec transitions vides . . . . . . . . . . . . . . . . . . 7Élimination des transitions vides d’un automate . . . . . . . . . . . . 83.4 Minimisation d’un automate déterministe . . . . . . . . . . . . . . . . . . . . . . . 93.4.1 Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.4.2 Calcul de l’automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . 113.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Nettoyage des automates 184.1 Décision du vide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 de la finitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.3 Décision du plein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.4 Exercices . . . . . . . . . . . . . ...

Sujets

• informatique

Informations

• Publié par: Unyu
• Nombre de lectures: 56
• Langue: Français

Extrait

Université Paris-Sud Licence d’Informatique

Informatique Théorique : Théorie des Langages, Analyse Lexicale, Analyse Syntaxique

Jean-Pierre Jouannaud Professeur

Adresse de l’auteur :

LIX École Polytechnique F-91128 Palaiseau CEDEX

URL :.euq/rfliw.pox.telynichww//p:tth

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 26 27 27 28 28 28 29 30

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table des matières

6.5

Expressions rationnelles 6.1 Expressions rationnelles . . . . . . . 6.2 Théorème de Kleene . . . . . . . . . 6.3 Identités remarquables . . . . . . . . 6.4 Analyse lexicale avec l’outil LEX . . 6.4.1 Notion de token . . . . . . . . 6.4.2 Fichier de description LEX . . 6.4.3 Description des tokens . . . . 6.4.4 Règles de priorité . . . . . . . Exercices . . . . . . . . . . . . . . .

ii

J.-P. Jouannaud

4 4 5 6 7 8 9 9 11 14

3

2

3

Université Paris

Sud

Propriétés de clôture des langages reconnaissables 5.1 Clôture Booléenne . . . . . . . . . . . . . . . 5.2 Clôture par produits . . . . . . . . . . . . . . . 5.3 Clôture par morphisme . . . . . . . . . . . . . 5.4 Pompage des langages reconnaissables . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21 21 22 23 23

5

Nettoyage des automates 4.1 Décision du vide . 4.2 Décision de la nitu 4.3 Décision du plein . 4.4 Exercices . . . . .

. . . . . . . . . . . . . . . . . . . . . de . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

18 18 19 19 19

4

Automates de mots nis 3.1 Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Automates non déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Déterminisation d’un automate non-déterministe . . . . . . . . . . . 3.3 Automates non déterministes avec transitions vides . . . . . . . . . . . . . . . . . . Élimination des transitions vides d’un automate . . . . . . . . . . . . 3.4 Minimisation d’un automate déterministe . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Calcul de l’automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Introduction

1

Langages formels

2

des

matières

6

Table

Table

7

8

9

10

11

des

matières

Grammaires formelles 7.1 Grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Langage engendré par une grammaire . . . . . . . . . . . . . . . . . . . . 7.3 Classication de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Grammaires contextuelles . . . . . . . . . . . . . . . . . . . . . . 7.3.2 Grammaires hors-contexte . . . . . . . . . . . . . . . . . . . . . . 7.3.3 Grammaires régulières . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Forme normale de Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Dérivations gauches et droites . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Arbres syntaxiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Automates à pile 8.1 Langages reconnaissables par automates à pile 8.2 Automates à pile et grammaires hors-contexte 8.3 Exercices . . . . . . . . . . . . . . . . . . .

. . .

. . .

. . . . . .

. . . . . .

. . .

. . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . .

. . .

Propriétés de clôture des langages algébriques 9.1 Vide et nitude des langages algébriques . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Pompage des langage algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.1 Propriété de pompage des algébriques . . . . . . . . . . . . . . . . . . . . . 9.2.2 Un peu de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Union, produit et étoile de Kleene. . . . . . . . . . . . . . . . . . . . Intersection et complémentation. . . . . . . . . . . . . . . . . . . . . 9.3.1 Substitution et homomorphisme . . . . . . . . . . . . . . . . . . . . . . . . 9.3.2 Homomorphisme inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32 32 33 34 34 34 34 35 36 38 40

41 41 43 44

45 45 45 45 46 47 47 48 48 49 49 49

Analyse syntaxique 50 10.1 Analyse syntaxique descendante . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 10.1.1 Analyse descendante non-déterministe . . . . . . . . . . . . . . . . . . . . . 51 10.1.2 Analyse descendante déterministe . . . . . . . . . . . . . . . . . . . . . . . 51 10.1.3 Automate d’analyse prédictive descendante . . . . . . . . . . . . . . . . . . 53 10.1.4 Condition de déterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 10.1.5 Factorisation des membres droits . . . . . . . . . . . . . . . . . . . . . . . . 54 10.2 Analyse syntaxique ascendante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 10.2.1 Automate non-déterministe d’analyse ascendante . . . . . . . . . . . . . . . 56 10.2.2 Déterminisation de l’analyse ascendante . . . . . . . . . . . . . . . . . . . . 57 10.2.3 Principes d’une analyse ascendante prédictive . . . . . . . . . . . . . . . . . 57 Conditions de déterminisme . . . . . . . . . . . . . . . . . . . . . . 59 10.2.4 Automate SLR d’analyse ascendante . . . . . . . . . . . . . . . . . . . . . . 60 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 10.2.5 Génération d’analyseurs syntaxiques avec YACC . . . . . . . . . . . . . . . 64 10.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Syntaxe abstraite des langages 68 11.1 Grammaires abstraites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 11.2 Arbres de syntaxe abstraite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 11.3 Représentation des valeurs des tokens dans l’arbre . . . . . . . . . . . . . . . . . . . 70 11.4 Calcul des arbres de syntaxe abstraite . . . . . . . . . . . . . . . . . . . . . . . . . 70

J.-P. Jouannaud

Université

Paris

iii

Sud

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

13

espace

73

Complexité en temps et en

74

74

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . .

. . . . .

. . .

.

. .

. .

. . .

.

. . . .

. . .

81

13.4

Exercices

.

.

. .

.

.

. . .

. .

. . .

. . . . . . . . . . . . . . . . . . . . . . . .

. .

.

73

.

.

.

.

. . .

. . . . .

. . . .

. . .

.

Réductions et complétude

13.3.1

76

77

.

.

. .

.

. .

. . .

. .

. .

. .

. . .

.

. . . .

. .

.

. .

PSPACE-complétude

13.3.3

79

13.3.2

NP-complétude . . . . . .

. . . . .

. . .

.

.

.

. . . . .

Classes de complexité . . . . .

.

.

.

.

75

.

. . . . .

. . . . .

13.1

13.2

Comparaisons entre mesures de

complexité

. . . . . . . . . . . . . . . . . . . . . . . . . . .

76

.

.

.

. . . . .

. . . .

.

Université

13.3

Sud

Paris

.

. . . .

Langages complets

.

J.-P. Jouannaud

Codages

iv

. . .

. . . .

. . . 72

11.5

. . . 72

. .

.

.

.

.

.

.

.

.

.

.

syntaxe abstraite

des arbres de

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

11.6

Table des

.

Exercices . . .

Machines de

12

matières

Turing

.

.

12.1 Exercices

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

TABLE DES MATIÈRES

Table

J.-P. Jouannaud

des

matières

1

Université Paris Sud

2

J.-P. Jouannaud

Chapitre

1

Introduction

Introduction

Ce cours se propose d’étudier en détail la notion de langage formel, initialement introduite par Noam Chomsky et son équipe dans le but de formaliser les langues naturelles. Si l’application aux langues naturelles a révolutionné leur étude, le but ultime consistant à automatiser le traitement de ces langues a largement échoué, au jour d’aujourd’hui en tout cas. Par contre, les travaux qui en ont résulté ont trouvé leur application naturelle dans le traitement automatisé des langages infor- matiques : la compilation, généralement découpée en analyse lexicale, analyse syntaxique, analyse sémantique et génération de code est une suite de traitements langagiers de complexité croissante : l’analyse lexicale met en oeuvre les traitements les plus simples, qui relèvent des langages dits ré- guliers ; l’analyse syntaxique a pour but d’analyser la structure syntaxique des phrases, qui relève des langages dits “hors-contxte” ; enn, les traitements dits sémantiques, comme le typage, mettent en jeu des structures langagières complexes, dites contextuelles. On retrouve également la notion de langage en théorie de la calculabilité, et en théorie de la complexité. On la retrouve enn au coeur de l’un des grands succès de la discipline, la vérication de programmes, qui a réussi ces dernières années une percée industrielle remarquée. Le but de ce cours est de faire le tour de ces différentes notions dans le contexte informatique : les automates nis et les expressions rationnelles, qui se sont révélés un outil de modélisation excep- tionnel et ont, à ce titre, envahi tout le paysage scientique, informatique, mathématiques, physique, biologie, etc ; leur application à l’analyse lexicale ; les grammaires hors-contexte et les automates à pile, autres outils de modélisation très commode dont les utilisations ont moins débordé la sphère informatique ; leur application à l’analyse syntaxique. Comme tout cours, celui-ci fait de nombreux emprunts, en particulier à [2], ouvrage remarquable dont une lecture approfondie est recommandée.

Université Paris Sud

Chapitre

2

Langages

formels

On appelleravocabulaireun ensemble niV t dont les éléments sont appelléslettres, etmot toute suite nie de lettres, notéeu=u 1 . . . u n pour un motudelongueurn. On notera parV T ∗ l’ensemble des mots, et parεle mot de longueur nulle, appellémot vide. L’ensemble des mots est muni d’une opération interne, leproduit de concaténation, telle que si u=u 1 . . . u n etv=v 1 . . . v p , alors le produituvest le motwtel quew i =u i pouri∈[1..n]et w n+j =v j pourj∈[1..p]. Il est aisé de vérier que la concaténation des mots est associative et possèdeεélément neure. On notera parfois le produit sous la formepour u∙van d’éviter certaines ambiguités. Tout produit, par répétition, donne naissance à une notion de puissance. La puissance nème d’un mot est dénie par récurrence surncomme suit :u 0 =εetu n+1 =u∙u n . Muni du produit de concaténation et de son élément neutre,V t ∗ est appellé lemonoïde libresur V t . Cette dénomination fait référence au fait que tout motuest soit le mot videε, soit commence par une certaine lettreaauquel cas il s’écrit de manière unique sous la formeavpour un certain motv de taille diminuée de une unité. Il sera donc possible de prouver une propriétéPd’un ensemble de mots en montrantP(ε), puis en montrantP(av)en supposantP(v). Il s’agit là d’un raisonnement par récurrence classique lié à cette décomposition des mots. Mais on peut aussi décomposer un mot uen exhibant sa dernière lettre : tout motuest soit le mot videεsoit s’écrit de manière unique sous la formevaoùa∈V t etv∈V t ∗ , ce qui fournit un autre principe de récurrence. Nous utiliserons l’un ou l’autre suivant les cas. Toute partie deV t ∗ est appelléelangage. On disnguera deux langages très particuliers, lelangage videnoté∅qui ne possède aucun mot, et lelangage unité{ε}réduit au mot vide. On dénit à nouveau des opérations sur les langages, opérations ensemblistes classiques ou opé- rations qui font référence aux opérations correspondantes sur les mots :

L 1 ∪L 2 désigne l’union des langagesL 1 etL 2 L 1 ∩L 2 désigne l’intersection des langagesL 1 etL 2 Ldésigne le complémentaire dansV t ∗ du langageL L 1 ×L 2 ={uv|u∈L 1 etv∈L 2 }désigne le produit des langagesL 1 etL 2 L n tel queL 0 ={ε}etL n+1 =L×L n désigne la puissance nème du langageL L ∗ = S i∈N L i désigne l’itéré du langageL L + = S i>0 L i désigne l’itéré strict du langageL Le lecteur est invité à montrer les propriétés suivantes : 1. Pour tout motuet tous entiersn, m,u n+m =u m+n =u n ∙u m =u m ∙u n . 2. Pour tout langageLet tous entiersn, m,L n+m =L m+n =L n ×L m =L m ×L n . 3. Siε∈L, alorsL ∗ =L + .

J.-P. Jouannaud

3

Université Paris Sud

4

J.-P. Jouannaud

Chapitre

3

Automates

de

mots

nis

Automates de mots nis

Les automates sont un outil de modélisation fondamental, qui servent à représenter des disposi- tifs automatiques, par exemples des systèmes réactifs, tout autant que des objets mathématiques ou physiques. Dans ce capitre, nous nous intéressons aux automates de mots nis, le cas important des mots innis étant abordé dans un chapitre ultérieur.

3.1

Automates déterministes

Dénition 3.1Unautomate ni déterministeAest un triplet(V t , Q, T)où 1.V t est levocabulairede l’automate ; 2.Qest l’ensemble ni desétatsde l’automate ; 3.T:Q×V t →Q, est une application partielle appelléefonction de transitionde l’automate.

a On noteraq−→q 0 pourT(q, a) =q 0 . LorsqueTtotale, autrement dit s’il y a dans chaqueest état exactement une transition pour toute lettre de l’alphabet, l’automate est ditcomplet. On omettra souvent le qualicatif ni.

Dénition 3.2Étant donné un automate déterministeA= (V t , Q, T), on appellecalcultoute suite (éventuellement vide) de transitionsq 0 − α → 1 q 1 ∙ ∙ ∙q n−1 − α n →q n , aussi notéeq 0 − w → A q n , ou encore sim- plementq 0 − w →q n en l’absence d’ambiguités, issue d’un étatq 0 et atteignant un étatq n en ayant lu le motw=α 1 ∙ ∙ ∙α n .

Notons que le calcul produit par la lecture d’un motwpar un automate ni déterministe est au- tomatique et se trouve donc exempte d’ambiguïté : la lecture des lettres composant le mot provoque des transitions bien dénies jusqu’à être bloqué en cas de transitions manquantes, ou bien jusqu’à atteindre un certain état après la lecture complète du mot. On en déduit la propriété fondamentale des automates déterministes complets :

Lemme 3.3SoitA= (V t , Q, T)déterministe complet. Alors, pour tout motun automate ni u∈ V t ∗ et tout étatq∈Q, il existe un unique étatq 0 ∈Qtel queq− u → A q 0 .

En pratique, il peut être utile de rendre un automate complet en ajoutant un nouvel état appelé poubelle, étiqueté par⊥, vers lequel vont toutes les transitions manquantes. Les calculs bloquants aboutissent alors dans la poubelle où ils restent capturés.

Dénition 3.4Un automate déterministe vient avec la donnée •d’unétat initiali∈Q; •d’un ensemble d’états acceptantsF⊆Q;

Université Paris Sud

3.2 Automates non déterministes

0, 01 1

q 0

q 2

q 1

F IG Automate déterministe reconnaissant les entiers naturels en numération binaire.. 3.1 –

0, 10 1

q 0

q 2

q 1

⊥

F IG . 3.2 – Automate déterministe complet reconnaissant les entiers naturels en numération binaire.

On notera parA F i le quintuplet(V t , Q, i, F, T), ou plus simplementAsiietFsont donnés sans ambiguité dans le contexte. Un motwestreconnupar l’automateA i F s’il existe un calcul ditréussiissu de l’état initiali et terminant en état acceptant après avoir lu le motw. On note parLang(A)le langage des mots reconnus par l’automateA. Un langage reconnu par un automate est ditreconnaissable. On note parRecl’ensemble des langages reconnaissables.

Il est clair que l’ajout d’une poubelle ne change pas les mots reconnus. On a l’habitude de dessiner les automates, en gurant les états par des cercles, en indiquant l’état initial par une èche entrante, les états acceptants par un double cercle ou une èche sortante, et la transition de l’étatqà l’étatq 0 en lisant la lettreαpar une èche allant deqversq 0 et étiquetée par α3.1 représente un automate (incomplet) reconnaissant le langage des entiers naturels en. La gure représentation binaire. L’automate obtenu reconnaît exactement le même langage si l’on convient que le nouvel état poubelle n’est pas acceptant. Ainsi, la gure 3.2 présente un automate complet reconnaissant le langage des entiers naturels en représentation binaire. Si l’automateAest complet, on pourra donc étendre l’applicationTaux mots, en posant T(q, u) =q 0 ∈Qtel queq−→ u q 0 . On peut donc dans ce cas reformuler la condition d’acceptation des mots commeu∈ Lang(A)ssiT(i, u)∈F.

3.2

Automates non déterministes

Dénition 3.5Unautomate non-déterministeAest un triplet(V t , Q, T)où 1.V t est levocabulairede l’automate ;

J.-P. Jouannaud

5

Université Paris Sud

6

J.-P. Jouannaud

Automates de mots nis

F IG des calculs d’un automate non déterministe.. 3.3 – Arbre

2.Qest l’ensemble desétatsde l’automate ; 3.T:Q×V t → P(Q), est lafonction de transitionde l’automate. On notera comme précédemmentq−→ α q 0 pourq 0 ∈T(q, α)avecα∈V t , et parT(q, u)l’ensemble (peut-être vide) des états atteignables depuisqen lisant le motu.

Notons qu’un automate déterministe est un cas particulier d’automate non-déterministe qui as- socie à tout élément deQ×V t une partie deQpossédant zéro ou un élément (exactement un si c’est un automate complet). On pourra dire d’un automate déterministe qu’il est incomplet s’il peut se bloquer, c’est-à-dire s’il existe un étatqet une lettreatels queT(q, a) =∅. Si l’automate est complet, nous aurons une forme affaiblie du Lemme 3.3 :

Lemme 3.6SoitA= (V t , Q, i, F, T)un automate ni non-déterministe complet. Alors, pour tout motu∈V t ∗ et tout étatq∈Q, il existe un (non nécessairement unique) étatq 0 ∈Qtel queq−→ u A q 0 .

La notion de calcul est la même pour cette nouvelle variété d’automates que pour les automates déterministes, ainsi que la notion de reconnaissance, nous ne les répètons pas. Le non-déterministe a toutefois une conséquence essentielle : il peut y avoir plusieurs calculs issus de l’état initiali qui lisent un motwdonné, dont certains peuvent se bloquer et d’autres pas, et dans ce dernier cas certains peuvent terminer en état acceptant et d’autres pas. L’acceptation a lieu s’il existe au moins un calcul réussi. Si tous les calculs échouent, il n’y aura pas d’autre moyen de le savoir que de les explorer tous avant de savoir que le motwn’est pas reconnu. La bonne notion n’est donc pas celle de calcul, mais d’arbre de calcul associé à un mot lu par l’automate :

Dénition 3.7Étant donné un automate non déterministeA, l’arbre de calcul de racineq∈Q engendré par la lecture du motuest un arbre doublement étiquetté déni par récurrence suru: Siu=ε, alors l’arbre est réduit à sa racineq; Siu=av, la racineqpossède des transitions sortantes étiquettées para∈V t vers différents arbres de calcul engendrés par la lecture devet dont les racines sont étiquettées par les états de T(q, a).

Un arbre de calcul est représenté à la gure 3.3. On a la propriété évidente :

Lemme 3.8Un motu∈V t ∗ est reconnu par un automate non déterministeAssi l’une des feuilles de son arbre de calcul est étiquettée par un état acceptant.

Déterminisation d’un automate non-déterministeNous allons maintenant déterminiser un au- tomate non-déterministe (sans transitions vides) en ajoutant de nouveaux états : siQest l’ensemble des états d’un automate non-déterministe, l’ensemble des états de l’automate déterministe associé seraP(Q), l’ensemble des parties deQ.

Dénition 3.9SoitA= (V t , Q, T)un automate non-déterministe. On dénitDet(A)comme l’au- tomate(V t ,P(Q), T det )oùT det (K, a) = S q∈K T(q, a).

Théorème 3.10SoitAun automate non-déterministe. AlorsDet(A) { { K i P∈ } (Q)|K∩F6=∅} est déter- ministe et reconnaît le même langage queA i F .

Université Paris Sud