Automi a stati finiti su parole finite - Riassunto

Fonte: raw/Automi a stati finiti su parole finite.md

Punti chiave

• DFA: automa deterministico definito da stati, alfabeto, funzione di transizione, stato iniziale e stati finali. Per ogni coppia stato-simbolo esiste un unico stato successivo.
• NFA: variante non deterministica in cui la transizione porta a un insieme di stati possibili. Gli epsilon-NFA ammettono anche transizioni spontanee.
• Teoremi di equivalenza:
• ogni NFA puo essere trasformato in un DFA equivalente tramite subset construction;
• ogni epsilon-NFA puo essere trasformato in un NFA;
• per McNaughton-Yamada, automi finiti e linguaggi regolari hanno lo stesso potere espressivo.
• Proprieta di chiusura: i linguaggi regolari sono chiusi per unione, concatenazione, stella di Kleene, complemento e intersezione.
• Decidibilita: vuotezza, infinitudine, equivalenza e inclusione sono problemi decidibili per linguaggi regolari.

Concetti collegati

• Automi finiti deterministici
• Automi finiti non deterministici
• Linguaggi regolari

Teorema di Myhill-Nerode - Riassunto

Fonte: raw/Myhill-Nerode Theorem.md

Punti chiave

• Il teorema caratterizza i linguaggi regolari tramite relazioni di equivalenza invarianti a destra e di indice finito.
• Per un linguaggio $L$, la relazione canonica e': $$x \approx_L y \iff \forall z\; (xz\in L \Leftrightarrow yz\in L)$$
• Un linguaggio e' regolare se e solo se $\approx_L$ ha indice finito.
• Le classi di equivalenza corrispondono agli stati del DFA minimo.
• Il teorema e' utile sia per dimostrare regolarita sia per dimostrare non regolarita.

Concetti estratti

• Teorema di Myhill-Nerode
• Linguaggi regolari

Automi finiti deterministici

Un DFA e' una macchina matematica che riconosce linguaggi regolari su parole finite.

Definizione formale

Un DFA e' una tupla: $$\mathcal{A}=\langle Q,\Sigma,\delta,q_0,F\rangle$$

dove: - $Q$ e' un insieme finito di stati; - $\Sigma$ e' l'alfabeto; - $\delta:Q\times\Sigma\to Q$ e' la funzione di transizione; - $q_0$ e' lo stato iniziale; - $F\subseteq Q$ e' l'insieme degli stati finali.

Accettazione

Una parola e' accettata se, partendo da $q_0$ e leggendo tutti i simboli, l'automa termina in uno stato finale.

Espressivita

I DFA riconoscono esattamente i linguaggi regolari. Sono equivalenti agli NFA sulle parole finite, anche se la determinizzazione puo causare un aumento esponenziale degli stati.

Complemento

Per complementare un DFA bisogna prima renderlo completo, poi scambiare stati finali e non finali.

Collegamenti

• Automi finiti non deterministici
• Linguaggi regolari
• Teorema di Myhill-Nerode

Automi finiti non deterministici

Un NFA e' un automa finito in cui da uno stato e un simbolo possono partire piu transizioni possibili.

Definizione

La funzione di transizione ha forma: $$\Delta:Q\times\Sigma\to 2^Q$$

Una parola e' accettata se esiste almeno una run che termina in uno stato finale.

Equivalenza con DFA

Sulle parole finite, gli NFA hanno lo stesso potere espressivo dei DFA. La subset construction costruisce un DFA i cui stati sono insiemi di stati dell'NFA.

Epsilon-NFA

Gli epsilon-NFA permettono transizioni che non consumano simboli. Anche questi sono equivalenti a NFA e DFA sulle parole finite.

Collegamenti

• Automi finiti deterministici
• Linguaggi regolari

Linguaggi regolari

Un linguaggio regolare e' un linguaggio su parole finite riconoscibile da un DFA o NFA, oppure descrivibile da un'espressione regolare.

Espressioni regolari

I linguaggi regolari possono essere costruiti da linguaggi base tramite unione, concatenazione e stella di Kleene. Intersezione e complemento non aumentano il potere espressivo.

Teorema automi-regex

Per ogni automa finito esiste un'espressione regolare equivalente, e per ogni espressione regolare esiste un automa equivalente.

Proprieta di chiusura

Sono chiusi per: - unione; - concatenazione; - stella di Kleene; - complemento; - intersezione.

Problemi decidibili

Vuotezza, universalita, equivalenza e inclusione sono decidibili; la complessita dipende dalla rappresentazione, ad esempio DFA o NFA.

Collegamenti

• Automi finiti deterministici
• Automi finiti non deterministici
• Teorema di Myhill-Nerode

Teorema di Myhill-Nerode

Il teorema di Myhill-Nerode caratterizza i linguaggi regolari tramite classi di equivalenza di parole.

Relazione canonica

