Pompage du lemme pour les langues régulières finies simples

20

Wikipedia a la définition suivante du lemme de pompage pour les langages réguliers ...

Soit L une langue régulière. Il existe alors un entier p ≥ 1 dépendant uniquement de L tel que chaque chaîne w dans L de longueur au moins p ( p est appelé la "longueur de pompage") puisse s'écrire w = xyz (c'est-à-dire que w peut être divisé en trois sous-chaînes), remplissant les conditions suivantes:

  1. | y | ≥ 1
  2. | xy | ≤ p
  3. pour tout i ≥ 0, xyizL

Je ne vois pas comment cela est satisfait pour un langage régulier fini simple. Si j'ai un alphabet de { a,b } et une expression régulière ab alors L compose d'un seul mot qui est a suivi de b . Je veux maintenant voir si ma langue régulière satisfait le lemme de pompage ...

Comme rien ne se répète dans mon expression régulière, la valeur de y doit être vide pour que la condition 3 soit satisfaite pour tout i . Mais si c'est le cas, il échoue à la condition 1 qui dit que y doit avoir au moins 1 longueur!

Si au contraire je laisse être soit a , byab ou alors il satisfera la condition 1 mais échouera à la condition 3 car il ne se répète jamais réellement.ab

De toute évidence, il me manque quelque chose d'esprit incroyablement évident. Lequel est?

Phil Wright
la source

Réponses:

29

Vous avez raison - nous ne pouvons pas permettre de "pomper" les mots d'un fini . Ce qui vous manque, c'est que le lemme dit qu'il existe un nombre pLp , mais ne nous dit pas le nombre.

Tous les mots plus longs que peuvent être pompés par le lemme. Pour un fini L , il se trouve que p est plus grande que la longueur du mot le plus long en L . Ainsi, le lemme ne tient que de façon vide et ne peut être appliqué à aucun mot de L , c'est-à-dire que tout mot de L ne satisfait pas à la condition "ayant une longueur d'au moins p " comme l'exige le lemme.pLpLLLp


Un corollaire: si a une longueur de pompage p , et qu'il existe un mot w L de longueur au moins p , alors L est infini.LpwLpL

A sonné.
la source
2
Une belle instance de l'ensemble vide remplissant les instructions .
Raphael
7

Le lemme de pompage est généralement utilisé sur des langues infinies, c'est-à-dire des langues qui contiennent un nombre infini de mots. Pour tout langage fini , puisqu'il peut toujours être accepté par un DFA avec un nombre fini d'états, L doit être régulier.LL

Selon wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), le pompage du lemme dit: (LΣ)(regular(L)((p1)((wL)((|w|p)((x,y,zΣ)(w=xyz(|y|1|xy|p(i0)(xyizL))))))))

Pour tout langage fini , soit l m a x la longueur maximale des mots dans L , et soit p dans le lemme de pompage soit l m a x + 1 . Le lemme de pompage tient car il n'y a pas de mots dans L dont la longueur l m a x + 1 .LlmaxLplmax+1Llmax+1

Wu Yin
la source
2

Une façon de formaliser la partie centrale du lemme de pompage est la suivante, en utilisant :Lk={wL|w|k}

Si est régulier, il existe p N pour queLpN

(*).wLp. x,y,z

Pour tout fini et p > max { | w | w L } , on a évidemment que L p = . Par conséquent (*) est (vide) vrai pour un tel p .Lp>max{|w|wL}Lp=p

Raphael
la source