Stati dell'automa deterministico

Se un automa non deterministico ha k stati, quanti stati può avere al massimo l'automa deterministico corrispondente?

L'ha chiesto il Mancarella all'orale, ma non mi è chiara la risposta.
È riguardo alla trasformazione di un automa deterministico in uno non deterministico.

In un automa non deterministico Q è l'insieme degli stati. In questo caso |Q|=k.
Nel corrispondente automa deterministico l'insieme degli stati sarà Parti di Q, ovvero l'insieme di tutti i possibili sottoinsiemi di Q.
Se non sbaglio la cardinalità di Parti di Q dovrebbe essere2 ^k, ma bisogna escludere l'insieme vuoto, quindi credo sia (2^k)-1.

È giusto?

Comments

  • MindFlyerMindFlyer Posts: 436
    Allora, ci sono tre tipi di risposta che si può dare a questa domanda di Mancarella.

    Il primo è che la domanda è mal posta, perché non esiste L'automa deterministico corrispondente, ma ne esistono infiniti, con un numero arbitrariamente alto di stati. Quindi non ha senso chiedere quanti stati può avere al massimo un siffatto automa.

    Il secondo tipo di risposta è quello che hai dato, e forse era quello che voleva sentirsi dire lui.

    Il terzo tipo di risposta presuppone che quella di Mancarella non sia una non-domanda, e inoltre che quella che si aspetta non sia una non-risposta. Qui le cose diventano più interessanti, perché il problema è quello di trovare, per ogni [tex]k[/tex], un automa non deterministico di [tex]k[/tex] stati il cui corrispondente automa deterministico minimo abbia esattamente [tex]2^k−1[/tex] stati. Questa è una domanda interessante che merita un po' di studio (una risposta è qui, ma credo che ne esistano di più semplici).
    Però si può ottenere in modo elementare qualcosa di più debole, ed è un utile esercizio:

    Esercizio. Per ogni [tex]k\geqslant 1[/tex], costruire un automa non deterministico di [tex]k[/tex] stati il cui automa deterministico minimo corrispondente abbia [tex]2^{k-1}[/tex] stati.
  • mz_mz_ Posts: 60
    sulle dispense del Degano di Calcolabilità e Complessità trovi un paragrafo al riguardo
  • MindFlyerMindFlyer Posts: 436
    edited January 2015
    mz_ wrote: »
    sulle dispense del Degano di Calcolabilità e Complessità trovi un paragrafo al riguardo
    Purtroppo quel paragrafo non dice nulla di più di quello che ho scritto sopra, ma contiene una soluzione al mio esercizio (quella standard presa dall'Hopcroft, per inciso). Sto arrivando alla conclusione che massimizzare davvero il numero di stati dell'automa minimo sia un problema troppo difficile per essere una domanda da esame.
Sign In or Register to comment.