Rimuovere epsilon transizioni automi non deterministici

di il
5 risposte

Rimuovere epsilon transizioni automi non deterministici

Salve,
ho un automa non deterministico con epsilon transizioni, vorrei eliminare tali transizioni, dove possibile, qual è l'algoritmo da usare?
Vi ringrazio per la disponibilità.

Saluti

5 Risposte

  • Re: Rimuovere epsilon transizioni automi non deterministici

    Hai già l'algoritmo per passare da NFA a DFA o devi partire da 0? Posso assumere che conosci il concetto di epsilon-closure?
  • Re: Rimuovere epsilon transizioni automi non deterministici

    Grazie per aver risposto.
    Non ho l'algoritmo per trasformare un NFA in un DFA, ma perché togliere le epsilon transizioni significa trasformare un NFA in un DFA?
    In merito all'epsilon-closure ho un po' di dubbi su come implementarla, ho compreso che le transizioni etichettate con epsilon vengono eliminate e sostituite con nuove transizioni che mi permettano di raggiungere stati finali raggiungibili solo attraverso epsilon transizioni, ma non so se questo mi basta per produrre codice funzionante.
  • Re: Rimuovere epsilon transizioni automi non deterministici

    Avere epsilon-transizioni implica avere un NFA, mentre non vale necessariamente il contrario. In ogni caso, l'algoritmo per passare da un epsilon-NFA a un DFA deriva, con minime variazioni, da quello necessario per passare da un generico NFA a un DFA. Non credo abbia molto senso rimuovere le epsilon-transizioni per ottenere comunque un NFA (anche se magari in teoria è possibile).

    Dato un insieme di stati S raggiungibili applicando una stringa di input alfa ad un certo stato iniziale all'interno di S, la epsilon closure di S è S union "stati raggiungibili da S tramite sequenze di epsilon-transizioni".

    Il DFA finale ha come stati le psilon-closure di insiemi di stati dell'automa di partenza (è questa l'unica differenza rispetto all'algoritmo per NFA normali, dove gli stati del DFA sono semplicemente insiemi di stati del NFA) così ottenute:
    1. Si inizia prendendo la epsilon-closure dello stato iniziale del NFA e la si mette in una coda; essa sarà lo stato iniziale del DFA;
    2. Per ogni closure nella coda:
    I. trova le epsilon-closure raggiungibili, a partire da quella estratta, applicando una singola transizione;
    II. per ogni closure trovata, se non era già stata visitata:
    a. aggiungila alla coda;
    b. crea un nuovo stato nel DFA corrispondente alla closure e collegato al precedente mediante lo stesso tipo di transizione che collegava la closure trovata a quella estratta dalla coda;
    3. Segna come stati finali del DFA tutti quegli stati raggiungibili mediante la/le stringa/stringhe con cui si raggiungevano gli stati finali dell'automa di partenza (questo è forse il passaggio più difficile, se non conosci a priori le stringhe in questione, ma fortunatamente solitamente le stringhe sono note perché l'automa viene creato in funzione di esse).
  • Re: Rimuovere epsilon transizioni automi non deterministici

    Grazie ancora per la risposta.
    A dir il vero, non devo trasformare l'NFA in un DFA, o per lo meno non ora. Sto' facendo un progetto per il quale mi si chiede di usare la epsilon-closure ma di non fare un DFA, per fare ciò mi è stato suggerito il metodo warshall, quindi la domanda è: secondo te è fattibile questa cosa? cioè posso eliminare le epsilon transizioni senza trasformare l'NFA in un DFA?
    Grazie!
  • Re: Rimuovere epsilon transizioni automi non deterministici

    Non conosco il metodo warshall, per cui non so dirti. Comunque resto dell'idea che togliere le closure senza eliminare gli (eventuali) altri stati non deterministici non abbia senso. Potresti postare (o mandarmi in pm) i requisiti del progetto?

    Eventualmente potrei chiedere al mio prof di compilatori se è una cosa fattibile, ma prima vorrei accertarmi che non si tratti magari di un errore di comprensione dei requisiti.
Devi accedere o registrarti per scrivere nel forum
5 risposte