Automa

di il
10 risposte

Automa

Salve, ho provato a realizzare un automa con alfabeto {a,b} che deve accettare le parole con un numero pari di a ed un numero dispari di b.
Gli stati sono i seguenti:
• q0 = numero pari di a e di b;
• q1 = numero pari di a e numero dispari di b;
• q2 = numero dispari di a e numero pari di b;
• q3 = numero dispari di a e di b;

La soluzione del prof è questa:


Mentre la mia soluzione è questa:


Perchè la mia soluzione è sbagliata?

10 Risposte

  • Re: Automa

    Ma scusa, gia dal primo passaggio

    "" è in q0 (numero pari di a e di b)

    aggiungi una 'b' e secondo te finisci in q3 (numero dispari di a e b)? Quindi "b" la rigetti?
  • Re: Automa

    Il problema è che non ho capito con quale criterio va costruito l'automa, so che lo stato q0 corrisponde allo stato iniziale e lo stato q1 allo stato finale, ma poi non so come procedere.
    Ad esempio:
    Dopo aver fatto la prima assegnazione da q0 a q1


    posso passare la a da q0 sia a q3 che a q2
    perchè il prof l'ha passata proprio a q3?
  • Re: Automa

    Da q0 puoi aggiungere una 'a' o una 'b'. La freccia con la 'b' l'hai scritta giusta. Quella con la 'a' dove va a finire? A che stato appartiene "a"?
    Da ogni stato escono due frecce, perché puoi aggiungere o 'a' o 'b' , quindi ti mancano 7 altre frecce.
    Per sapere dove vanno le frecce inizia da un caso noto, non ti serve fare un percorso intero. Oppure parti da dove sei arrivato, ad esempio da "a" o da "b"
  • Re: Automa

    La a può andare sia in q3 che in q2.
    se la mando in q2 sbaglio ?
  • Re: Automa

    Non sbagli. Quindi che errore (ininfluente) ha fatto il professore?
  • Re: Automa

    Sinceramente non ho la più pallida idea di cosa avrebbe sbagliato influentemente il prof.
    sono arrivato a questa configurazione, ora il problema è che dovrei passare la a da q3 a qualche altro stato ma il problema è che "sono tutti occupati" .
  • Re: Automa

    Se parti da "b" (q1) e aggiungi una 'b' arrivi in "bb" (q0), non arrivi in q2, quindi hai sbagliato ancora.

    Il professore ha invertito le label q2 e q3: lo schema è corretto ma q2 è il nodo in basso a sinistra, q3 quello in basso a destra
  • Re: Automa

    Sono riuscito ad ottenere lo stesso automa che ha disegnato il prof.
    Ora mi chiedo:
    1) esiste solo una rappresentazione di un automa?
    2) io per risolvere l'automa ho fatto così:
    dopo aver risolto il caso noto (ovvero ho mandato la b (q0) in q1) ho provato con uno stato alla volta a mandare le lettere a e b agli altri stati e dopo ogni associazione mi sono assicurato che l'automa funzionasse (sebbene per stringhe ridotte), fino ad arrivare al punto in cui tutti gli stati sono stati occupati e che quindi qualsiasi parola di lunghezza variabile potesse essere riconosciuta.
    E' il metodo "mentalmente" più giusto per risolvere un automa?
  • Re: Automa

    1) Dipende dalle definizioni che avete dato. In generale no, tuttavia si possono definire certe relazioni o classi di equivalenza, quindi in un certo senso si può definire anche un concetto di "unicità". Chiedi direttamente al professore
    2) va bene
  • Re: Automa

    thomas99 ha scritto:


    Sono riuscito ad ottenere lo stesso automa che ha disegnato il prof.
    Ora mi chiedo:
    1) esiste solo una rappresentazione di un automa?
    No, ne esistono infinite MA c'e' un teorema che ti permette di dimostrare che sono tutti equivalenti, e ne esiste un'altro che ti permette di ottenere la versione minimizzata del DFA (Deterministic Finite Automata) e, corrispondentemente, TUTTE le versioni minimizzate sono le stesse a meno delle ettichette associate ai nodi.

    Ma tutte queste cose le dovresti GIA' sapere se ti hai studiato DFA/NFA!

    https://en.wikipedia.org/wiki/DFA_minimizatio
    https://en.wikipedia.org/wiki/Deterministic_finite_automaton
Devi accedere o registrarti per scrivere nel forum
10 risposte