[PDF] [PDF] Langages formels Calculabilité et Complexité - ENS Lyon

View - Download [PDF] Langages formels Calculabilité et Complexité - ENS Lyon

Previous PDF

Next PDF

Langages formels,

Calculabilité et Complexité

Olivier Carton

Formation prédoctorale

École Normale Supérieure

Version du 12 avril 2007

Rédaction

Une toute première version de ce support de cours a été rédigée pendant l"année 2004/2005 par les élèves Gaëtan Bisson, François Garillot, Thierry Mar- tinez et Sam Zoghaib. Ensuite, il a été complètement repris et très largement étoffé par mes soins. Même si la version actuelle est relativement éloignée de la première version, elle lui doit l"impulsion initiale sans laquelle elle n"existerait peut-être pas. Certains passages ont aussi bénéficié de quelques travaux de ré- daction des élèves. Malgré tous ces efforts, ce support de cours contient encore de trop nombreuses erreurs et omissions. Une certaine indulgence est demandée au lecteur. Les corrections et suggestions sont bien sûr lesbienvenues.

Objectifs

Ce support de cours reflète les deux objectifs de ce cours. Le premier est d"ac- quérir les principales notions élémentaires en langages formels, calculabilité et complexité. Le second est de ne pas rester uniquement au niveau des définitions et trivialités et de montrer quelques jolis résultats de cesdifférents domaines. Ce choix fait que des résultats de difficultés très différentes secôtoient. Le premier chapitre sur les langages rationnels contient par exemple le lemme de l"étoile mais aussi la caractérisation de Schützenberger des langages sans étoile. Plan La structure de ce document reprend la division du cours en deux grandes parties : les langages formels d"une part, calculabilité etcomplexité d"autre part. Chacune de ces deux parties est scindée en deux chapitres. Les deux premiers chapitres sont consacrés aux langages rationnels et aux langages algébriques et les deux suivants à la calculabilité et à la complexité.

Téléchargement

Ce support de cours est disponible à l"URL

Table des matièresI Langages formels5

1 Langages rationnels7

1.1 Premières définitions . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Opérations rationnelles . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Combinatoire des mots . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Périodicités . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.2 Mots infinis . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.3 Motifs inévitables . . . . . . . . . . . . . . . . . . . . . . . 14

1.4 Un peu d"ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4.1 Quasi-ordres sur les mots . . . . . . . . . . . . . . . . . . 20

1.4.2 Ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . 22

1.4.3 Quasi-ordres sur les arbres . . . . . . . . . . . . . . . . . . 22

1.5 Langages rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.5.1 Expressions rationnelles . . . . . . . . . . . . . . . . . . . 25

1.5.2 Automates . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.6 Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . 31

1.7 Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.7.1 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.7.2 Congruence de Nerode . . . . . . . . . . . . . . . . . . . . 36

1.7.3 Calcul de l"automate minimal . . . . . . . . . . . . . . . . 37

1.8 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . 40

1.8.1 Opérations booléennes . . . . . . . . . . . . . . . . . . . . 40

1.8.2 Morphisme et morphisme inverse . . . . . . . . . . . . . . 40

1.8.3 Mélange . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

1.9 Lemme de l"étoile et ses variantes . . . . . . . . . . . . . . . . . . 41

1.10 Hauteur d"étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

1.11 Reconnaissance par morphisme . . . . . . . . . . . . . . . . . . . 45

1.12 Langages sans étoile . . . . . . . . . . . . . . . . . . . . . . . . . 52

1.13 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1.13.1 Conjecture de Černý . . . . . . . . . . . . . . . . . . . . . 57

1.13.2 Rationnels d"un monoïde quelconque . . . . . . . . . . . . 58

2 Langages algébriques61

2.1 Grammaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.1.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . 61

2.1.2 Grammaires réduites . . . . . . . . . . . . . . . . . . . . . 64

2.1.3 Grammaires propres . . . . . . . . . . . . . . . . . . . . . 65

2.1.4 Forme normale quadratique . . . . . . . . . . . . . . . . . 66

3

4TABLE DES MATIÈRES

2.2 Systèmes d"équations . . . . . . . . . . . . . . . . . . . . . . . . . 67

2.2.1 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . 67

2.2.2 Système d"équations associé à une grammaire . . . . . . . 68

2.2.3 Existence d"une solution pourS(G). . . . . . . . . . . . 68

