Annuler
connectez vous
logique en post-bac
- Description de mathématique formelle-termes et relations
- Théorèmes
- Théories logiques
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Langage non-rationel
Posté par Foxi1309
Bonjour,
Je dois demontrer que le langage {ww| w
{0;1}* } n'est pas rationnel.
Si j'ai bien compris, je dois employer la lemme de pompage, le probleme etant que je ne comprends pas son enonce et donc ne vois pas du tout comment l'employe
Merci d'avance
On l'appelle sinon lemme de l'etoile, d'apres Wiki:
Lemme de l'étoile —
Soit L un langage rationnel. Il existe un entier N tel que tout mot w de L de longueur |w|
N possède une factorisation w=xyz telle que
0<|y|
N et
xy^{n}z L pour tout entier n 0.
Ici: https://fr.wikipedia.org/wiki/Lemme_de_l%27étoile
(desole pour cette definition copiee, mon cours est en polonais.)
Bonjour !
Tu devrais prendre un mot et voir à quoi ressemblent les facteurs donnant
.
A mon avis ne sera pas dans le langage (impossible de le mettre sous la forme
).
Merci pour ton aide. J'ai essaye de bricoler qqch, et l'exercice a ete corrige en TD:
Admettons qu'il s'agisse d'un langage rationnel, on a donc un facteur n, d'apres le lemme de l'etoile. Soit w=0n10n un mot de ce langage, avec |w|>n.
On a donc w=uvz, |uv|n, |v|>0, pour tout i uviz appartient a ce langage => v=0j, j0
Cependant, 10n1 n'appartient pas a ce langage, donc contradiction, donc le langage n'est pas rationnel.
Je n'arrive juste pas du tout a comprendre cette histoire de decomposition et d'appartenance ou pas :/ Est ce que qqn pourrait m'expliquer plus "ideologiquement" le lemme? :/
Merci d'avance
Surtout que mnt je me retrouve avec un exercice analogique, sauf que le langage a analyser est {an[sup]2[/sup] |n 
}
Et je ne suis pas d'accord avec "ton" corrigé !
Le mot n'est pas dans le langage
de ton énoncé.
Tout mot de ce langage est la juxtaposition de deux mots identiques ce que je ne vois pas dans ton exemple .
Il faut donc revoir ou ton énoncé initial ou ce que tu as compris du corrigé donné !
Je te signale par ailleurs que tu utilises un "lemme de l'étoile" différent de celui que tu as copié dans wiki (ils sont peut-être équivalents mais il a une différence entre " " selon wiki et "
" selon "ton" corrigé).
......................................
Quant à "l'idéologie du lemme" je ne peux que te renvoyer à ton cours (RTFM - Read The Fucking Manual- comme disent certains SAV quand on demande une information qui est déjà dans un manuel qu'on a négligé de lire)