Per un linguaggio $L\subseteq\Sigma^\ast$: $$u\approx_L v \iff \forall t\in\Sigma^\ast\;(ut\in L \Leftrightarrow vt\in L)$$

Due parole sono equivalenti se nessun suffisso futuro puo distinguerle rispetto all'appartenenza a $L$.

Enunciato

Un linguaggio $L$ e' regolare se e solo se $\approx_L$ ha indice finito. Le classi di equivalenza corrispondono agli stati del DFA minimo.

Uso positivo

Per costruire il DFA minimo, si identificano le classi di comportamento futuro.

Uso negativo

Per dimostrare che un linguaggio non e' regolare, si mostra che esistono infinite parole a due a due distinguibili.

Esempio

Per $L=\lbrace w\mid w \text{ termina con } a\rbrace$, bastano due classi: parole che terminano con $a$ e parole che non terminano con $a$.

Collegamenti

• Linguaggi regolari
• Automi finiti deterministici
• Apprendimento di automi

Approfondimento completo settimana 1 - Automi finiti e linguaggi regolari

Questo documento espande il Capitolo 2 della prima settimana di V&V. L'obiettivo non e' solo ricordare definizioni, ma capire il ragionamento dietro: perche gli automi finiti riconoscono esattamente i linguaggi regolari, come si fanno le costruzioni, e come usare Myhill-Nerode per capire quanta memoria serve a un linguaggio.

0. Idea guida: uno stato e' memoria compressa

Un automa finito non ricorda tutta la parola letta. Ricorda solo l'informazione che serve per decidere il futuro.

Esempio: per riconoscere le parole su $\lbrace a,b\rbrace$ che terminano con a, non serve ricordare tutta la parola. Basta ricordare una domanda:

l'ultimo simbolo letto e' a?

Questa domanda ha due risposte, quindi bastano due stati:

Transizioni:

Questo e' il filo rosso di tutto il capitolo: un linguaggio e' regolare quando puo essere deciso con un numero finito di "situazioni future" distinguibili.

1. Operazioni sui linguaggi e chiusura di Kleene

Un alfabeto $\Sigma$ e' un insieme finito di simboli, per esempio $\Sigma = \lbrace a,b\rbrace$. Una parola e' una sequenza finita di simboli. La parola vuota si indica con $\varepsilon$. Un linguaggio e' un insieme di parole, quindi $L \subseteq \Sigma^\ast$.

Operazioni fondamentali:

Esempi:

• Se $L=\lbrace a\rbrace$, allora $L^\ast=\lbrace \varepsilon, a, aa, aaa,\dots\rbrace$.
• Se $L=\lbrace ab\rbrace$, allora $L^\ast=\lbrace \varepsilon, ab, abab, ababab,\dots\rbrace$.
• Se $L=\lbrace a,b\rbrace$, allora $L^\ast$ e' l'insieme di tutte le parole finite su a e b.

Attenzione a una sottigliezza: se $L$ contiene gia $\varepsilon$, allora $L^+$ contiene comunque $\varepsilon$, perche puoi scegliere il blocco $\varepsilon$ come prima ripetizione.

2. DFA: automi deterministici

Un DFA e' una quintupla:

$$ \mathcal{A}=\langle Q,\Sigma,\delta,q_0,F\rangle $$

dove:

• $Q$ e' un insieme finito di stati;
• $\Sigma$ e' l'alfabeto;
• $\delta:Q\times\Sigma\to Q$ e' la funzione di transizione;
• $q_0\in Q$ e' lo stato iniziale;
• $F\subseteq Q$ e' l'insieme degli stati finali.

La funzione $\delta$ e' totale: per ogni stato e per ogni simbolo deve esserci una transizione definita. Se una transizione sembra mancare nel disegno, formalmente va aggiunto uno stato pozzo.

Estensione della transizione

La funzione $\delta$ legge un solo simbolo. Per leggere una parola intera si usa $\hat{\delta}$:

$$ \hat{\delta}(q,\varepsilon)=q $$

$$ \hat{\delta}(q,wa)=\delta(\hat{\delta}(q,w),a) $$

Una parola $w$ e' accettata se:

$$ \hat{\delta}(q_0,w)\in F $$

Esempio: parole con numero pari di a

Linguaggio:

$$ L=\lbrace w\in\lbrace a,b\rbrace^\ast \mid w \text{ contiene un numero pari di } a\rbrace $$

Memoria necessaria: la parita del numero di a viste finora.

Transizioni:

Perche b lascia fermo lo stato? Perche non cambia il numero di a. La parola vuota e' accettata, perche contiene zero a, e zero e' pari.

Esempio: parole che contengono 101

Su $\Sigma=\lbrace 0,1\rbrace$, voglio riconoscere le parole che contengono 101 come sottostringa.

Gli stati ricordano quanto del pattern 101 e' gia stato visto come suffisso utile:

Transizioni:

Il punto delicato e' q1 con input 1: resto in q1, perche l'ultimo simbolo e' ancora un possibile inizio del pattern. Da q2, se leggo 0, torno a q0: il suffisso 100 non contiene un inizio utile di 101.

3. NFA ed epsilon-NFA

Un NFA ha la stessa forma generale di un DFA, ma la transizione restituisce un insieme di stati:

$$ \Delta:Q\times\Sigma\to 2^Q $$

L'idea non e' che l'automa "sceglie a caso"; e' meglio pensarla cosi:

una parola e' accettata se esiste almeno un cammino che, leggendo tutta la parola, arriva in uno stato finale.

Quindi l'accettazione e' esistenziale.

Esempio: parole che finiscono con ab

Un NFA per le parole su $\lbrace a,b\rbrace$ che finiscono con ab puo restare in uno stato iniziale che consuma tutto, e quando vede una a puo "tentare" di iniziare il riconoscimento del suffisso finale.

Stati:

• q0: scansione libera;
• q1: ho scelto una a come possibile penultimo simbolo;
• q2: ho letto ab, stato finale.

Transizioni principali:

Per la parola aabab, l'NFA puo fare molti tentativi. Accetta perche esiste un cammino che sceglie la penultima a e poi legge l'ultimo b.

Un epsilon-NFA aggiunge transizioni $\varepsilon$, cioe' transizioni che non consumano simboli. Servono soprattutto nelle costruzioni da espressioni regolari: unione, concatenazione e stella diventano molto piu facili da costruire.

4. Subset construction: da NFA a DFA

Per ogni NFA esiste un DFA equivalente. La costruzione si chiama subset construction.

Se l'NFA ha stati $Q$, il DFA avra' come stati sottoinsiemi di $Q$. Un sottoinsieme rappresenta tutti gli stati in cui l'NFA potrebbe trovarsi dopo aver letto un certo prefisso.

Formula:

$$ \delta_D(S,a)=\bigcup_{q\in S}\Delta(q,a) $$

dove $S\subseteq Q$.

Gli stati finali del DFA sono i sottoinsiemi che contengono almeno uno stato finale dell'NFA:

$$ F_D=\lbrace S\subseteq Q \mid S\cap F\neq\emptyset\rbrace $$

Esempio svolto di subset construction

NFA:

• stati: $\lbrace q_0,q_1,q_2\rbrace$;
• iniziale: $q_0$;
• finale: $q_2$;
• alfabeto: $\lbrace 0,1\rbrace$;
• transizioni:

$$ \Delta(q_0,0)=\lbrace q_0,q_1\rbrace $$

$$ \Delta(q_0,1)=\lbrace q_0\rbrace $$

$$ \Delta(q_1,1)=\lbrace q_2\rbrace $$

Le transizioni non indicate portano all'insieme vuoto.

Parto dallo stato DFA $\lbrace q_0\rbrace$.

Gli unici stati raggiungibili sono questi tre. Lo stato $\lbrace q_0,q_2\rbrace$ e' finale perche contiene $q_2$.

Che linguaggio riconosce questo automa? Le parole che contengono 01 come sottostringa. Infatti l'NFA "apre" un tentativo quando vede 0 e accetta se subito dopo legge 1.

Con epsilon-transizioni

Se ci sono epsilon-transizioni, bisogna usare la epsilon-closure:

$$ \varepsilon\text{-closure}(S)=\text{insieme degli stati raggiungibili da }S\text{ usando solo }\varepsilon $$

La transizione determinizzata diventa:

$$ \delta_D(S,a)=\varepsilon\text{-closure}\left(\bigcup_{q\in S}\Delta(q,a)\right) $$

e anche lo stato iniziale e' $\varepsilon\text{-closure}(\lbrace q_0\rbrace)$.

5. Equivalenza tra automi finiti ed espressioni regolari

Il teorema di McNaughton-Yamada/Kleene dice:

un linguaggio e' regolare se e solo se e' riconosciuto da un automa finito, equivalentemente se e' descritto da un'espressione regolare.

Ci sono due direzioni.

Da espressione regolare ad automa

Si costruisce un epsilon-NFA per induzione strutturale.

Esempio: per $(a\cup b)^\ast ab$, costruisci prima l'automa per a, quello per b, poi l'unione, poi la stella, poi concateni con a e b. Il risultato riconosce tutte le parole che finiscono con ab.

Da DFA a espressione regolare

Metodo Montanari/Kleene con $R_{i,j}^k$:

• $R_{i,j}^k$ e' il linguaggio delle parole che portano da $q_i$ a $q_j$ usando come stati intermedi solo stati con indice al massimo $k$.
• Se $k=0$, non posso usare stati intermedi.
• Se aumento da $k-1$ a $k$, i percorsi o non passano per $q_k$, oppure passano per $q_k$ e possono fare loop su $q_k$.

Caso base, come negli appunti del docente:

$$ R_{i,j}^0 = \lbrace a\in\Sigma \mid \delta(q_i,a)=q_j\rbrace \quad\text{se } i\neq j $$