2.2.4 Unicité des solutions propres . . . . . . . . . . . . . . . . 69

2.2.5 Théorème de Parikh . . . . . . . . . . . . . . . . . . . . . 70

2.2.6 Systèmes d"équations en commutatifs . . . . . . . . . . . 71

2.2.7 Solutions rationnelles des systèmes commutatifs . . .. . . 71

2.3 Arbres de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . 74

2.3.1 Ambiguïté . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

2.3.2 Lemme d"itération . . . . . . . . . . . . . . . . . . . . . . 75

2.3.3 Applications du lemme d"itération . . . . . . . . . . . . . 76

2.3.4 Ambiguïté inhérente . . . . . . . . . . . . . . . . . . . . . 78

2.4 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . 78

2.4.1 Opérations rationnelles . . . . . . . . . . . . . . . . . . . 78

2.4.2 Substitution algébrique . . . . . . . . . . . . . . . . . . . 79

2.4.3 Morphisme alphabétique inverse . . . . . . . . . . . . . . 79

2.4.4 Intersection avec un rationnel . . . . . . . . . . . . . . . . 80

2.4.5 Théorème de Chomsky-Schützenberger . . . . . . . . . . . 81

2.5 Forme normale de Greibach . . . . . . . . . . . . . . . . . . . . . 82

2.6 Automates à pile . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

2.6.1 Définitions et exemple . . . . . . . . . . . . . . . . . . . . 85

2.6.2 Différents modes d"acceptation . . . . . . . . . . . . . . . 86

2.6.3 Équivalence avec les grammaires . . . . . . . . . . . . . . 87

2.6.4 Automates à pile déterministes . . . . . . . . . . . . . . . 88

2.7 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

2.7.1 Réécriture . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2.7.2 Contenus de pile . . . . . . . . . . . . . . . . . . . . . . . 92

2.7.3 Groupe libre . . . . . . . . . . . . . . . . . . . . . . . . . 93

II Calculabilité et complexité 95

3 Calculabilité97

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

3.1.1 Notion de problème . . . . . . . . . . . . . . . . . . . . . 97

3.1.2 Notion de codage . . . . . . . . . . . . . . . . . . . . . . . 98

3.1.3 Machines de Turing . . . . . . . . . . . . . . . . . . . . . 98

3.1.4 Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . 103

3.1.5 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

3.2 Langages récursivement énumérables . . . . . . . . . . . . . . . .110

3.3 Langages décidables . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.4 Problème de correspondance de Post . . . . . . . . . . . . . . . . 116

3.4.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . 116

3.4.2 Indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . 117

3.4.3 Application aux grammaires . . . . . . . . . . . . . . . . . 119

3.5 Théorème de récursion . . . . . . . . . . . . . . . . . . . . . . . . 121

3.6 Machines linéairement bornées . . . . . . . . . . . . . . . . . . . 123

3.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

3.6.2 Grammaires contextuelles . . . . . . . . . . . . . . . . . . 123

TABLE DES MATIÈRES5

3.6.3 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 125

3.6.4 Complémentation . . . . . . . . . . . . . . . . . . . . . . . 126

3.7 Décidabilité de théories logiques . . . . . . . . . . . . . . . . . .. 126

3.7.1 Modèles et formules logiques . . . . . . . . . . . . . . . . 126

3.7.2 Arithmétique de Presburger . . . . . . . . . . . . . . . . . 127

3.7.3 Addition et multiplication . . . . . . . . . . . . . . . . . . 129

3.7.4 Logique monadique du second ordre . . . . . . . . . . . . 129

3.8 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . 130

3.8.1 Fonctions primitives récursives . . . . . . . . . . . . . . . 130

3.8.2 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . 134

3.8.3 Équivalence avec les machines de Turing . . . . . . . . . . 134

3.8.4 Thèse de Church . . . . . . . . . . . . . . . . . . . . . . . 135

3.9 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

3.9.1 Écritures des entiers dans une base . . . . . . . . . . . . . 135

3.9.2 Machines de Turing sans écriture sur l"entrée . . . . . . .138

4 Complexité141

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

4.1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

4.1.2 Définition des complexités . . . . . . . . . . . . . . . . . . 141

4.1.3 Graphes des configurations . . . . . . . . . . . . . . . . . 142

4.2 Complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . . 142

