Est-ce qu'un langage régulier L a des mots infinis? Ce

Question

est bizarre, mais par pompage lemme, par exemple

Soit L un langage régulier. Il existe une constante n telle que pour chaque chaîne w dans L tel que |w| >= n, nous pouvons casser w en xyz de sorte que xy*z soit également en L.

Ce lemme est fort car il argumente pour toutes les langues régulières. Mais que faire si la langue régulière L = a? Il n'y a qu'un seul mot (a) dedans. Comment le lemme de pompage fonctionne pour ce cas?

Answer 1

Si n = 2 alors il est vrai que tout vacuously w dans L avec |w| >= n satisfait à la conclusion du lemme de pompage. Aucun mot dans L sont assez longs pour servir de contre-exemples. Plus généralement, si L est une langue finie alors L satisfait le lemme de pompage: il suffit de prendre n pour être supérieur à la longueur du mot le plus long en L.