Automate Minimal
kiddy
Voici mon problème:
Soit n un entier, on construit l'automate A(n) comme suit:
L'alphabet est {a,b}
L'ensemble des états est {q1,q2, ... , qn }
L'etat initial est q1
L'ensemble des états finals est {qn}
Pour tout i<n il y a une unique fleche indexee par a partant de qi
et qui aboutit en qi+1 . il n'y a pas de flèche indexée par a partant de
qn.
Pour tout i<=n, il y a une boucle indexée par b de qi, vers lui-meme,
ainsi qu'une fleche indexée par b partant de qi et qui aboutit en q1.
il n'y a pas d'autres flèches.
Soit B(n), l'automate obtenu en déterminisant A(n).
les questions sont:
1)Combien y-a-t-il d'etats dans B(n) ?
2)Montrez que B(n) est minimal.
Je ne vois pas comment montrer 1 et 2. Si vous pouvez m'aider.
Merci d'avance
Kiddy
Frederic
Pour la déterminisation : de q1, par a on atteint q2, et par b on
reste en q1. De q2, par a on atteint a3, et par b soit on retourne en q1,
soit on reste en q2, etc. Sur l'ensemble des états accessibles, prendre
un b ajoute q1 à l'ensemble des états dont on part, et lire un a
le translate d'un cran vers l'avant. Je prétends que l'automate
déterminisé possède 2^n-1 états. En effet :
{ q1 } est un état.
Si X est un état du déterminisé, alors X+1 (X décalé de 1) et
X union {q1} en est un aussi. Or ces deux opérations engendrent
toutes les parties non vides des états de l'automate de départ.
(Preuve : p. ex. si on veut créer {q1, q4, q5}, on part
de q1, puis on fait :
q1, a -> q2, b -> q12, a -> q23, a -> q34, a -> q45, b -> q145.
Pour un ensemble quelconque, ça marche pareil).
Bilan : B(n) possède 2^n-1 états.
Pourquoi est-ce minimal ?
J'ai la flemme de détailler, mais le premier rang de l'équivalence
de Myhill-Nerode stoppe (les classes d'équivalences sont triviales)
donc l'automate est minimal. Ça n'a pas l'air trop méchant à démontrer,
vu sous cet angle.
--
Frédéric
kiddy
dit...
Pour le nombre d'etats de B(n), on ne compte pas la poubelle ??
donc 2^n états ???
merci encore
Frederic
>Pour le nombre d'etats de B(n), on ne compte pas la poubelle ??
>donc 2^n états ???
Ah oui, j'ai oublié l'entrée a^{n+1}. 2^n états tout rond, donc.
--
Frédéric
kiddy
leo....@laposte.net dit...
J'ai bien compris pour la premiere question.
Mais pour la seconde c'est encore assez sombre.
Je n'ai jamais vu Myhill-Nerode, par contre les classes d'equivalences
oui.
Mais je crois que je n'ai pas bien compris car si c simple (pas pour moi
:(
Si vous avez un cours ou des exos pour que je puisse comprendre.
En fait, mon probleme c'est que je sais minimiser un automate mais je ne
sais pas montrer qu'un automate est minimal. Si vous pouvez me
l'expliquer rapidement par exemple pour B(3) ca serai vraiment cool.
Merci d'avance et encore pardon de vous déranger
Kiddy
Frederic
>Mais pour la seconde c'est encore assez sombre.
>Je n'ai jamais vu Myhill-Nerode, par contre les classes d'equivalences
>oui.
>Mais je crois que je n'ai pas bien compris car si c simple (pas pour moi
>:(
>Si vous avez un cours ou des exos pour que je puisse comprendre.
>
>En fait, mon probleme c'est que je sais minimiser un automate mais je ne
>sais pas montrer qu'un automate est minimal. Si vous pouvez me
>l'expliquer rapidement par exemple pour B(3) ca serai vraiment cool.
http://cs.engr.uky.edu/~lewis/essays/compilers/min-fa.html
Pour montrer qu'un automate est minimal, tu prends ton algorithme
de minimisation et tu montres qu'à la fin, toutes
tes classes sont distinctes (si tu appliques le même algorithme
que celui présenté sur cette page, ce que je pense, vu que
c'est l'Algorithme pour la minimisation).
Une autre méthode : le théorème de Myhill-Nerode donne le
cardinal de l'automate minimal. Si ton automate a le
même cardinal, c'est qu'il est minimal.
Pour un énoncé, cf. Wikipedia :
http://en.wikipedia.org/wiki/Myhill-Nerode_Theorem
Et pour une version française de l'algorithme de minimisation
auquel je pense, avec le preuve donc contenant un exemple
de démonstration qu'un automate est minimal :
http://pauillac.inria.fr/ups/private/ds.html
=> DS 9, Minimisation d'un automate
Bon courage et bonnes lectures... Si après ça tu as encore des
questions, n'hésite pas à les poser.
--
Frédéric