4.2.1 Théorème d"accélération . . . . . . . . . . . . . . . . . . . 142

4.2.2 Changements de modèles . . . . . . . . . . . . . . . . . . 143

4.2.3 Classes de complexité en temps . . . . . . . . . . . . . . . 144

4.2.4NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . 146

4.2.5NP-complétude deSatet3Sat. . . . . . . . . . . . . . 147

4.2.6 Exemples de problèmesNP-complets . . . . . . . . . . . . 151

4.3 Complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . . 158

4.3.1 Changement de modèle . . . . . . . . . . . . . . . . . . . 158

4.3.2 Classes de complexité en espace . . . . . . . . . . . . . . . 159

4.3.3 Complexités en temps et en espace . . . . . . . . . . . . . 159

4.3.4 Exemples de problèmes dansPSpace. . . . . . . . . . . 160

4.3.5PSpace-complétude . . . . . . . . . . . . . . . . . . . . . 161

4.3.6 Espace logarithmique . . . . . . . . . . . . . . . . . . . . 162

4.4 Théorèmes de hiérarchie . . . . . . . . . . . . . . . . . . . . . . . 163

4.5 Machines alternantes . . . . . . . . . . . . . . . . . . . . . . . . . 164

4.5.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . 164

4.5.2 Algorithme alternant pourQSat. . . . . . . . . . . . . . 164

4.5.3 Automates alternants . . . . . . . . . . . . . . . . . . . . 165

4.5.4 Classes de complexité . . . . . . . . . . . . . . . . . . . . 165

4.6 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

4.6.1 Machines à une bande en tempso(nlogn). . . . . . . . . 167

Bibliographie174

Index175

6TABLE DES MATIÈRES

Première partie

Langages formels

7

Chapitre 1Langages rationnels

Les langages rationnels sont le premier niveau de la hiérarchie de Chomsky. Cette famille est constituée des langages acceptés par les automates finis qui sont le modèle le plus simple de machines. Cette famille de langages jouit de propriétés remarquables. Elle est en particulier closes par de très nombreuses opérations. La théorie des automates est une théorie relativement richeet certains de ses résultats sont de véritables perles. Elle entretient aussides liens avec beaucoup d"autres domaines comme la dynamique symbolique, la combinatoire, l"algèbre, la topologie, la théorie des jeux, l"arithmétique, la logique et l"algorithmique. Certains de ces liens avec l"algèbre et la logique sont abordés dans ce support de cours (cf. sections 1.11 et 3.7.2 par exemple). Les automates se sont aussi imposés comme un outil incontournable d"un point de vue pratique. Tout éditeur de texte un peu évolué comprend une fonc- tion de recherche à partir d"une expression rationnelle. Cette recherche com- mence toujours par la construction d"un automate équivalent à l"expression. Les automates sont aussi utilisés dans le domaine de la vérification. Ils s"agit dans ce domaine de vérifier qu"un objet tel un composant logiciel ou un protocole satisfait bien une spécification. Ce chapitre introduit les notions de mots et de langages. Après quelques éléments de combinatoire des mots, il développe les langages rationnels et les automates finis qui les acceptent. Une dernière partie est consacrée à la re- connaissance par morphismes des langages rationnels et à lacaractérisation des langages sans étoile. Pour l"essentiel du chapitre, une bonne référence est [Per90].

1.1 Premières définitions

On commence par quelques définitions élémentaires. La terminologie est em- pruntée à la linguistique et provient du fait qu"un des objectifs initiaux de ce domaine était la modélisation des langues naturelles. Définition 1.1.- Unalphabetest un ensemble fini (souvent notéAouΣ) dont les éléments sont appeléslettresousymboles. - Unmotwsur l"alphabetAest une suite finiew1w2···wnde lettres deA. L"entiernest appelé lalongueurdewqui est notée|w|. - Lemot videnotéεou parfois1correspond à l"unique mot de longueur0. 9

10CHAPITRE 1. LANGAGES RATIONNELS

