Domanda su automi a stati finiti
Salve, in Laboratorio di Programmazione 1, al primo anno del corso di triennale di matematica, abbiamo fatto gli automi a stati finiti, e tuttavia non ci è stato spiegato bene come si determinano tutte e sole le stringhe che vengono accettate da un automa. Dato che si avvicina la prova intercorso, volevo chiedervi se ci fosse un metodo del genere e quale fosse.
Risposte
Dipende dall'automa, no?
Scusa, forse dovevo esprimermi meglio: preso un qualunque automa a stati finiti, esiste un modo per formalizzare il problema, in modo tale da trovare tutte e sole le stringhe che vengono accettate dall'automa?
Definisci "trovare". Ci sono molti modi di rispondere; il mio preferito è questo, leggi le prime pagine.
Non mi viene un modo per definire "trovare", quindi faccio un esempio: mi viene presentato un'automa con due stati Q e P, dove P è quello di accettazione. Se tale automa legge 1 quando sta nello stato Q, va nello stato P, se legge 0 rimane in Q. Una volta in P, se legge 0 rimane in P, se legge 1 ritorna in Q. Allora, certamente le stringhe che possono essere divise come ripetizioni di stringhe in cui è presente un numero dispari di 1, saranno accettate, e non mi sembra ce ne siano altre, il punto è che è un'idea intuitiva basata su un numero finito di tentativi, mentre io vorrei formalizzarlo in modo da dimostrare che solo queste sono le soluzioni.
Ti ringrazio per il link, che proverò a leggere, ma già dal titolo, penso che sia un po' oltre la mia portata.
Ti ringrazio per il link, che proverò a leggere, ma già dal titolo, penso che sia un po' oltre la mia portata.
Suppongo \(Q\) sia lo stato iniziale dell'automa. In tal caso puoi dimostrare la tua proposizione come segue.
Sia \(s\) una stringa accettata dal tuo automa. Sappiamo che per essere stata accettata la stringa deve essere passata dallo stato \(Q\) a \(P\) \(M + 1\) volte e da \(P\) a \(Q\) \(M\) volte. Siccome ogni passaggio di stato è causato da un \(1\) nella stringa, mentre gli zeri vengono in pratica ignorati, allora \(s\) avrà \(2\,M + 1\) \(1\) e un numero arbitrario di \(0\).
Viceversa se la tua stringa ha un numero dispari \(2K + 1\) di \(1\), sarà passato da \(Q\) a \(P\) \(K + 1\) volte e da \(P\) a \(Q\) \(K\) volte per cui verrà accettando finendo nello stato \(P\).
In generale credo che il metodo più semplice per sapere quali stringhe sono accettate da un automa è quello di trasformarlo in una regex (espressione regolare).
Sia \(s\) una stringa accettata dal tuo automa. Sappiamo che per essere stata accettata la stringa deve essere passata dallo stato \(Q\) a \(P\) \(M + 1\) volte e da \(P\) a \(Q\) \(M\) volte. Siccome ogni passaggio di stato è causato da un \(1\) nella stringa, mentre gli zeri vengono in pratica ignorati, allora \(s\) avrà \(2\,M + 1\) \(1\) e un numero arbitrario di \(0\).
Viceversa se la tua stringa ha un numero dispari \(2K + 1\) di \(1\), sarà passato da \(Q\) a \(P\) \(K + 1\) volte e da \(P\) a \(Q\) \(K\) volte per cui verrà accettando finendo nello stato \(P\).
In generale credo che il metodo più semplice per sapere quali stringhe sono accettate da un automa è quello di trasformarlo in una regex (espressione regolare).
@apatriarca: grazie, per aver risposto.
Mi è piaciuto il metodo, ma non ho idea di cosa sia un'espressione regolare. Se non ti reca disturbo potresti consigliarmi qualche link o qualche testo per capire cosa sono e come applicarli agli automi?
Mi è piaciuto il metodo, ma non ho idea di cosa sia un'espressione regolare. Se non ti reca disturbo potresti consigliarmi qualche link o qualche testo per capire cosa sono e come applicarli agli automi?
Una espressione regolare su un alfabeto \(A\) è una espressione formata dalle seguenti costanti:
1. l'insieme vuoto \(∅\),
2. l'insieme contenente solo la stringa vuota \(\{ε\}\),
3. l'insieme \(\{a\}\) contenente il solo carattere \(a\) (\(\forall a \in A\)),
e dalle sequenti operazioni:
1. la concatenazione \(R\,S\) che rappresenta l'insieme \(\{α\,β \mid α \in R \wedge β \in S\}\),
2. l'unione \(R \mid S\) che corrisponde all'unione insiemistica \(R \cup S\).
3. la stella di Kleene \(R^*\) che rappresenta l'insieme che contiene tutte le possibili iterazioni (eventualmente vuote) ottenibili dagli elementi di \(R\),
Oltre alla definizione formale, vengono usate in diversi strumenti informatici in versioni modificate e in alcuni casi potenziate. Alcuni esempi di operatori aggiuntivi sono:
1. [tt]a+ = aa*[/tt].
2. [tt]a? = (a|ε)[/tt].
3. [tt]a{3,5} = aaa(aa?)?[/tt].
Una descrizione completa richiederebbe troppo tempo ma credo che sia comunque qualcosa di utile da imparare perché presenti veramente ovunque.
Per quanto riguarda la relazione con gli automi a stati finiti, le due rappresentazioni sono equivalenti ed è sempre possibile passare da una rappresentazione a un'altra. Per esempio, il tuo precedente automa sarebbe equivalente a qualcosa come [tt]0*1(0*10*1)*0*[/tt]. Questa espressione significa che le stringhe accettate sono formate da un numero qualsiasi di zeri seguito da un uno, seguita da un'espressione con un numero pari di uno e un numero qualsiasi di zeri e da un numero arbitrario di zeri alla fine. Non è l'unico modo per scrivere l'espressione. In effetti esistono diverse espressioni che accettano lo stesso linguaggio. Qui è descritto un algoritmo per passare da automi a regex. [url=https://web.archive.org/web/20100101190447/http://swtch.com/~rsc/regexp/regexp1.html]Questo è invece un articolo che descrive il passaggio inverso con lo scopo di valutare velocemente una espressione regolare[/url].
NOTA: L'algoritmo che ti ho mandato alla fine crea in effetti la seguente regex per il tuo automa [tt]0*1(0|10*1)*[/tt]... che è diversa da quella che avevo scritto io.
1. l'insieme vuoto \(∅\),
2. l'insieme contenente solo la stringa vuota \(\{ε\}\),
3. l'insieme \(\{a\}\) contenente il solo carattere \(a\) (\(\forall a \in A\)),
e dalle sequenti operazioni:
1. la concatenazione \(R\,S\) che rappresenta l'insieme \(\{α\,β \mid α \in R \wedge β \in S\}\),
2. l'unione \(R \mid S\) che corrisponde all'unione insiemistica \(R \cup S\).
3. la stella di Kleene \(R^*\) che rappresenta l'insieme che contiene tutte le possibili iterazioni (eventualmente vuote) ottenibili dagli elementi di \(R\),
Oltre alla definizione formale, vengono usate in diversi strumenti informatici in versioni modificate e in alcuni casi potenziate. Alcuni esempi di operatori aggiuntivi sono:
1. [tt]a+ = aa*[/tt].
2. [tt]a? = (a|ε)[/tt].
3. [tt]a{3,5} = aaa(aa?)?[/tt].
Una descrizione completa richiederebbe troppo tempo ma credo che sia comunque qualcosa di utile da imparare perché presenti veramente ovunque.
Per quanto riguarda la relazione con gli automi a stati finiti, le due rappresentazioni sono equivalenti ed è sempre possibile passare da una rappresentazione a un'altra. Per esempio, il tuo precedente automa sarebbe equivalente a qualcosa come [tt]0*1(0*10*1)*0*[/tt]. Questa espressione significa che le stringhe accettate sono formate da un numero qualsiasi di zeri seguito da un uno, seguita da un'espressione con un numero pari di uno e un numero qualsiasi di zeri e da un numero arbitrario di zeri alla fine. Non è l'unico modo per scrivere l'espressione. In effetti esistono diverse espressioni che accettano lo stesso linguaggio. Qui è descritto un algoritmo per passare da automi a regex. [url=https://web.archive.org/web/20100101190447/http://swtch.com/~rsc/regexp/regexp1.html]Questo è invece un articolo che descrive il passaggio inverso con lo scopo di valutare velocemente una espressione regolare[/url].
NOTA: L'algoritmo che ti ho mandato alla fine crea in effetti la seguente regex per il tuo automa [tt]0*1(0|10*1)*[/tt]... che è diversa da quella che avevo scritto io.
Buonasera @apatriarca, grazie per la risposta, domani mi metterò a studiare i link che mi hai inviato, penso che torneranno molto utili per la prova e sono molto interessanti. Ti ringrazio per il disturbo che ti sei preso.
Buone feste.
Buone feste.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo