Residuel d'un langage

[naruto-next]

Bonjour,



j'ai un langage L = ( b(ab)* + (ab)*a )

je veux le residuel de L par rapport à "a"

je trouve : (ab)* + b(ab)*a + 1

1 represente le mot vide .

mais le prof a trouvé : 1 + b(ab)*a

bref je suis perdu je demande donc pourquoi je n'arrive pas a calculer correctement . je me fit à ca pour le calcul :

image

[Doraki]

comment tu peux avoir "ab" dans ton langage résiduel par rapport à "a" si "aab" n'est pas dans L ?

[naruto-next]

comment tu peux avoir "ab" dans ton langage résiduel par rapport à "a" si "aab" n'est pas dans L ?

justement je sais que j'ai faux mais j'applique les formules et c'est ce que j'obtiens ...

[Doraki]

Tu peux écrire le détail de ton calcul ?

[naruto-next]

Tu peux écrire le détail de ton calcul ?

sur mon calcul lorsque j'applique la formule je trouve des truc pas cohérent par exemple :

puisque mot vide n'appartient pas au langage vide
et le resultat n'est pas cohérent ...

merci beaucoup en tout cas pour ton aide

[Doraki]

que dit ton formulaire à propos de a-1.(b) ?

[naruto-next]

que dit ton formulaire à propos de a-1.(b) ?

il dit ensemble vide , si b est different de a .

tu fais reference à ??

ca donne ensemble vide . (ab)* donc (ab)*

[Doraki]

Tu peux m'expliquer pourquoi tu penses que la concaténation du langage vide avec L = (ab)* donne L ?
Par exemple, (ab) est dans L mais j'arrive pas à trouver de décomposition ab = u.v où u est dans le langage vide et v est dans L.

[naruto-next]

Tu peux m'expliquer pourquoi tu penses que la concaténation du langage vide avec L = (ab)* donne L ?
Par exemple, (ab) est dans L mais j'arrive pas à trouver de décomposition ab = u.v où u est dans le langage vide et v est dans L.

en effet , si la concatenation du langage vide avec un autre langage donne le langage vide a ce moment la tout les resultats du prof coïncide

merci de m'avoir aidé

[naruto-next]

je revise et là j'ai un autres soucis :id: .

j'ai un automate A , je veux automate AM qui correspond à l'automate minimal de A .

donc un automate avec le moins etat mais qui reconnait le meme langage .

j'utilise l'algo de moore mais je trouve un automate qui reconnait un autres langage ...

voici automate :

automate A

je pense a vu d'oeil que cet automate reconnait le langage bab(ab)*

je veux donc un automate minimal qui reconnait le meme langage .

Methode de Moore :

0 1 2 3
B I II I II
a v I v I
b II v II v
B I II I II
a v I v I
b II v II v
B I II I II

donc la d'après le tableau il y aura deux etat I et II avec I->II etiqueté par b et II->I etiqueté par a
etat initial I et final

bref cet automate que j'obtiens reconnait : (ba)* ce qui ne coincide pas avec l'automate de base

ai je mal utilisé l'algorithme de Moore ?

[Doraki]

L'automate initial reconnaît b(ab)*, et dans ton automate simplifié tu t'es trompé d'état final.

[naruto-next]

Super , merci de ton aide , une dernière chose que je ne maitrise pas ensuite j'arrête de reviser les automate .

peut tu m'expliquer comment obtenir une expression reguliere en fonction d'un automate ? en utilisant la methode de macnaughton-Yamada .

pour cet exemple :

automate

[Doraki]

Ben ... tu appliques la méthode sans te gourrer ?

[naruto-next]

Ben ... tu appliques la méthode sans te gourrer ?

bah avec la formule :



j'obtiens :



soit (b(bb)*+ab(bb)*) + (aa+(bb+abb).(bb)*a(b(bb)*ba+a)*.b(bb)*)

est ce correct ?

[Doraki]

Ca veut dire quoi tes 9 ?
T'as calculé l'automate minimal ?

Est-ce que y'a bbaabbaab qui est accepté par ton expression régulière ?

[naruto-next]

Ca veut dire quoi tes 9 ?
T'as calculé l'automate minimal ?

Est-ce que y'a bbaabbaab qui est accepté par ton expression régulière ?

les 9 correspond en faite à "+" je viens de corrigé , faute de frappe ...

bbaabbbaab n'est pas reconnu sur mon expression alors que automate si donc j'ai faux :zen: .

alors sachant que la formule dit : aller de 1 à 2 sans passer par les etat sup à 5 ( donc aucun etat) vaut :

aller de 1 à 2 privée de 5 ou aller de 1 à 5 privée de 5 concatener avec (aller de 5 à 5 privée de 5)* concatener avec aller de 5 à 2 privée de 5

bbaabbaab : je pense que mon expression n'accepte pas en faite le deuxieme a elle arrive a bba et ensuite elle ne peut faire le a suivant car elle est privée de 5 donc je comprend pas ...

[Doraki]

Est-ce que tu as calculé l'automate minimal ?

T'as un lien ou un cours où la méthode est expliquée en détail ou est-ce que tu vas sortir une fraction de phrase de la méthode par jour avant qu'on puisse voir où est-ce que tu l'appliques mal ?

Parceque non, une formule absconse au hasard sortie de tout contexte, c'est pas près de me dire ce que tu es censé faire dans cette méthode.

Et sinon est-ce que tu as calculé l'automate minimal ?

[naruto-next]

Est-ce que tu as calculé l'automate minimal ?

T'as un lien ou un cours où la méthode est expliquée en détail ou est-ce que tu vas sortir une fraction de phrase de la méthode par jour avant qu'on puisse voir où est-ce que tu l'appliques mal ?

Parceque non, une formule absconse au hasard sortie de tout contexte, c'est pas près de me dire ce que tu es censé faire dans cette méthode.

Et sinon est-ce que tu as calculé l'automate minimal ?

je n'ai pas calculé l'automate minimal , la methode de macnaughton yamada est censé permettre d'obtenir une expression rationnel d'un automate .

http://www.desmontils.net/emiage/Module209EMiage/c6/Ch6_4.htm

mais en fait bbaabbaab est bien reconnu ...

[Doraki]

tu as donc, en découpant le mot "bbaabbaab" à chaque fois qu'il passe par l'état 5, 5 possibilités :

- ton L(1->5) sans passer par 5 ne contient pas "bba", dans ce cas-là il est faux
- ton L(5->5) sans passer par 5 ne contient pas "a", dans ce cas-là il est faux
- ton L(5->5) sans passer par 5 ne contient pas "bba", dans ce cas-là il est faux
- ton L(5->2) sans passer par 5 ne contient pas "b", dans ce cas-là il est faux
- Tu as mal recopié la formule.

Je te laisse remonter à la source de(s) l'erreur(s) comme ça.