Langage rationnel

[Arshan]

Bonjour,
Je suis en L3 Info, j'ai un DS Mercredi, et je ne comprends pas très bien une notion du cours sur les langages : comment prouver qu'un langage n'est pas rationnel ?

J'ai par exemple le langage L = { a^n b^n | n ;) N } et je dois prouver qu'il n'est pas rationnel avec l'algorithme de Kleene. Donc je suppose par l'absurde qu'il est rationnel, et selon l'algorithme, L doit alors pouvoir être reconnu par un automate fini. Je ne vois pas comment prouver que ce n'est pas le cas.

Merci pour votre aide :id:

[L.A.]

Bonjour.

Suppose que ton langage est reconnu par un automate fini déterministe, et note S_n l'état sur lequel on aboutit quand on lit le mot a^n. Comme l'automate est fini il existe un couple i

[Arshan]

Je te remercie pour ton explication, je saisis mieux la logique du raisonnement

[Groucho]

Pour ce genre de question, on dispose du "pumping lemme" (il y a plusieurs traduction en français, celle que je préfère est : lemme du pompier). Va

[Groucho]

Pour ce genre de question, on dispose du "pumping lemma" (il y a plusieurs traductions en français, celle que je préfère est : lemme du pompier). Va voir

http://fr.wikipedia.org/wiki/Lemme_de_l%27%C3%A9toile

où ton exercice est traité en exemple. La preuve qui t'en est donnée par LA n'en est qu'un cas particulier.