$$ R_{i,i}^0 = \lbrace a\in\Sigma \mid \delta(q_i,a)=q_i\rbrace \cup \lbrace\varepsilon\rbrace $$

L'idea e' che, senza stati intermedi, posso usare solo transizioni dirette. Se parto e arrivo nello stesso stato, devo includere anche $\varepsilon$, perche il cammino vuoto porta uno stato in se stesso.

Formula:

$$ R_{i,j}^k = R_{i,j}^{k-1} \cup R_{i,k}^{k-1}(R_{k,k}^{k-1})^\ast R_{k,j}^{k-1} $$

L'espressione finale del linguaggio e':

$$ \bigcup_{f\in F} R_{q_0,f}^{n} $$

Esempio minuscolo da DFA a regex

DFA per parole che terminano con a:

Senza fare tutta la matrice $R_{i,j}^k$, puoi ragionare semanticamente: prima posso leggere qualunque parola su a e b, poi l'ultimo simbolo deve essere a.

Regex:

$$ (a\cup b)^\ast a $$

Questo esempio non sostituisce la dimostrazione generale, ma aiuta a capire cosa la costruzione produce.

Espressioni regolari ristrette e generali

Negli appunti compare anche il corollario:

le espressioni regolari ristrette sono espressive quanto le espressioni regolari generali, e viceversa.

Il punto e' questo. Le espressioni regolari "generali" possono usare direttamente operazioni booleane come complemento e intersezione. Le espressioni regolari "ristrette" usano solo gli operatori costruttivi base, tipicamente unione, concatenazione e stella.

Perche hanno la stessa espressivita?

1. Ogni espressione ristretta e' ovviamente anche una espressione regolare generale.
2. Se hai una espressione generale con booleani, puoi:
3. trasformarla in un automa usando le proprieta di chiusura;
4. poi trasformare quell'automa in una espressione regolare ristretta con il teorema DFA $\rightarrow$ regex.

Quindi gli operatori booleani sono comodi come abbreviazioni, ma non aumentano la classe dei linguaggi descrivibili: resti sempre nei linguaggi regolari.

La terza classe: espressioni star-free

Negli appunti compaiono in realta' tre classi di espressioni regolari:

Le star-free tengono i booleani ma rinunciano alla stella di Kleene, e questa volta l'espressivita' cala davvero: definiscono una sottoclasse propria dei regolari. L'osservazione degli appunti da ricordare e':

la presenza o assenza della stella ti colloca rispettivamente al livello del secondo ordine o del primo ordine.

Cioe': con la stella (piu' i booleani che essa permette di ricostruire) si raggiunge il potere della logica monadica del secondo ordine, senza stella si resta al potere della logica del primo ordine. Questa corrispondenza linguaggi star-free $=$ linguaggi FO-definibili viene ripresa e dimostrata nel Capitolo 6 con S1S e il teorema di Büchi.

6. Proprieta di chiusura dei linguaggi regolari

I linguaggi regolari sono chiusi per molte operazioni. "Chiusi" significa: se parto da linguaggi regolari, il risultato resta regolare.

Complemento: perche il DFA deve essere completo

Se una transizione manca, alcune parole non arrivano in nessuno stato. Ma nel complemento ogni parola deve essere classificata come accettata o rifiutata. Per questo si aggiunge uno stato pozzo.

Esempio: DFA parziale che accetta solo a su alfabeto $\lbrace a,b\rbrace$:

• q0 --a--> q1;
• q1 finale;
• mancano le transizioni su b e dopo q1.

Prima di complementare bisogna completarlo:

• ogni transizione mancante va allo stato pozzo sink;
• sink cicla su a e b.

Poi si scambiano finali e non finali. Nel complemento, sink diventa finale, perche rappresenta tutte le parole che il vecchio automa non accettava.

Prodotto: esempio concreto

Siano:

• $L_1$: parole che terminano con a;
• $L_2$: parole con numero pari di a.

L'intersezione $L_1\cap L_2$ contiene parole che terminano con a e hanno un numero pari di a.

Il prodotto combina le memorie:

• memoria 1: ultimo simbolo e' a oppure no;
• memoria 2: parita del numero di a.

Gli stati sono coppie:

$$ (N,E), (N,O), (A,E), (A,O) $$

Lo stato finale per l'intersezione e' solo $(A,E)$: devo soddisfare entrambe le proprieta. La parola ba arriva in $(A,O)$, quindi non e' accettata; la parola aba arriva in $(A,E)$, quindi e' accettata.

Avvertimento da orale: il prodotto non si generalizza alle parole infinite

Negli appunti il docente segnala esplicitamente che questo punto viene usato per aprire gli orali. La costruzione prodotto con $F_1\times F_2$ funziona sulle parole finite perche' la condizione di accettazione si controlla alla fine: quando la parola termina, entrambe le componenti devono trovarsi in uno stato finale, nello stesso istante.

