Lemme de l'étoile

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En théorie des automates, le lemme de l'étoile (ou lemme de la pompe) établit que si un mot suffisamment grand est reconnaissable par un automate fini, alors on peut en répéter une certaine partie autant de fois que l'on veut et obtenir des mots toujours reconnaissables. Ceci est dû au fait qu'il y a alors un cycle dans l'automate.

[modifier] Énoncé

Soient L un langage régulier, et A un automate fini déterministe (Q,Σ,δ,qo,F) tel que L = L(A).

Pour tout mot \omega \in L tel que |\omega| \geq Card(Q), il existe x, u, y \in \Sigma ^{*}, tels que u \neq \epsilon et |x.u| \leq Card(Q), vérifiant x.u.y = ω et \forall n \geq 0, x.u^{n}.y \in L.

[modifier] Applications

On utilise fréquemment la contraposée du lemme de l'étoile pour montrer qu'un langage (tel que \{a^nb^n|n\in N\}) n'est reconnaissable par aucun automate fini et n'est donc pas rationnel. En effet, d'après le théorème de Kleene, un langage est rationnel si et seulement s'il existe un automate fini qui le reconnaît.

[modifier] Voir aussi