- Unlangagesur l"alphabetAest un ensemble de mots surA. - L"ensemble de tous les motssur l"alphabetAest notéA?et il est appelé lemonoïde libresurA. Laconcaténationdes deux motsu=u1···umetv=v1···vnest le mot notéu·vouuvet égal àu1···umv1···vnobtenu par simple juxtaposition. C"est une opération associative dont le mot videεest l"élément neutre. C"est pour cette raison que le mot vide est parfois noté1. Exemple1.2.Siu=abaaetv=bab, on auv=abaababetvu=bababaa. La concaténation n"est pas commutative. Comme la concaténation est une loi de composition interne associative avec un élément neutre, elle munit l"ensembleA?de tous les mots d"une structure de monoïde. Pour cette raison, la concaténation est aussi appeléeproduit. Ce monoïde est dit libre parce que les seules équations qu"il satisfait sont celles qui sont conséquences de la définition de monoïde. Ce fait est énoncé de manière rigoureuse à la proposition 1.106 (p. 46). La notion destructure librepeut être définie de manière très générale dans le cadre de l"algèbre universelle [Alm94]. Un motuest unpréfixe(resp.suffixe) d"un motws"il existe un motvtel quew=uv(resp.w=vu). Un motuest unfacteurd"un motws"il existe deux motsvetv?tels quew=vuv?. Exercice1.3.Soitw=w1···wnun mot de longueurn. Par un léger abus, on utilise la notationwimême si l"entierin"est pas dans l"intervalle[1;n]. On note appelleoccurrence circulaired"un motu=u1···upun entierkdans l"intervalle Montrer que pour tout alphabetAet tout entierk, il existe un motwktel que tous les mots de longueurksurAont exactement une occurrence circulaire danswk. Un tel mot est appelé un mot dede Bruijnd"ordrek. Les mots1100 et11101000sont des mots de de Bruijn d"ordre2et3sur l"alphabet{0,1}. On pourra considérer l"automate dont l"ensemble des états estAk-1et dont l"ensemble des transitions est{aua-→ub|a,b?Aetu?Ak-2}. Montrer qu"il y a bijection entre les chemins eulériens de cet automate et les mots de de Bruijn d"ordrek. SoitAetBdeux alphabets. Un morphisme de monoïdesμdeA?dansB?est une application deA?dansB?qui est compatible avec la structure de monoïde. Ceci signifie que l"image du mot vide est le mot vide (μ(ε) =ε) et queμ(uv) = μ(u)μ(v)pour tout motuetvdeA?. L"image d"un motw=w1···wnest donc

égal àμ(w) =μ(w1)···μ(wn). Le morphisme est complètement déterminé par

les images des lettres. Un morphismeμest diteffaçants"il existe une lettrea tel queμ(a) =ε. Exemple1.4.SoitAl"alphabet{a,b}et soitμ:A?→A?le morphisme de monoïde déterminé parμ(a) =abetμ(b) =a. Ce morphisme est non-effaçant. L"image du motabaparμest le motabaab=ab·a·ab.

1.2 Opérations rationnelles

On définit maintenant les opérations rationnelles qui permettent de construire de nouveaux langages.

1.3. COMBINATOIRE DES MOTS11

Définition 1.5(Union, Produit).- L"unionest l"opération qui à deux lan- gagesLetL?associe le langageL+L?=L?L?. - Leproduitest l"opération qui à deux langagesLetL?associe le langage

L·L?=LL?={uv|u?Letv?L?}.

Exemple1.6.Soient les deux langagesL={u?A?| |u|pair}etL?={u? A ?| |u|impair}. On a alors les égalités suivantes. -L+L?=A?-LL?=L?=L?L -L?L?=L\ {ε}-LL=L(Lest un sous-monoïde deA?) Définition 1.7(Étoile).SoitL?A?, on définit : L

0={ε}, Li+1=LLi, L?=?

i≥0L i Cette définition justifie donca posteriorila notationA?puisque l"ensemble de tous les mots est bien l"étoile de l"alphabet. Il faut remarquer qu"en général L iest différent de{ui|u?Leti≥0}. Unsous-monoïdedeA?est un langage deA?qui contient le mot vide et qui est clos pour la concaténation. On vérifie que pour tout langageL, le langageL? est le plus petit sous-monoïde deA?qui contientL. Inversement tout sous- monoïdeKdeA?est de la formeL?puisqueK=K?. Exemple1.8.- SiL={a,ba}, alorsL?est constitué de tous les mots dans lesquels chaquebest suivi d"una. - SiL={anb|n≥0}, alorsL?est constitué du mot videεet de tous les mots qui se terminent par unb. - SiL=∅, alorsL?est le langage{ε}uniquement constitué du mot vide.

