Pumping Lemma

L L

• ∗

∈ ∈

δ([x], a) = [xa] per ogni x Σ e a Σ

M è un DFA che riconosce L, e M ha il minor numero di stati tra tutti

L L

gli FA che riconoscono L.

Spiegazione del Teorema

Il teorema fornisce una costruzione per ottenere il DFA minimo, cioè il DFA con

il numero minimo di stati possibili, che riconosce un dato linguaggio regolare L.

• L: È il linguaggio regolare che stiamo considerando.

• Σ: L’alfabeto da cui sono formate le stringhe del linguaggio.

• M = (Q , Σ, q , δ, A ): Questa è la definizione formale del DFA minimo

L 0 L

che riconosce L.

– Q : L’insieme degli stati del DFA. Ogni stato è una classe di equiv-

L

alenza delle stringhe rispetto alla relazione di indistinguibilità IL. In

altre parole, due stringhe sono nello stesso stato se e solo se non ci

sono differenze nel modo in cui si relazionano a L.

– q = [ε]: Lo stato iniziale del DFA, dove ε rappresenta la stringa

0

vuota. Questo significa che lo stato iniziale corrisponde alla classe di

equivalenza della stringa vuota.

3

– A : Gli stati di accettazione del DFA. Un stato è di accettazione se

L

l’intersezione tra le stringhe in quella classe di equivalenza e L non è

vuota, ovvero ci sono stringhe in quella classe che appartengono a L.

– δ([x], a) = [xa]: La funzione di transizione. Dice che se siamo in

uno stato che rappresenta la classe di equivalenza di una stringa x

e leggiamo il simbolo a, ci spostiamo nello stato che rappresenta la

classe di equivalenza della stringa ottenuta aggiungendo a a x (cioè

xa).

Il DFA Finale

Il DFA finale, M , è costruito in modo tale che ogni stato rappresenti un

L

insieme di stringhe che si comportano allo stesso modo rispetto al linguaggio

L: se una stringa in uno stato è accettata, allora tutte le stringhe in quello

stato sono accettate, e viceversa. Questo garantisce che il DFA sia il più ”com-

patto” possibile, eliminando ridondanze o stati inutili che non contribuiscono a

distinguere tra stringhe che appartengono o meno a L.

In pratica, ciò significa che abbiamo trovato il modo più efficiente per ri-

conoscere se una stringa appartiene o meno a L, utilizzando il minor numero di

distinzioni (stati) necessarie. Questo DFA minimo è unico per ogni linguaggio

regolare L, nel senso che qualsiasi altro DFA che riconosce L avrà almeno tanti

stati quanti M o più.

L

Il ruolo del teorema nel trovare il DFA minimo

Definizione di DFA minimo: Un DFA minimo per un linguaggio L è il

DFA che riconosce L e ha il minor numero di stati possibili tra tutti i DFA

che riconoscono L. L’importanza di avere il minimo numero di stati risiede

nell’efficienza computazionale: meno stati significa, in genere, una macchina

più semplice e veloce da eseguire.

Come il teorema si collega al DFA minimo:

Il teorema fornisce un metodo per costruire un DFA partendo da un concetto

di indistinguibilità tra le stringhe. Questo metodo assicura che ogni stato del

DFA rappresenti un insieme di stringhe che non possono essere distinte l’una

dall’altra rispetto alla loro appartenenza al linguaggio L.

Seguendo le istruzioni del teorema, ogni stato del DFA rappresenta una

classe di equivalenza di stringhe indistinguibili. In pratica, questo significa che

il DFA include solo gli stati strettamente necessari per riconoscere se una stringa

appartiene a L, senza alcuna ridondanza.

La funzione di transizione δ è definita in modo tale da mantenere questa

proprietà di indistinguibilità durante la lettura di una stringa. Ciò garantisce

che il passaggio da uno stato all’altro sia ottimizzato per riconoscere L senza

stati superflui.

Unicità e minimalità:

Il DFA costruito seguendo il teorema è unico per L, nel senso che, per un

dato linguaggio regolare, non esiste un altro DFA con meno stati che possa

4

riconoscerlo. Questo è il significato della minimalità: abbiamo ridotto al minimo

le ”differenziazioni” necessarie per decidere sull’appartenenza di una stringa a

L. La minimalità non implica solo un numero minore di stati, ma anche che

ogni stato è ”essenziale” per la definizione del linguaggio. Non ci sono stati

”inutili”.

In conclusione,

il titolo ”DFA minimo” si riferisce alla costruzione di un automa determin-

istico finito che utilizza il minor numero di stati necessari per riconoscere un

particolare linguaggio regolare, basato sulla relazione di indistinguibilità tra

stringhe.

Il Teorema di Myhill-Nerode

Siamo ora in grado di stabilire il nostro primo criterio generale per la regolarità

dei linguaggi.

Teorema: Myhill-Nerode.

∗

Un linguaggio L in Σ è regolare se e solo se l’insieme delle classi di equiv-

alenza di IL è finito. L è non regolare se e solo se esiste un sottoinsieme infinito

∗

di Σ , in cui ogni due elementi sono distinguibili rispetto a L.

Dimostrazione:

Prima di tutto, notiamo che le due affermazioni dicono esattamente la stessa

cosa. Dire che due stringhe sono distinguibili rispetto a L è lo stesso che dire

che si trovano in due diverse classi di equivalenza di IL. Quindi, da un lato, se

l’insieme delle classi di equivalenza di IL è finito, allora ogni insieme di stringhe

distinguibili a coppie ha al massimo tanti elementi quante sono le classi di equiv-

alenza di IL (e quindi non può esserci alcun insieme infinito di stringhe distin-

guibili a coppie). D’altra parte, se l’insieme di classi di equivalenza è infinito,

allora un insieme composto da una stringa da ciascuna classe di equivalenza è

un insieme infinito di stringhe distinguibili a coppie.

Ora, se l’insieme delle classi di equivalenza di IL è finito, sappiamo dal

teorema precedente (che non abbiamo dimostrato) che esiste un DFA con esat-

tamente quel numero di stati che riconosce L. Al contrario, abbiamo già di-

mostrato che se esiste un insieme di dimensione N di stringhe distinguibili

rispetto a L, allora qualsiasi DFA che lo riconosca deve avere almeno N stati.

Pertanto, se esiste un insieme infinito di stringhe distinguibili a coppie, non può

esistere alcun DFA che riconosca L.

Teorema di Myhill-Nerode: Spiegazione Semplice

Il Teorema di Myhill-Nerode fornisce un criterio molto potente per determinare

se un linguaggio è regolare o meno. Dice sostanzialmente due cose:

1. Regolarità di un linguaggio: Un linguaggio è regolare se e solo se il

numero delle sue classi di equivalenza è finito. Questo significa che, se

5

possiamo raggruppare tutte le stringhe possibili in un numero finito di

”categorie” basate su come si relazionano al linguaggio (cioè, se possono

essere accettate da un automa o meno in modo indistinguibile), allora

possiamo costruire un DFA per riconoscere quel linguaggio. Ogni stato

del DFA corrisponde a una di queste classi di equivalenza.

2. Non regolarità di un linguaggio: Un linguaggio non è regolare se

esiste un insieme infinito di stringhe tali che ogni coppia di stringhe in

questo insieme è distinguibile rispetto al linguaggio. Questo significa che

se possiamo trovare un numero infinito di stringhe che necessitano tutte

di essere separate in classi di equivalenza diverse (perché per ogni cop-

pia esiste almeno una sequenza di simboli che, aggiunta a una stringa la

fa appartenere al linguaggio e aggiunta all’altra no), allora non possiamo

costruire un DFA con un numero finito di stati per riconoscere il linguag-

gio.

Come funziona il teorema nella pratica:

• Se il numero delle classi di equivalenza è finito, possiamo letteralmente

”mappare” queste classi agli stati di un DFA. Ogni stato rappresenta una

classe di equivalenza, e le transizioni tra gli stati seguono le regole di come

le stringhe di una classe possono trasformarsi in stringhe di un’altra classe

aggiungendo più simboli.

• Se troviamo un insieme infinito di stringhe tutte distinguibili l’una dall’altra

rispetto al linguaggio, questo ci dice che qualsiasi tentativo di costruire un

DFA fallirebbe perché avremmo bisogno di un numero infinito di stati per

rappresentare tutte queste classi di equivalenza distinte, il che è impossi-

bile in un DFA.

Conclusione:

Il Teorema di Myhill-Nerode, quindi, ci offre un criterio chiaro e matem-

aticamente solido per determinare se un linguaggio è regolare o meno, basato

sulla struttura e sulla relazione tra le stringhe all’interno del linguaggio stesso.

Questo criterio è estremamente utile non solo per comprendere meglio la natura

dei linguaggi regolari ma anche per applicazioni pratiche in informatica teorica

e progettazione di compilatori.

Esempi: Applicazione del Teorema di Myhill-Nerode

Esempio: 0n1n (il linguaggio non regolare canonico)

n n

{0 |n ≥

Sia L = 1 0}. A questo punto è intuitivamente ovvio che nessun

DFA può riconoscere L, perché dobbiamo ricordare quante volte abbiamo letto

il simbolo 0 finora per poter determinare se vi è lo stesso numero di 1 a seguire.

Per utilizzare il teorema di Myhill-Nerode, consideriamo l’insieme infinito S =

n i j

{0 |n ≥ ̸

0}. Qualsiasi due elementi di S, diciamo 0 e 0 per i = j, possono

i

essere distinti dalla stringa 1 . Pertanto, L non può essere regolare.

6

Esempio: Espressioni algebriche

Sia L il linguaggio di tutte le espressioni algebriche legittime che coinvolgono

l’identificatore A, l’operatore + e le parentesi tonde sinistra e destra. Per di-

mostrare che L non è regolare, possiamo ignorare gran parte della struttura del

j ∈ ⇔

linguaggio. Useremo solo il fatto che (iA) L i = j. Possiamo quindi uti-

{n|n ≥

lizzare esattamente la stessa logica del precedente esempio, con S = 1}.

Qual sarà la stringa che distinguerà gli elementi in questo caso?

{ww|w ∈ {0,

Esempio: 1}}

Questo è l’insieme di tutte le stringhe di lunghezza pari il cui secondo metà è

n

{0 |n ≥

uguale alla prima. Ancora una volta, sia S = 0}. Per trovare una

i j

stringa z che distingua 0 e 0 , dobbiamo essere un po’ più creativi: lasciare

i i i i j

∈ ∈ ̸

z = 1 0 1 servirà, poiché 0 z L, ma 0 z / L per j = i.

Esempi di Applicazione del Teorema di Myhill-

Nerode n n

Esempio 1: 0 1 (il linguaggio non regolare canonico)

n n

{0 | ≥

Linguaggio: L = 1 n 0}. Questo linguaggio contiene stringhe formate

da n zeri seguiti da n uni, dove n può essere qualsiasi numero naturale, inclusi

zero zeri e zero uni.

Perché è non regolare?: Per riconoscere questo linguaggio, un automa dovrebbe

essere capace di ”ricordare” il numero di zeri che ha letto, per assicurarsi che ci

sia lo stesso numero di uni successivamente. Tuttavia, un DFA ha