Sulle parole infinite la condizione di accettazione diventa "passare infinitamente spesso per stati finali" (Büchi, Capitolo 5). E qui il prodotto ingenuo fallisce: puo' succedere che la prima componente passi infinitamente spesso per $F_1$ e la seconda per $F_2$, ma mai nello stesso momento. La parola apparterrebbe all'intersezione, ma nessuno stato di $F_1\times F_2$ viene visitato infinitamente spesso: l'automa prodotto la rifiuta.

La soluzione richiede di rinunciare alla sincronizzazione: si aspetta prima una visita a $F_1$, poi una a $F_2$, poi di nuovo $F_1$, alternando con un contatore a due fasi. E' la costruzione dell'intersezione per automi di Büchi (e la generalizzazione GNBA), trattata nel Capitolo 5 e nella pagina delle dimostrazioni.

7. Problemi decisionali sugli automi

Gli automi finiti sono utili in verifica perche molti problemi diventano visite su grafi finiti.

Vuotezza

Domanda:

$$ L(\mathcal{A})=\emptyset? $$

Algoritmo: fai una DFS/BFS dallo stato iniziale e controlla se raggiungi uno stato finale.

Esempio:

• se nessun finale e' raggiungibile, il linguaggio e' vuoto;
• se trovi anche un solo cammino verso un finale, hai una parola accettata.

Universalita

Domanda:

$$ L(\mathcal{A})=\Sigma^\ast? $$

Algoritmo:

1. rendi il DFA completo;
2. complementa;
3. controlla se il complemento e' vuoto.

Se il complemento e' vuoto, non esiste nessuna parola rifiutata dall'automa originale.

Inclusione

Domanda:

$$ L(\mathcal{A})\subseteq L(\mathcal{B})? $$

Idea:

$$ L(\mathcal{A})\subseteq L(\mathcal{B}) \iff L(\mathcal{A})\cap \overline{L(\mathcal{B})}=\emptyset $$

Traduzione intuitiva:

cerco una parola accettata da $\mathcal{A}$ ma rifiutata da $\mathcal{B}$.

Se non esiste, allora ogni comportamento di $\mathcal{A}$ e' ammesso da $\mathcal{B}$. Questa e' la stessa forma mentale del model checking: cerco un comportamento del sistema che violi la specifica.

Equivalenza

Domanda:

$$ L(\mathcal{A})=L(\mathcal{B})? $$

Puoi verificarla con doppia inclusione, oppure cercando la differenza simmetrica:

$$ (L(\mathcal{A})\cap \overline{L(\mathcal{B})}) \cup (\overline{L(\mathcal{A})}\cap L(\mathcal{B})) $$

Se questa e' vuota, non esiste una parola su cui i due automi differiscono.

Inclusione ed equivalenza sono anche inter-riducibili tra loro, come negli appunti:

$$L(\mathcal{A}_1)\subseteq L(\mathcal{A}_2) \quad\Longleftrightarrow\quad L(\mathcal{A}_1) = L(\mathcal{A}_1)\cap L(\mathcal{A}_2)$$

(la direzione inclusione $\to$ equivalenza usa la chiusura per intersezione; il viceversa e' la doppia inclusione).

Quanto costano questi problemi

Gli appunti annotano con cura le complessita', e la chiave e' sempre la stessa: quali passaggi richiedono di complementare, perche' complementare un NFA costa la determinizzazione (esponenziale), mentre complementare un DFA e' lineare.

La vuotezza non complementa nulla: e' raggiungibilita' su grafo, lineare. L'universalita' invece e' "la validita' degli automi": come la validita' si riduce all'insoddisfacibilita' della negazione, l'universalita' si riduce alla vuotezza del complemento, e il complemento dell'NFA costa esponenziale.

C'e' un'asimmetria da non sbagliare all'orale: nell'inclusione $L(\mathcal{A}_1)\cap\neg L(\mathcal{A}_2)=\emptyset$ si complementa solo $\mathcal{A}_2$. Quindi:

• se $\mathcal{A}_2$ e' un DFA (e $\mathcal{A}_1$ anche NFA), il complemento e' lineare, l'intersezione polinomiale: l'inclusione scende a PTIME;
• se invece e' $\mathcal{A}_1$ a essere deterministico e $\mathcal{A}_2$ resta NFA, non cambia nulla: resta PSPACE-completo. E' l'automa "contenitore" che deve essere deterministico.

Infinitudine

Domanda:

$$ L(\mathcal{A}) \text{ e' infinito?} $$

Un DFA riconosce un linguaggio infinito se e solo se esiste un ciclo:

1. raggiungibile dallo stato iniziale;
2. da cui si puo raggiungere uno stato finale.

Perche? Se posso entrare in un ciclo utile, posso ripeterlo quante volte voglio e ottenere infinite parole accettate.

Esempio:

• Il DFA per (ab)^\ast ha un ciclo utile e riconosce infinite parole: $\varepsilon, ab, abab,\dots$.
• Un DFA che accetta solo ab non ha un ciclo utile verso un finale: il linguaggio e' finito.

Versione "small model" usata spesso negli appunti:

se un DFA con $n$ stati riconosce un linguaggio infinito, allora accetta una parola di lunghezza compresa tra $n$ e $2n$ circa; viceversa, se accetta una parola abbastanza lunga da forzare un ciclo utile, allora il linguaggio e' infinito.

L'intuizione e' sempre la stessa: una parola lunga almeno $n$ attraversa piu stati di quanti ce ne siano disponibili, quindi ripete uno stato. Se la parola e' accettata e il ciclo sta su un cammino verso un finale, puoi pompare quel ciclo e ottenere infinite parole accettate.

8. Small model theory e pumping

Per la vuotezza vale un piccolo teorema molto utile:

Se un DFA con $n$ stati accetta almeno una parola, allora accetta una parola di lunghezza minore di $n$.

Perche? Prendi la parola accettata piu corta. Se avesse lunghezza almeno $n$, durante la lettura attraverserebbe almeno $n+1$ stati. Per il principio dei cassetti, uno stato si ripete. Quindi c'e' un ciclo. Rimuovendo il ciclo ottieni una parola piu corta ancora accettata: contraddizione.

Questa e' la stessa intuizione del pumping lemma:

• se una parola e' abbastanza lunga, in un automa finito deve ripetere uno stato;
• ripetere uno stato significa avere un ciclo;
• un ciclo puo essere pompato o rimosso.

Attenzione: il pumping lemma serve spesso per dimostrare non regolarita, ma Myhill-Nerode e' piu preciso per capire il numero di stati necessari.

9. Myhill-Nerode: la memoria minima di un linguaggio

Per un linguaggio $L\subseteq\Sigma^\ast$, definisci:

$$ x\sim_L y \iff \forall z\in\Sigma^\ast,\ xz\in L \Leftrightarrow yz\in L $$

Due prefissi sono equivalenti se nessun suffisso futuro li distingue.

Tre idee da tenere insieme

Teorema:

$L$ e' regolare se e solo se $\sim_L$ ha indice finito. Il numero di classi e' il numero di stati del DFA minimo.

Relazione dell'automa e relazione del linguaggio

Per un DFA $\mathcal{A}$ puoi definire:

$$ x\sim_\mathcal{A}y \iff \hat{\delta}(q_0,x)=\hat{\delta}(q_0,y) $$

Questa relazione dice: due parole sono equivalenti se portano nello stesso stato dell'automa. Siccome gli stati sono finiti, le classi sono finite.

La relazione $\sim_L$ e' piu canonica: non dipende da un automa scelto, ma solo dal linguaggio. Il DFA minimo e' proprio quello che identifica esattamente le classi di $\sim_L$.

Prova delle tre implicazioni, in forma orale

Negli appunti il teorema viene presentato tramite tre affermazioni equivalenti:

1. $L$ e' regolare.
2. $L$ e' unione di classi di una relazione invariante a destra di indice finito.
3. $\sim_L$ ha indice finito.

Da 1 a 2. Se $L$ e' regolare, esiste un DFA $\mathcal{A}$ che lo riconosce. Definisci $\sim_\mathcal{A}$ dicendo che due parole sono equivalenti se portano dallo stato iniziale allo stesso stato. Questa relazione e' invariante a destra: se due parole arrivano nello stesso stato, aggiungere lo stesso suffisso le fara' muovere nello stesso modo. Ha indice finito perche il DFA ha finiti stati. Inoltre $L$ e' l'unione delle classi che portano a stati finali.

Da 2 a 3. Se $L$ e' unione di classi di una relazione $\sim$ invariante a destra e di indice finito, allora $\sim$ e' un raffinamento sufficiente per distinguere appartenenza e non appartenenza a $L$. La relazione canonica $\sim_L$ puo solo fondere classi che hanno lo stesso comportamento rispetto a tutti i suffissi. Quindi $\sim_L$ non ha piu classi di $\sim$, e resta di indice finito.

Da 3 a 1. Se $\sim_L$ ha indice finito, costruisci un DFA:

• stati = classi di equivalenza di $\sim_L$;
• stato iniziale = classe di $\varepsilon$;
• transizione da $[x]$ con simbolo $a$ = classe di $xa$;
• stati finali = classi $[x]$ tali che $x\in L$.

La transizione e' ben definita proprio per l'invarianza a destra. Questo DFA riconosce $L$, quindi $L$ e' regolare.

Il punto delicato della prova 3 → 1: perche' $\delta$ e' ben definita

Negli appunti questo passaggio occupa due pagine, perche' e' il punto che un esaminatore controlla. La definizione

$$\delta([u]_{\sim_L}, a) := [u\cdot a]_{\sim_L}$$

usa un rappresentante $u$ della classe. Ma una classe ha tanti rappresentanti: se $[u] = [v]$, chi garantisce che $[ua] = [va]$? Per un'equivalenza arbitraria potrebbe succedere che $u\sim v$ ma $ua\not\sim va$: allora $\delta(q,a)$ varrebbe contemporaneamente $q'$ e $q''$ diversi, e non sarebbe una funzione.

La garanzia e' che $\sim_L$ e' invariante a destra, e questo va dimostrato (non e' nella definizione). Devo provare:

$$u\sim_L v \implies \forall t',\ ut'\sim_L vt'.$$

Spacchettando la definizione, $ut'\sim_L vt'$ significa: per ogni $t''$, $ut't''\in L \iff vt't''\in L$. Il trucco degli appunti: dato un $t''$ arbitrario, poni $t = t'\cdot t''$. Siccome $u\sim_L v$ vale per ogni suffisso $t$, vale in particolare per questo $t$ composto:

$$ut = u t' t'' \in L \iff v t' t'' = vt \in L.$$

Che e' esattamente cio' che serviva. Quindi $\sim_L$ e' invariante a destra, $\delta$ e' ben definita, e l'automa e' un DFA legittimo.

Esempio guidato dagli appunti: $L = (ab)^\ast$

Verifichiamo le classi di $\sim_L$ come fa il docente.

• $ab \sim_L abab$: per ogni $t$, $ab\cdot t\in L \iff t = abab\ldots ab \iff abab\cdot t\in L$.
• $a \not\sim_L ab$: basta $t = b$, perche' $a\cdot b = ab \in L$ ma $ab\cdot b = abb \notin L$.
• $aba \sim_L a$: entrambe richiedono $t$ della forma $b\cdot(ab)^\ast$. Nota che i suffissi che funzionano non appartengono a $L$, e non e' un problema: la quantificazione e' su tutti i $t$, conta solo che le risposte coincidano.

Le classi sono tre:

E $L$ e' unione di classi: $L = [\varepsilon]_{\sim_L}$. Osservazione in piu' degli appunti: il linguaggio $L' = (ab)^\ast a \cup b(a+b)^\ast = [a]\cup[b]$ induce la stessa relazione di equivalenza, $\sim_L = \sim_{L'}$. Linguaggi diversi possono condividere la stessa partizione di $A^\ast$; cambiano solo le classi marcate come finali.

Esempio positivo: parole che terminano con a

Linguaggio:

$$ L=\lbrace w\in\lbrace a,b\rbrace^\ast \mid w \text{ termina con } a\rbrace $$

Ci sono due classi:

Il suffisso vuoto $\varepsilon$ distingue le due classi: una parola in A e' gia nel linguaggio, una in N no.

Non servono piu classi: se due parole terminano entrambe con a, qualsiasi suffisso comune fara' dipendere il risultato solo dal suffisso; lo stesso vale per due parole che non terminano con a.

Conclusione: il DFA minimo ha due stati.

Esempio positivo: lunghezza multipla di 3

Linguaggio:

$$ L=\lbrace w\in\lbrace a,b\rbrace^\ast \mid |w| \equiv 0 \pmod 3\rbrace $$

Le classi sono tre, in base alla lunghezza modulo 3:

Per distinguere classe 0 e classe 1, usa un suffisso di lunghezza 0 oppure 2 a seconda del confronto. In generale ogni resto modulo 3 ha un futuro diverso per tornare a lunghezza multipla di 3.

Conclusione: il DFA minimo ha tre stati.

Esempio negativo: $a^n b^n$

Linguaggio:

$$ L=\lbrace a^n b^n \mid n\ge 0\rbrace $$

Considera i prefissi:

$$ \varepsilon, a, aa, aaa,\dots $$

Sono tutti distinguibili. Se prendo $a^i$ e $a^j$ con $i<j$, uso il suffisso $b^i$.

Allora:

$$ a^i b^i \in L $$

ma:

$$ a^j b^i \notin L $$

Quindi $a^i$ e $a^j$ non sono equivalenti. Poiche ci sono infiniti prefissi distinguibili, $\sim_L$ ha indice infinito. Dunque il linguaggio non e' regolare.

Esempio negativo: palindromi

Linguaggio:

$$ PAL=\lbrace w\in\lbrace a,b\rbrace^\ast \mid w=w^R\rbrace $$

Considera i prefissi:

$$ a,\ aa,\ aaa,\ aaaa,\dots $$

Per distinguere $a^i$ e $a^j$ con $i<j$, usa il suffisso $ba^i$.

Allora:

$$ a^i b a^i $$

e' palindroma, mentre:

$$ a^j b a^i $$

non e' palindroma se $j\neq i$. Anche qui hai infinite classi distinguibili, quindi il linguaggio dei palindromi non e' regolare.

Metodo operativo per Myhill-Nerode

Quando devi usare Myhill-Nerode all'orale:

1. Scrivi la relazione: due prefissi sono uguali se tutti i suffissi futuri li trattano allo stesso modo.
2. Per dimostrare regolarita, identifica un numero finito di classi.
3. Dai il significato di ogni classe.
4. Per dimostrare non regolarita, scegli una famiglia infinita di prefissi.
5. Per ogni coppia diversa, trova un suffisso che accetta una parola e rifiuta l'altra.

La frase chiave e':

ho trovato infiniti prefissi a due a due distinguibili, quindi servirebbero infiniti stati, quindi il linguaggio non e' regolare.

10. Collegamento con V&V e model checking

La forma dell'inclusione:

$$ L(\text{sistema})\subseteq L(\text{specifica}) $$

e' gia' una versione astratta del model checking. Se voglio verificare che tutti i comportamenti del sistema rispettino una specifica, cerco:

$$ L(\text{sistema})\cap \overline{L(\text{specifica})} $$

Se l'intersezione e' vuota, non esiste un comportamento cattivo. Se non e' vuota, una parola accettata dall'intersezione e' un controesempio.

Nel caso delle parole finite tutto si risolve con automi finiti classici. Piu avanti, per sistemi reattivi e comportamenti infiniti, la stessa idea ricompare con automi di Buchi, LTL e model checking automata-theoretic.

11. Mini-esercizi svolti

Esercizio 1: complementa un DFA

Linguaggio: parole su $\lbrace 0,1\rbrace$ con almeno un 1.

DFA:

E' gia completo. Complemento:

Il complemento riconosce le parole con nessun 1, cioe' $0^\ast$.

Esercizio 2: inclusione

Sia:

• $L_1 =$ parole che finiscono con ab;
• $L_2 =$ parole che contengono ab.

Vale $L_1\subseteq L_2$? Si. Ogni parola che finisce con ab contiene certamente ab.

Come lo controlla l'automa? Cerca una parola in:

$$ L_1\cap \overline{L_2} $$

cioe' una parola che finisce con ab ma non contiene ab. Impossibile, quindi il linguaggio e' vuoto e l'inclusione vale.

Esercizio 3: distinguere due prefissi

Linguaggio:

$$ L=\lbrace w \mid w \text{ contiene } 101\rbrace $$

I prefissi 1 e 10 sono distinguibili? Si. Usa il suffisso 1.

• 1 + 1 = 11, non contiene 101;
• 10 + 1 = 101, contiene 101.

Quindi 1 \not\sim_L 10 e nel DFA minimo devono stare in stati diversi.

12. Due richiami utili: lemma di Arden e minimizzazione

Il capitolo e' gia' centrato su DFA, NFA, regex e Myhill-Nerode. Aggiungo due richiami che aiutano a collegare meglio gli esercizi.

Lemma di Arden

Il lemma di Arden e' uno strumento per risolvere equazioni sui linguaggi.

La forma tipica e':

$$X = A X \cup B.$$

Se $\varepsilon\notin A$, allora la soluzione minima e':

$$X=A^\ast B.$$

Intuizione:

• per ottenere una parola in $X$, posso ripetere un blocco di $A$ zero o piu' volte;
• poi devo uscire con un blocco di $B$.

Questo compare quando si trasforma un automa in espressione regolare tramite sistemi di equazioni: ogni stato genera un'equazione per il linguaggio delle parole che portano da quello stato a un finale.

Esempio:

$$X = aX \cup b.$$

La soluzione e':

$$X=a^\ast b.$$

Perche' posso leggere zero o piu' a restando nel comportamento ricorsivo, e poi chiudere con b.

Minimizzazione del DFA

Myhill-Nerode dice che il DFA minimo ha uno stato per ogni classe della relazione:

$$u\sim_L v \quad\Longleftrightarrow\quad \forall z,\ uz\in L\iff vz\in L.$$

Questa e' la caratterizzazione teorica.

Operativamente, la minimizzazione di un DFA parte da una partizione degli stati:

• finali;
• non finali.

Poi raffina la partizione distinguendo stati che, leggendo una stessa lettera, vanno in blocchi diversi.

Due stati possono essere fusi solo se nessun suffisso li distingue.

Quindi:

• Myhill-Nerode ragiona sui prefissi/parole;
• la minimizzazione del DFA ragiona sugli stati;
• le due visioni coincidono per il DFA minimo.

Questo richiamo e' importante anche per il capitolo 3: L* cerca di imparare proprio queste classi minime usando membership ed equivalence query.

13. Quiz interattivo per l'autovalutazione

14. Fonti usate

• Appunti locali: raw/Automi a stati finiti su parole finite.md, raw/Myhill-Nerode Theorem.md, sources/Automi_stati_finiti_parole_finite_Summary.md, sources/Myhill-Nerode Theorem_Summary.md.
• Baier e Katoen, Principles of Model Checking, MIT Press: riferimento generale per il collegamento tra linguaggi, automi e verifica. https://mitpress.mit.edu/9780262026499/principles-of-model-checking/