Equation de langage et automate

[Rockleader]

Bonsoir, je me suis cassé la tête sur ce problème toute l'aprèm...je vais à présent m'avouer vaincu et demander de l'aide.

J'ai deux langages caractérisé par les équations suivante

L0 = aL2 + bL1 + lambda
L1 = aL2 + lambda
L2 = aL1 + lambda

et

L3 = aL4+bL5+lambda
L4=bL3
L5=aL3

Je dois démontrer que L4L3 + L4 = L4L3 et ensuite on admettra que L5L3 + L5 = L5L3

J'ai beau me casser la tête je ne vois absolument pas comment faire ça...

Pour la suite, construire l'automate de trois états reconnaissant L3L3

L3L3 =
(aL4+bL5+lambda)L3 =
a(L4L3) + b(L5L3) + L3 =
a(L4L3) + b(L5L3) + aL4+bL5+lambda
= a(L4L3 + L4) + b(L5L3+L5) + lambda
= a(L4L3) + b(L5L3) + lambda (grâce à ce qu'on a trouvé tout à l'heure en 1)

L4L3= bL3L3
L5L3 = aL3L3

Donc la dessus par de soucis, je peux construire l'automate avec cette équation.


Par la suite l'on me demande de montrer que L3L3 = L3


L3L3= a(L4L3) + b(L5L3) + lambda

L3 = aL4+bL5+lambda

Donc il me faudrait prouver que L4 = L4L3 et L5 = L5L3

Et là je suis aussi bloqué...je peux bien écrire L4 = bL3L3 et L5=aL3L3 mais ça ne m'avance pas plus vu que je n'ai aucun moyen de simplifier tout ça...je ne fais que tourner en rond...

Ensuite je dois déduire un automate qui reconnaît L3* ... aucun soucis avec ça non plus étant donné que L3L3 = L3 par récurrence on peut arriver à L3* = L3 et donc reprendre l'automate précédent déterministe ou même celui de la consigne non déterministe dans le système d'équation.





Bref pour résumer ce qui me bloquer c'est de montrer

L4L3 = L4L3 + L4

et

L3L3 = L3

En espérant que vous pourrez m'aider =) :mur:

[Doraki]

C'est quoi lambda ?

[Rockleader]

C'est quoi lambda ?

C'est l'élément neutre.

lambda . L = L

L. lambda = L

Et lambda symbolise un état final de l'automate.

[Doraki]

lambda = {mot vide} ?

Ben alors L3 contient le mot vide,
et donc L4 est inclus dans L4L3, et donc L4L3 + L4 = L4L3 (procède par double inclusion si tu vois pas que A+B= A veut dire exactement la même chose que B inclus dans A)


Pour ton autre question, si tu regardes très très fort les automates de L3 et de L3L3
(rappel : les équations sont
L3 = aL4 + bL5 + lambda
L4 = bL3
L5 = aL3

L3L3 = aL4L3 + bL5L3 + lambda
L4L3 = bL3L3
L5L3 = aL3L3
)
ben tu verras que sont les mêmes.

[Rockleader]

Oui lambda est le mot vide.

et donc L4 est inclus dans L4L3, et donc L4L3 + L4 = L4L3 (procède par double inclusion si tu vois pas que A+B= A veut dire exactement la même chose que B inclus dans A)

AH d'accord, j'étais parti dans les équations et je ne voyais vraiment pas comment faire; et je dois bien avouer que je n'avais pas penser à raisonner comme ça.

Merci !


Pour l'autre question, je suis pas totalement convaincu.

Ok l'automate est le même, mais les états ne sont pas les mêmes; donc, comment je peux être certain que l'état L4 est égal à l'état L4L3 et que l'état L5 est égal à l'état L5L3

Parce que plus haut du coup on aura prouvé que L4 est inclus dans L4L3; mais le fait d'être inclus n'implique pas l'égalité nan ?



Merci beaucoup pour ta réponse, et désolé si je suis un peu "lourd", je veux être certain de bien comprendre^^

[Doraki]

Ben le langage accepté par un automate ne dépend pas de comment tu as appelé les états qui le composent.

Par exemple si t'as un automate qui accepte seulement le mot "a"

-> (1) -a-> (2) ->

ben l'automate suivant où on a changé le nom des deux états

-> (abricot) -a-> (lampadaire) ->

suprise ! le langage qu'il accepte est le même qu'avant, c'est {a}


Si vraiment ça te plait pas, tu peux montrer par récurrence sur la longueur des mots,
que pour tout mot w,
((w est dans L3 <=> w est dans L3L3) et (w est dans L4 <=> w est dans L4L3) et (w est dans L5 <=> w est dans L5L3)).

(donc que L3 = L3L3 etc)

[Rockleader]

Dac merci beaucoup c'est compris :)