Pour un langageL, on noteL+le langageLL?=L?L=?

i≥1Li. SiL contient le mot vide, on aL+=L?et sinon on aL+=L?\{ε}. Le langageA+ est par exemple l"ensemble des mots non vides.

1.3 Combinatoire des mots

La combinatoire des mots est l"étude des propriétés structurelles des mots. Dans cette partie, on s"intéresse d"abord à des questions depériodicité puis à des questions de motifs inévitables.

1.3.1 Périodicités

w u v u v u

Fig.1.1 - Période d"un motw

Soitw=w1···wnun mot sur un alphabetA. Unepériodedewest un

12CHAPITRE 1. LANGAGES RATIONNELS

convention, la longueur dewest une période dew. On noteP(w)l"ensemble des périodes dew. Il faut remarquer qu"une période ne divise pas nécessairement pas la longueur du mot. Sipest une période dew, le motwse factorisew= (uv)ku où l"entierkvérifiek≥1, l"entierpest égal à|uv|et le motvest non vide (cf. figure 1.1). w u u u

Fig.1.2 - Mot non primitifw=u3

Un motwestprimitifs"il ne s"écrit pasw=ukaveck≥2. Autrement dit, un mot est primitif si sa longueur est l"unique période qui divise sa longueur (cf. figure 1.2). Tout motws"écrit de manière uniquew=ukoù l"entierkvérifie k≥1et le motuest primitif. L"entierkest égal à1quandwest primitif. Exemple1.9.Le motw= 010101aP(w) ={2,4,6}pour ensemble de périodes. Il n"est pas primitif car il s"écritw= (01)3. Le motw?= 01001010010aP(w?) = {5,8,10,11}pour ensemble de périodes. Il est primitif car aucune de ses périodes autre que sa longueur ne divise sa longueur. Le plus grand commun diviseur de deux entierspetqest notép?q. Le théorème de Fine et Wilf est le résultat de base de la combinatoire des mots. Les preuves de beaucoup d"autres résultats font appel à ce théorème. Théorème 1.10(Fine-Wilf 1965).Sipetqsont deux périodes d"un motwde longueur supérieure ou égale àp+q-p?q, alorsp?qest aussi une période dew. Avant de donner la preuve du théorème, on montre que la borne du théorème est optimale. Soit(fn)n≥0la suite de mots définie par récurrence parf0= 1, f

1= 0etfn+2=fn+1fn. Les premiers mots de cette suite sontf2= 01,

f

3= 010,f4= 01001etf5= 01001010. Les mots de cette suite sont appelés

mots de Fibonacci. En effet, la longueur de chaque motfnest le nombre de FibonacciFnoù la suite(Fn)n≥0est définie parF0=F1= 1et la relation de récurrenceFn+2=Fn+1+Fnpourn≥0. Les mots de Fibonacci possèdent beaucoup de propriétés remarquables. Ils constituent en particulier des cas extrémaux pour le théorème de Fine et Wilf. Soit, pourn≥2, le motgnobtenu en supprimant defnses deux dernières lettres qui sont01sinest pair et10sinon. Les premiers mots de cette suite sont doncg2=ε,g3= 0,g4= 010etg5= 010010. On va montrer que le motgnadmetFn-1etFn-2pour périodes mais pasFn-1?Fn-2= 1alors que sa longueur|gn|est égale àFn-2 =Fn-1+Fn-2-(Fn-1?Fn-2)-1. On vérifie facilement que deux nombres des Fibonacci consécutifsFnetFn+1sont premiers entre eux :Fn?Fn+1= 1. On montre par récurrence quegn+2=fn+1gn=fngn+1pour toutn≥2. Les premières valeursg2=ε,g3= 0etg4= 010permettent de vérifier ces égalités pourn= 2. La formulefn+2=fn+1fnet la définition degndonnent immédiatement l"égalitégn+2=fn+1gn. On a ensuitegn+2=fnfn-1gn= f ngn+1par hypothèse de récurrence. Les relationsgn+2=fnfn-1gn=fnfngn-1 montrent quegn+2admetFn=|fn|etFn+1=|fnfn-1|pour périodes. Par

1.3. COMBINATOIRE DES MOTS13

quotesdbs_dbs45.pdfusesText_45

[PDF] fonction calculable

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal