[C] Automi a stati finiti

[spider-net]

Vorrei anche aggiungere Introduction to Automata Theory, Languages, and Computation dei mostri sacri Hopcroft e Ullman.

Ovviamente si sottintende la terza edizione, o al limite la seconda, ambedue con l'aggiunta agli autori del terzo moschettiere Motwani.

L'edizione originale degli anni Settanta, e il suo predecessore del 1969 "Formal Languages and Their Relation to Automata" degli stessi autori, oggi risultano probabilmente illeggibili al laureato quadratico medio italiano ed a quasi tutti i practitioners.

Certo, avrei dovuto specificare che intendevo la terza edizione, io in realtà ho la seconda edizione che è altrettanto buona.

[gila75]

Io per il momento sono alle basi, credo che testi del genere siano fuori portata al momento.
Ho una domanda: con un automa si potrebbe scrivere un programma che riconosca le parentesi ? (avevo provato con lo stack)
ma vorrei esercitarmi:
[( espressione )] ok

[spider-net]

Non voglio entrare nei dettagli perché non è questa la sede, però vorrei dare un paio di definizioni per impostare il contesto. Le definizioni sono state semplificate volutamente.

Allora un automa a stati finiti (chiamiamo M) riconosce o accetta un linguaggio (chiamiamolo L). Un linguaggio L è un insieme di stringhe di simboli di un alfabeto Σ.

Nel tuo caso l'alfabeto Σ è l'insieme dei simboli di parentesi, quindi Σ = { ( , ) , [ , ] }. Quindi il nostro automa M dovrebbe accettare un linguaggio L formato da tutte le possibili stringhe di Σ, che siano anche "bilanciate", nel senso che dato un simbolo "(" , esiste da qualche parte la sua controparte ")".
Ad esempio la stringa "[(()()())]".

Ebbene questo è un'esempio di linguaggio di Dyck, e non esiste nessun automa in grado di accettare tale linguaggio, perché gli automi non sono in grado di contare, quindi servirebbe uno stato per ogni parentesi aperta e questo richiederebbe un numero di stati unbounded (illimitato).

Infatti il linguaggio di Dyck non è un linguaggio regolare. Un linguaggio L è regolare se è accettato da un qualche DFA (Deterministic Finite Automaton = automa a stati finiti), ovvero se esiste M tale che L = L(M).

Se ti vuoi esercitare prova a costruire l'automa che accetta i seguenti linguaggi. Σ = {0, 1}:

• L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 2;
• L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 4;
• L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 5.

[gila75]

(" , esiste da qualche parte la sua controparte ")".
Ad esempio la stringa "[(()()())]".

Infatti quello intendevo

Ebbene questo è un'esempio di linguaggio di Dyck, e non esiste nessun automa in grado di accettare tale linguaggio, perché gli automi non sono in grado di contare

Ok. Ma un "pochino" sono in grado di contare. Se per esempio voglio una stringa che accetti 5 'a' consecutive lo posso fare.
@Spider, sto parlando dall'alto della mia ignoranza in merito
Forse contare indefinitivamente non sono in grado di farlo, dovrei leggere i testi "sacri", ma se lo dici vuol dire che è così.

Se ti vuoi esercitare prova a costruire l'automa che accetta i seguenti linguaggi. Σ = {0, 1}:
L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 2;
L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 4;
L'insieme di tutte le stringhe tali che, se interpretate come numero binario, sono divisibili per 5.

Ci proverò.
Se hai voglia e tempo, dai un'occhiata ai codici che ho postato.
Odio sollecitare, ma sono rimasti in sospeso e non so se sono corretti. Nel caso grazie, e grazie delle precisazioni fatte

[spider-net]

Ok. Ma un "pochino" sono in grado di contare. Se per esempio voglio una stringa che accetti 5 'a' consecutive lo posso fare.
@Spider, sto parlando dall'alto della mia ignoranza in merito
Forse contare indefinitivamente non sono in grado di farlo, dovrei leggere i testi "sacri", ma se lo dici vuol dire che è così.

Certo per cinque simboli, si può anche fare. Ma quando hai una stringa di anche 100 simboli, l'automa inizia ad esplodere. Poi non dimentichiamoci che le parentesi devono essere bilanciate.

Un'altro esempio di linguaggio non regolare e quindi non riconoscibile da un'automa, è quello che consiste nelle stringhe nella forma (a^n)(b^n). Ad esempio se n = 5: "aaaaabbbbb". Formalmente dimostrabile che non è regolare usando il Pumping Lemma. Se n fosse limitato superiormente, cioè n <= X, X numero naturale allora sarebbe possibile, ma n può essere un numero arbitrariamente grande. Ad esempio, ok faccio un'automa che riconosce stringe di 100.000 a e b consecutive, ora mi arriva una di 200.000, e ora che faccio, aggiungo altri stati, ma ora arriva in input una stringa di 1Mln di a e b consecutive e così via.

Ci proverò.
Se hai voglia e tempo, dai un'occhiata ai codici che ho postato.
Odio sollecitare, ma sono rimasti in sospeso e non so se sono corretti. Nel caso grazie, e grazie delle precisazioni fatte

Darò un'occhiata

[Claudio_F]

sono rimasti in sospeso e non so se sono corretti

In questo periodo non ho tempo/forze

Per quanto riguarda il discorso contare le parentesi, vale sempre il discorso che un automa riconoscitore come quelli trattati fin qui è un caso particolare di automa stateless (ha solo il suo stato interno e nient'altro), ma un altro tipo di macchina a stati può contare ed elaborare dati quanto le pare (è quello che fa il normalizzatore di numeri di qualche post fa che costruisce una nuova stringa pezzo per pezzo mano a mano che "entrano" i caratteri da analizzare).

[spider-net]

Per quanto riguarda il discorso contare le parentesi, vale sempre il discorso che un automa riconoscitore come quelli trattati fin qui è un caso particolare di automa stateless (ha solo il suo stato interno e nient'altro), ma un altro tipo di macchina a stati può contare ed elaborare dati quanto le pare (è quello che fa il normalizzatore di numeri di qualche post fa che costruisce una nuova stringa pezzo per pezzo mano a mano che "entrano" i caratteri da analizzare).

Una macchina di Turing con due nastri lo riconoscerebbe. Se non erro basterebbe una macchina di Turing con un solo nastro, ma non vorrei scommeterci.
Ma qui si parlava di DFA/NFA, quindi non l'ho citata

[M_A_W_ 1968]

Il linguaggio di Dyck (con relativo problema della parentesizzazione) è un tipico esempio di linguaggio context-free. Come tale, è decidibile tramite un semplice automa a pila non deterministico. Si veda anche la gerarchia di Chomsky al riguardo.

[gila75]

In questo periodo non ho tempo/forze

Ci mancherebbe Claudio, non devi mica timbrare Ero solo curioso di sapere se la mia variante al tuo codice era valida...con calma...

Il linguaggio di Dyck...

Mi documento

EDIT:
se qualcuna ha voglia\tempo, potrebbe postare un grafico d'esempio di un'automa a pila?
In rete ho visto, ma sono esempi un po' complicati.
Nel caso grazie...nel caso contrario grazie lo stesso

[M_A_W_ 1968]

Purtroppo ho sempre pochissimo tempo. Aggiungo solo che l'algoritmo di Rohl-Ganapathi-Rama del quale ho trattato recentemente in un lungo articolo allegato al mio blog (inutile che posti di nuovo il link) è in grado di generare tranquillamente anche stringhe di Dyck valide, previa una banale piccola modifica illustrata nell'articolo originale a pagg. 14-15.
L'implementazione, a partire dai sorgenti esemplificativi da me proposti, è lasciata come esercizio per tutti i lettori interessati.

[spider-net]

Grazie MAW, veramente interessante.

[gila75]

Bhè...grazie MAW... ma inutile dire, come ben saprai,che per me quell'articolo è ben oltre...diciamo qualche annetto luce.
Proverò a cercare ancora in rete la spiegazione\grafico di un'automa a pila.
Credo però che prima di avventurarmi negli automi a pila, dovrei studiare un po' gli automi non deterministici.
A riguardo non ho capito però se sono solo un concetto teorico. Dobbiamo sempre convertire in deterministico per darlo in pasto al
calcolatore giusto?
Per esempio come faccio nel grafico sotto a determinare l'uscita dello stato q se non ha archi che si richiudono come nei dfa?
presumo vada convertito

[spider-net]

Per implementare un NFA ci sono due possibilità:

1) vediamo l'automa come un albero ed usiamo la tecnica di backtracking finché non raggiungiamo uno stato di accettazione;
2) come computazione di insiemi di stati. In pratica, dato uno stato q generico ed un simbolo s, da q posso finire (potenzialmente) non in uno stato ma in un insieme di stati. Posso quindi costruire una matrice di transazioni.

Ora sono al cellulare quindi non riesco a portarti un esempio, ma alla pausa pranzo posso buttare giù qualcosa e spiegare un po' più in dettaglio.

Nota inoltre che la conversione da NFA a DFA comporta l'aumento del numero di stati. Se un NFA contiene n stati il corrispettivo DFA può contenere fino a 2^n stati.

Edit: faccio una precisazione. Gli NFA possono essere implementati in software, ma in hardware si implementano i DFA minimi.

[gila75]

vediamo l'automa come un albero ed usiamo la tecnica di backtracking finché non raggiungiamo uno stato di accettazione;

Cavoli con gli alberi sono un po' a terra, li stavo guardando ,ma o automi o alberi studio

posso finire (potenzialmente) non in uno stato ma in un insieme di stati.

Teoricamente (se non erro) un NFA potrebbe anche non aver alcun risultato giusto?

Nota inoltre che la conversione da NFA a DFA comporta l'aumento del numero di stati. Se un NFA contiene n stati il corrispettivo DFA può contenere fino a 2^n stati.

Si quello ho visto. In un esempio un NFA aveva pochissimi stati, nel corrispettivo DFA era molti di più...roba tipo triplo o quadruplo.

Edit: faccio una precisazione. Gli NFA possono essere implementati in software, ma in hardware si implementano i DFA minimi.

Infatti quello è il mio sospetto: è un'astrazione, a conti fatti a una macchina, o un integrato ,un flip-flop che sia...devi dirgli cosa fare no?
ma allora, via software non sono obbligato a convertire?
come potrei fare per il grafico che ho postato con una normale tabella di transizioni?
lo stato q termina come non essendoci nessun cappio?
Forse gli nfa semplificano il ragionamento e poi però devono diventare dfa...mi fermo, rischio di spararle grosse
Grazie mille @spider

[spider-net]

Teoricamente (se non erro) un NFA potrebbe anche non aver alcun risultato giusto?

Assumiamo che l'alfabeto sia {0, 1}.
Un NFA è un'automa a stati finiti non deterministico, questo vuol dire che dato uno stato q (generico), da q posso "uscire" verso un'altro stato (non necessariamente diverso da q) con il simbolo 0, con il simbolo 1, oppure con uno solo dei simboli, o anche con nessun simbolo (quindi non esco)
Ad esempio:


Da q0, con il simbolo 1 vado a q3, ma con 0 vado sia a q1 che a q2. Da q1 esco solo con il simbolo 0, mentre da q3 e q4 non esco. Rimango su quello stato anche se "mi arrivano" altri simboli.

Infatti quello è il mio sospetto: è un'astrazione, a conti fatti a una macchina, o un integrato ,un flip-flop che sia...devi dirgli cosa fare no?

Perché l'hardware agisce in modo deterministico. Gli NFA sono usati per semplificare il ragionamento. Possono essere sempre convertiti in DFA e da DFA in DFA minimi.

come potrei fare per il grafico che ho postato con una normale tabella di transizioni?

Per il tuo grafo:


Come ho detto prima, dal generico stato q con un simbolo si "va" ad un insieme di stati, nel caso in cui si vada ad un solo stato, l'insieme di stati di arrivo è caratterizzato dalla presenza di un solo stato (insieme singoletto). Da qui si capisce che il DFA è un caso particolare di NFA. ø è l'insieme vuoto.

Oppure chiedevi come convertirlo in DFA?


Tornando alle due implementazioni, prendiamo il grafo che ho postato sopra.

Metodo 1: backtracking
Assumiamo mi arrivi in input la stringa "00". q0 è lo stato iniziale, bene. Da q0 con il simbolo "0" posso andare a q1 o a q2. Per esempio scegliamo di andare a q1, ora da q1, con "0" andiamo solo verso "q3"; q3 non è uno stato di accettazione o finale, quindi torniamo alla scelta precedente: q1. Non ci sono altri modi per uscire da q1, andiamo ancora indietro: q0.
Bene, da q0, con "0" ora andiamo a q2, da q2 con "0" andiamo a q4, q4 è uno stato finale. OK stringa riconosciuta.

Metodo 2: computazione di un insieme di stati
Allora partiamo notando che q4, è lo stato finale di accettazione. Quindi una stringa è accettata dall'automa se alla fine arriviamo allo stato q4.
Iniziamo la computazione (parallela): mi arriva in input la stringa "00" (andrebbe bene anche "000", "001", "0000", ...). Da q0 con il simbolo "0" finisco nell'insieme di stati {q1, q2}. Nota che finisco contemporaneamente in q1 e in q2. Ora da q1 con "0", finisco in {q2}, da q2 con "0" arrivo a {q4}, q4 è lo stato finale. OK stringa riconosciuta.
Oppure in modo parallelo ho che: da q0, con "0" arrivo a {q1, q2}, da q1 e da q2 con "0" arrivo all'insieme di stati {q3, q4}. L'insieme contiene q4, quindi la stringa è accettata.
Matrice di transizioni:


Ora se hai capito, che grafo genera questa tabella?



Ho cercato di spiegare il tutto in modo molto informale, senza dover introdurre pesanti notazioni e definizioni / teoremi, ...

[gila75]

Molte grazie @spider!!!
Non facilissima la cosa...devo leggere bene e assimilare

Ora se hai capito, che grafo genera questa tabella?

Dammi un po' di tempo

[gila75]

Il metodo del backtracking, presumo richieda o uno stack, o la ricorsione giusto?
L'avevo usato per implementare l'algoritmo deep first serarch (DFS), per la generazione del percorso di un labirinto, e per tornare
indietro avevo usato uno stack.
Il secondo metodo lo devo ancora capire bene.
Credo che la tabella di transizione degli automi deterministici, centri poco nulla con gli nfa.
Purtroppo sta mattina non ho molto tempo.
Appena ho tempo cerco di fare un programma in C che risolva un nfa anche basilare.
Per capire devo iniziare a vedere come funziona il tutto.
Comunque ho provato a mettere giù il grafico che mi hai proposto in base alla tabella.
credo sia così
Purtroppo però non mi è ben chiaro lo stato accettato.

[spider-net]

Il metodo del backtracking, presumo richieda o uno stack, o la ricorsione giusto?
L'avevo usato per implementare l'algoritmo deep first serarch (DFS), per la generazione del percorso di un labirinto, e per tornare
indietro avevo usato uno stack.

Esattamente, stesso principio.

Il secondo metodo lo devo ancora capire bene.
Credo che la tabella di transizione degli automi deterministici, centri poco nulla con gli nfa.

Dato che un DFA è un caso particolare di NFA (a sua volta l'NFA è un caso particolare di ε-NFA, lo cito soltanto), le tabelle di transizione solo molto imparentate tra di loro. Purtroppo una spiegazione testuale, senza l'introduzione degli opportuni formalismi, perde un po' in efficacia, e poi non sono molto portato per l'insegnamento

Purtroppo sta mattina non ho molto tempo.
Appena ho tempo cerco di fare un programma in C che risolva un nfa anche basilare.
Per capire devo iniziare a vedere come funziona il tutto.

Ti abbozzo una traccia di possibile implementazione di NFA in pseudo-pseudo-pseudocodice:
assumiamo di avere già memorizzato la tabella delle transizioni in una qualche struttura dati.

Codice: Seleziona tutto

Q = [1, 0, 0, 0, ..., 0]
while (input != NULL) {
    c = first(input) // estraggo il primo simbolo dalla stringa in input
    per ogni stato "ad 1" nel vettore Q, simulo la computazione seguendo la matrice delle transizioni
    e imposto i nuovi stati (quelli a cui arrivo) ad 1. Impostando a 0, gli stati "vecchi".
    input = other(input) // assegno ad input la stringa input escluso il primo carattere.
}

Dove Q è un vettore di booleani (o di 0 - 1) lungo tanto quanti sono gli stati. Q[0] è q0, Q[1] è q1 e così via. Q = 1 se mi trovo attualmente sullo stato i. Quindi all'inizio solo q0 sarà 1.

Comunque ho provato a mettere giù il grafico che mi hai proposto in base alla tabella.
credo sia così
Purtroppo però non mi è ben chiaro lo stato accettato.

Colpa mia, non ti ho detto che lo stato di accettazione è q2.

[gila75]

Perfetto,grazie.
Comunque il grafico è giusto?
Domani provo a vedere con calma,magari tento il backtracking,la ricorsione mi è un po' indigesta.
Traendo le somme:gli nfa riducono gli stati e quindi più facile (umanamente) ragionare.
Poi volendo se si è nell'ambito software si possono risolvere così o convertirli in dfa
Con algoritmi apposta (ora è prematuro).
Però deduco sia più facile disegnare un grafico per un nfa
Un compito anche banale per un dfa può richiedere molti stati ed archi.
Confermi la corretteza di quello che ho detto?

[spider-net]

Perfetto,grazie.
Comunque il grafico è giusto?

E' giusto.

Domani provo a vedere con calma,magari tento il backtracking,la ricorsione mi è un po' indigesta.
Traendo le somme:gli nfa riducono gli stati e quindi più facile (umanamente) ragionare.
Poi volendo se si è nell'ambito software si possono risolvere così o convertirli in dfa
Con algoritmi apposta (ora è prematuro).
Però deduco sia più facile disegnare un grafico per un nfa
Un compito anche banale per un dfa può richiedere molti stati ed archi.
Confermi la corretteza di quello che ho detto?

Confermo.