Bonsoir,

On sait que pour démontrer qu'un langage L n'est pas régulier,

il suffit de le montrer qu'il ne vérifie pas la condition nécessaire de la lemme de l'étoile,

c'est à dire trouver une chaine w /: |w| > N , avec toutes les décompositions de w en XYZ,

X Y^i Z n'appartienerat pas à L ...

supposons que j'ai le langage des palindromes (qui n'est pas régulier),

le problème est que quelque soit la chaine que j'ai choisie, comme a^N b a^N, ou a^N b^N a^N, ou a^N b^N b^N a^N, ...

la décomposition de l'une de ces chaines en X = epsilon, Y = la chaine entière, et Z = epsilon, XY^iZ me rend toujours dans L quelque soit i,

Donc comment choisir une bonne chaine comme palindrome, pour prouver que L n'est pas régulier ?

Et merci beaucoup d'avance.

-
Edité par ABX 23 mai 2018 à 21:40:07

Tout ceci n'a aucun sens.

Quelqu'un peut m'aider ?

Le texte n'a aucun sens en Français on ne le peut donc en l'état.

Salut,

Ryan : ce n'est pas parce que tu ne comprends pas que ça n'a aucun sens...

ABX : Alors forcément si tu as x et z qui sont vides, ça ne va pas t'avancer à grand-chose. Cela dit, n'oublie pas une des conditions de l'application du lemme, quelle est la condition sur y que l'on a pour pouvoir appliquer le lemme ?

melepe : Merci beaucoup pour votre réponse ..

je rapelle deux conditions sur Y

la première est que Y doit-être différente de la chaîne vide,

et la deuxième |XY| < N

c'est ça ce que tu signifie ?

Ouaip.

Notamment, fais attention à ce que la longueur de xy ne dépasse pas N.

Si je cite ton message :

> le problème est que quelque soit la chaine que j'ai choisie, comme a^N b a^N, ou a^N b^N a^N, ou a^N b^N b^N a^N, ...

> la décomposition de l'une de ces chaines en X = epsilon, Y = la chaine entière, et Z = epsilon, XY^iZ me rend toujours dans L quelque soit i,

Tu vois d'où vient ton erreur ? Après tu n'arriveras pas à prouver l'irrationalité de L avec a^N b a^N, mais tu devrais pouvoir trouver d'autres exemples qui eux seront satisfaisants.

-
Edité par melepe 26 mai 2018 à 0:23:30

melepe a écrit:

Salut,

Ryan : ce n'est pas parce que tu ne comprends pas que ça n'a aucun sens...

ABX : Alors forcément si tu as x et z qui sont vides, ça ne va pas t'avancer à grand-chose. Cela dit, n'oublie pas une des conditions de l'application du lemme, quelle est la condition sur y que l'on a pour pouvoir appliquer le lemme ?

Autant pour moi ce sont les : la lemme de l'étoile  : il suffit de le montrer

Qui m'avait amené à conclure trop rapidement pour quelques erreurs sans importance.

Désolé pour l'auteur.

-
Edité par Eridabis 26 mai 2018 à 1:36:31

RyanCarrier : Ce n'est pas grave du tout ;-)

melepe :  peut tu m'aider dans le choix d'une chaine 

qui prouve l'irrégularité de cette langage ?

ABX : mon mauvais, en fait a^Nba^N fonctionne... Essaie d'appliquer le lemme de l'étoile, n'oublie pas les conditions d'applications. Qu'est-ce que ça donne ?

pour la décomposition : X = epsilon,  Y = a^N b a^N,  Z = epsilon,

on peut utiliser la deuxième condition du lemme : |XY| < N  n'est pas vérifiée;

car |XY| = |X| + |Y| = 0 + (N + 1 + N) = 2N + 1 > N

pour la décomposition X  = a^N,  Y = b,  Y = a^N

on peut utiliser aussi la deuxième condition du lemme : |XY| < N  n'est pas vérifiée;

car |XY| = |X| + |Y| =  N + 1 > N

et pour toutes autres décompositions :

X  Y^i  Z  détruit le fait que la chaînes soit une palindromes 

c'est vrai comme ça ?

-
Edité par ABX 29 mai 2018 à 0:01:43

C'est ça ! Après, il faut y mettre les formes.

Le lemme de l'étoile dit : "soit L un langage rationnel, et w un mot. Il existe une décomposition XYZ avec |XY| < N telle que pour tout i, XY^îZ soit dans L.

Ici, la condition |XY| < N implique que X = a^k et Y = a^l avec k+l < N, et que toute combinaison XY^iZ résultante ne sera pas un palindrome, vu qu'il y aura l + i*l + (N-k-l) a avant le b et N seulement après le b. Autrement dit, il n'existe pas de décomposition de a^Nba^N telle que le lemme de l'étoile soit vrai, ce qui signifie que le langage des palindromes n'est pas rationnel.

-
Edité par melepe 29 mai 2018 à 2:01:36

merciii beaucoup pour votre patience et pour votre attention !! ^_^

-
Edité par ABX 29 mai 2018 à 21:24:08