Problème d'automates!

[invite11923c3d]

Salut tous le monde,
j'ai un probleme sur les automates, (je joins l'automate que j'ai),
il me dis de donner 4 mots qui sont acceptés par cet automate.

Merci à vous
-----

[Médiat]

Bonjour,

Connaissez-vous la signification de cette notation ?

[invite11923c3d]

Je comprend pas que voulez vous dire??
j'ai un automate, j'ai sortie le langage correspondant (alphabet, ens des etats, fcts de transitions,...)

[Médiat]

Donc si vous connaissez ce formalisme, suivez-le, entrez par l'entrée et sortez par la sortie

[A voir en vidéo sur Futura]

[invite11923c3d]

je joins ma solution est ce que vous pouvez me dire si c'est juste,svp?
pour la 1ere question c'était donnez M=(A,Q,CIGMA,q0,F)
est ce que vous pouvez mexpliker la 3eme question aussi:
Question 3 Given an arbitrary automaton M = (A, Q, δ, q0, F), explain how
could one determine whether M accepts at least one word.

[Médiat]

Oui, les 4 mots que vous avez extrait sont corrects

[invite11923c3d]

Ho super alors
avez-vous une idée comment je commence la Q3

[Kairn]

Voilà comment on m'a appris à déterminiser un automate :

Tu fais un tableau à 3 lignes (parce que tu as 2 lettres) et un nombre indéterminé de colonnes.
- 1ère colonne : tu laisse vide la 1ère case ; tu mets a et b dans les deux autres.
- 2è colonne : tu inscrit {q0} dans la première case (c'est ton état initial). Dans la ligne du "a", tu notes l'ensemble des états accessibles depuis q0 avec la lettre "a" ; dans ton cas il s'agit de {q2}. Tu fais la même chose avec "b" : tu as {q1}.
- tu inscris dans la première ligne les ensembles que tu n'as pas encore traités chacun dans une case, c'est-à-dire {q1} et {q2}, et tu leur appliques séparément le même traitement.
- Tu continues de la sorte jusqu'à ne plus avoir d'ensemble non traité.

Tu peux maintenant construire l'automate déterministe équivalent :
- les états sont les ensembles de la première ligne du tableau
- l'état initial reste q0
- les états finaux sont les ensembles contenant un état final de l'automate d'origine
- et les lignes 2 et 3 du tableau t'indiquent les transitions

Je sais pas si c'est très clair, alors je joins un début de déterminisation pour un automate, histoire d'illustrer tout ça .

[invite11923c3d]

Merci pour votre explication
Mais j'ai pas compris pk vous avez fait un nouveau automate?
Ma question est dimplementer une procedure qui permet a un automate daccepter un mot ou non, c.a.d je lui donne un mot et si ce mot est accepté par mon automate return true else false le mot nest pas accepté

[Kairn]

Ah excuse moi, j'ai lu trop vite la question, c'est pas du tout ça que tu demandais...

Hmm, ça va dépendre de comment ton automate est implémenté, mais en gros pour le mot a1.a2...an tu dois vérifier qu'il existe une transition (p0,a1,p1), puis une transition (p1,a2,p2), puis [...], puis une transition (p(n-1),an,pn), où p0 doit être un état initial et pn un état final.

[invite11923c3d]

Bonjour,

J'ai fait un ptit programme (pas complet), pouvez vous me dire si cest juste

[Kairn]

J'ai l'impression que tu as les bons trucs, mais je connais pas le langage alors je sais pas si c'est correct