[PDF] Modèles de calculs - Lemme de la pompe

View - Download Modèles de calculs - Lemme de la pompe

Previous PDF

Next PDF

Modèles de calculs

Lemme de la pompe

Florent Madelaine

Fondements de l"informatique

Lemme de la pompeAu delà

Plan

1Lemme de la pompe

2Au delà

Lemme de la pompeAu delà

Introduction

Nous avons vu brièvement le modèle des automates finis.

On admettra qu"ils correspondent aux

langages r éguliers . Il existe des méthodes pour passer de l"un à l"autre, en particulier il y a des ateliers disponibles dans JFLAP.

Nous voyons maintenant une méthode dite du

lemme de la pompe qui per metparfois de montr erqu"un langage n"est pas régulier.

Lemme de la pompeAu delà

Objectif

Question

Étant donné un langageL, existe-t-il un automate fini qui reconnaît ce langage?

Lemme de la pompeAu delà

Objectif

Question

Étant donné un langageL, existe-t-il un automate fini qui reconnaît ce langage? Si le langageLest donné par unee xpressionr égulière, on sait que la réponse est OUI , et on sait même construire un automate fini qui r econnaîtce langage.

Mais si la réponse est

NON , autrement dit s"il n"existe aucun automate fini qui r econnaîtle langage L, comment le pr ouver

Lemme de la pompeAu delà

Objectif

Question

Étant donné un langageL, existe-t-il un automate fini qui reconnaît ce langage?Outil pour le NON

On va voir une propriété (appelée le

lemme de la pompe ) qui est vraie pour tous les langages r éguliers

Par conséquent, si un langage

ne vérifie pas cette propriété, il est impossible qu"il soit un langage r égulier

Lemme de la pompeAu delà

Ce que pomper veut dire1

234
a aa b b bb a b bbaccepté b b bbaccepté b b b b bb accepté

N"importe quel mot de la

accepté

Car il y a un cycle

1 ÝÑ2ÝÑ3bÝÑ1

On dit qu"on peut

pomper bdans le motbbb

Lemme de la pompeAu delà

Pomper ici ou pomper ailleurs1

234
a aa b b bb a b b baccepté b b b baccepté b b b b b bbaccepté

N"importe quel mot de la

accepté

Car il y a un cycle1bÝÑ1

On peut aussi

pomper bdans le motbbb

Lemme de la pompeAu delà

Peut-on toujours pomper?4

a b baa 5 67b
a b bbbbaccepté

Peut-on pomper quelque

chose quelque part? bb b b (cycle5bÝÑ7ÝÑ5) oubbbb (cycle 5

Lemme de la pompeAu delà

Peut-on toujours pomper?4

a b baa 5 67b
a b bbaccepté

Peut-on pomper quelque

chose quelque part? Non : aucune partie de bbne correspond à un cycle sur l"automate

Lemme de la pompeAu delà

Dans quels mots peut-on pomper?

On peut pomper chaque fois

qu"une partie d"un mot accepté correspond à un cycle sur l"automate

Lemme de la pompeAu delà

Dans quels mots peut-on pomper?

Dès que la

longueur d"un mot accepté est plus grande que le nombre d"états de l"automate, on doit forcément repasser par (au moins) un état en lisant ce mot

ùñil y a un cycle

Lemme de la pompeAu delà

Dans quels mots peut-on pomper?

Finalement, dès que la longueur

d"un mot accepté est plus grande que le nombre d"états de l"automate, on est sûr de pouvoir pomper une partie du mot

Lemme de la pompeAu delà

Lemme de la pompe

Théorème

SoitLun langage reconnu par un automateAavecnétats. Alors on peut pomper quelque chose dans tout mot deLde longueur¥n.

Autrement dit :

Tout motdeLde longueur¥nse décompose sous la

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

Utilisation du lemme de la pompe

L tkbk,k¥0u tϵ,b,bb,bbb,...u On va montrer queLn"est pas régulier par unraisonnement par l"absurde

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbnPLavec

|| 2n¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbn, donc1

n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, c.-à-d.Ln"est pas un langage régulier

Lemme de la pompeAu delà

D"autres langages non réguliers

Le langage des palindromes

Mot qui se lit pareil de droite à gauche et de gauche à droite

En français : RADAR, KAYAK, RESSASSER, ...

On noteRle motrenversé :bbdevientbb Tout motde la formeRest un palindrome

Le langage des parenthèses bien formées

ppqqpqppqqouppppqqqq mais paspqqpnippqppq Le langage composé des mots qui contiennent le même nombre deque deb etc.

Lemme de la pompeAu delà

Autre exemple

Lle langage des palindromes

On va montrer

par l"absur de que Ln"est pas régulier.

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbbnPLavec

|| 2n2¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbbnn"est pas un

palindrome, donc1 n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, doncLn"est pas un langage régulier

Lemme de la pompeAu delà

Autre exemple

Lle langage des palindromes

On va montrer

par l"absur de que Ln"est pas régulier.

Supposons

que Lsoit reconnu par un automateAet appelonsn le nombre d"états deA.

Le motnbbnPLavec

|| 2n2¥nùñpomper

Doncdavecd¡0

appartient àL

Mais1ndbbnn"est pas un

palindrome, donc1 n"appartient pas àL

Contradiction

DoncLn"est pas reconnu parAConclusion: Il n"e xisteaucun automate fini qui r econnaisse le langageL, doncLn"est pas un langage régulier

Lemme de la pompeAu delà

Autre exemple

Lle langage des palindromes

On va montrer

par l"absur dequotesdbs_dbs35.pdfusesText_40

[PDF] case based reasoning example

[PDF] samarium

[PDF] case based reasoning algorithm

[PDF] molecule de l'air

[PDF] molécule d'air formule

[PDF] l'air un mélange de molécules 4ème

[PDF] pourquoi les molécules principales de l'air sont-elles appelées diazote et dioxygène

[PDF] molécule d'air définition

[PDF] diazote et dioxygene dans l'air

[PDF] raisonnement philosophique

[PDF] exemple de raisonnement

[PDF] le raisonnement inductif

[PDF] raisonnement hypothético-déductif exemple

[PDF] raisonnement par contre exemple exercices

[PDF] exercice raisonnement direct