Discussion :

[serigne mbaye SARR]

Bonjour
j'ai un problème à résoudre l'exercice suivant

exercice:

Prouver que
1- le langage L1={uw: |u|=2|w|} est régulier
2- le langage L2={(a+b)n.bn | n} ∈ N n'est pas régulier
3- discuter de la rationalité de L3={an.bn.(a+b)m |n ∈ N et m>0}

[dourouc05]

Pour ton L1, tu es sûr que le langage est régulier ? J'imagine sans peine un automate à pile pour accepter le langage, mais pas un automate fini non déterministe pour n'importe quelle longueur de mot…

Pour L2, tu as dû apprendre des techniques de preuve pour ça, ne les comprends-tu pas ?

[serigne mbaye SARR]

Pour L2 je sais comment faire.
Pour L3 je voulais le faire comme L2 (pompage) mais vu qu'on dit "discuter" je crois qu'on doit jouer sur m et n.
Pour L1 j'ai pensé à un automate modulo 3. mais je sais pas comment le représenter

[dourouc05]

L1 : jamais entendu parler d'un "automate modulo 3" . Ou alors c'est un automate qui accepte tous les nombres (représentés dans une base intéressante) égaux à zéro modulo 3 ?

L3 : j'ai du mal à voir sur quoi tu devrais baser ta discussion, vu qu les paramètres m et n sont dans l'ensemble (tu génères des mots pour chaque paire de valeurs possible pour m et n). Peut-être attend-on de toi de donner une intuition derrière ?