Proprietà degli automi a stati finiti

Lezione precedente: Automa a stati finiti deterministico

Corso: Materia:Informatica Teorica

Prossima lezione: Minimizzazione degli stati di un automa

Obiettivo della lezione

Fino a questo punto ci siamo occupati di introdurre tre formalismi nell'ambito degli automi a stati finiti senza badare alle proprietà di cui essi siano dotati; in particolare, l'introduzione del modello computazionale del riconoscitore a stati finiti ha portato il concetto di accettazione; a sua volta l'idea di accettazione ha consentito di gettare un ponte tra la teoria degli automi e quella dei linguaggi formali.

Questo aspetto fa nascere spontaneamente alcuni interrogativi: sarà vero che ad ogni accettore è associato un linguaggio formale? Sarà vero che per ogni linguaggio formale definito su un alfabeto esiste un accettore a stati finiti in grado di riconoscerlo?

L'obiettivo di questa lezione è quello di trovare risposta a quante più domande possibili, adottando uno stile formale e rigoroso che consenta di dimostrare con assoluta certezza le congetture formulate.

Il linguaggio vuoto

Indaghiamo anzitutto la possibilità che un automa a stati finiti riconosca il linguaggio vuoto; in altre parole, ci chiediamo se esiste un automa riconoscitore che non accetta nessuna stringa.

Questa situazione è compatibile con la struttura dell'automa accettore in almeno due sensi: è anzitutto possibile che l'insieme degli stati di accettazione sia vuoto, ma se anche così non fosse gli stati di accettazione potrebbero non essere raggiungibili, condizione che si verifica quando nessuna transizione porta ad uno stato finale.

Per aiutare l'immaginazione riportiamo di seguito i diagrammi a stati di due accettori $A=(\left\{q_{0},q_{1},q_{2}\right\},\left\{0,1\right\},q_{1},\emptyset )$ e $B=(\left\{q_{0},q_{1},q_{2},q_{3}\right\},\left\{a,b\right\},q_{0},\left\{q_{1},q_{3}\right\})$ che hanno il linguaggio vuoto come linguaggio macchina.

Diagramma a stati dell'automa A

Diagramma a stati dell'automa B

Più formalmente potremmo dire che eseguendo l'automa su tutte le possibili stringhe non viene mai raggiunto nessuno degli stati finali.

In conclusione, dato un automa accettore $A=(Q,I,\delta ,q_{o},F)$, vale la seguente affermazione: $\forall x\in I^{*},\delta ^{*}(q_{0},x)\not \subset F$.

Linguaggi finiti

Ora che sappiamo che gli automi riconoscitori possono accettare il linguaggio vuoto vale la pena di indagare la categoria dei linguaggi finiti, intendendo con ciò i linguaggi che si possono rappresentare come insiemi contenenti un numero finito di stringhe.

A livello intuitivo, se il diagramma degli stati di un automa non contiene cicli (autoanelli compresi), dovrebbe esistere un insieme finito di stringhe accettate dall'automa.

Supponiamo di disporre di una stringa di ingresso accettabile da un riconoscitore a stati finiti privo di cicli. Evidentemente, l'evoluzione dell'automa man mano che riceverà i caratteri della stringa lo porterà, nella peggiore delle ipotesi, a visitare tutti gli stati dell'automa stesso una volta sola: questa garanzia ci deriva dall'assenza di cicli.

Dato che il diagramma degli stati dell'automa è, come abbiamo visto, un grafo, l'ipotesi di assenza di cicli lo rende necessariamente un albero.

Sappiamo che ogni transizione consuma un simbolo in ingresso, perciò nel caso peggiore la stringa riconosciuta sarà composta da un numero di simboli pari al numero di lati di un albero.

Indicando con $A$ l'accettore a stati finiti, con $n=|Q|$ il numero di stati dell'automa e con $x\in L(A)$ una qualsiasi stringa accettata da $A$, si può quindi concludere che $|x|<n$.

A questo punto si può porre anche un limite superiore alla cardinalità del linguaggio dell'automa: dato che le stringhe accettabili hanno lunghezza limitata e considerando che ognuna di esse viene formata a partire da un insieme finito, si può concludere che esisterà un limite superiore al numero di stringhe appartenenti al linguaggio. Per calcolare questo limite basterà sommare tutte le possibili stringhe aventi lunghezza 0, poi quelle di lunghezza 1, quelle di lunghezza 2 e così via, fino ad arrivare a $n-1$. Indicando con la lettera $m=|I|$ la cardinalità dell'alfabeto di ingresso, la generica stringa composta da $k$ simboli potrà essere generata in $m^{k}$ modi diversi. Per questo motivo, il limite superiore che stiamo cercando si potrà esprimere con la seguente formula:

$|L(A)|\leq \sum _{k=0}^{n-1}m^{k}$

Teorema

Condizione necessaria e sufficiente affinché un accettore a stati finiti $A=(Q,I,\delta ,q_{0},F)$ accetti un linguaggio non vuoto è che possa accettare una stringa $x\in I^{*}$ con $|x|<|Q|$.

Dimostrazione

Dato che il teorema esprime una condizione necessaria e sufficiente, la dimostrazione viene divisa in due parti.

Parte del se - Si tratterebbe di dimostrare che, se l'accettore riconosce una stringa con lunghezza inferiore al numero degli stati, allora il linguaggio riconosciuto non è vuoto. Evidentemente banale.

Parte del solo se - Qui si deve dimostrare che, se l'accettore riconosce un linguaggio finito, allora riconosce una stringa con lunghezza inferiore al numero degli stati. Si consideri quindi una stringa $x\in L(A)|\forall y\in L(A),|x|<|y|$ e si supponga, per assurdo, che $|x|>|Q|$. Questa ipotesi implica che nel linguaggio non vuoto accettato dall'automa non esistono stringhe con lunghezza inferiore al numero di stati. Per quanto abbiamo discusso in precedenza l'automa deve disporre, in questo caso, di almeno un ciclo; possiamo quindi scomporre la stringa $x$ in tre sottostringhe non vuote: $x_{1}$ che viene prima della parte ciclica, $x_{2}$ che rappresenta la parte ciclica e $x_{3}$ che viene dopo la parte ciclica. Analizziamo l'evoluzione dello stato dell'automa in corrispondenza a queste tre sottostringhe:

1. $\delta ^{*}(q_{0},x_{1})=q$
2. $\delta ^{*}(q,x_{2})=q$
3. $\delta ^{*}(q,x_{3})\subset F$

La seconda sottostringa porta al medesimo stato della prima in quanto rappresenta la componente ciclica. Come si può notare, sarebbe possibile raggiungere uno stato finale anche con la stringa $x_{1}x_{3}$, saltando quindi la parte ciclica. Ma $|x_{1}x_{3}|<|x_{1}x_{2}x_{3}|=|x|$ e ciò contraddice l'ipotesi secondo cui $x$ è la stringa più corta. Questo ci permette di concludere che $S=\left\{x\in L(A)||x|<|Q|\right\}\neq \emptyset$; ciò dimostra il teorema.

Linguaggi infiniti

Qualora il diagramma degli stati di un automa accettore dovesse contenere cicli (autoanelli compresi), questi potrebbero essere attraversati per un numero arbitrario di volte, portando alla costruzione di linguaggi contenenti infinite stringhe.

Intuitivamente, all'interno di una stringa è possibile identificare un comportamento ciclico perché vi sarà un gruppo di simboli che si ripete regolarmente. La stringa si potrà quindi scomporre in tre parti: una che precede il ciclo, una che si ripete ciclicamente ed una che segue il ciclo.

Teorema

Un automa riconoscitore a stati finiti $A=(Q,I,\delta ,q_{i},F)$ accetta un linguaggio infinito se e solo se accetta una stringa $x\in I^{*}$ con $|Q|\leq |x|<2|Q|$.

Dimostrazione

Considerando che il teorema esprime una condizione necessaria e sufficiente è possibile suddividere la dimostrazione in due parti.

Parte del se - In questa parte bisogna dimostrare che se l'automa accetta una stringa $x$ con $|Q|\leq |x|<2|Q|$, allora il linguaggio riconosciuto dall'automa stesso è infinito.

Nel teorema che abbiamo dimostrato nella sezione per i linguaggi finiti è stato evidenziato che quando una stringa ha lunghezza maggiore o uguale al numero degli stati di un automa, allora l'automa deve ammettere un ciclo, inteso come una sequenza di uno o più stati che vengono percorsi più di una volta durante le transizioni.

Considerando che, per ipotesi, lavoreremo con una stringa dotata di lunghezza maggiore o uguale al numero degli stati dell'automa, possiamo concludere che la stringa si potrà scomporre in tre parti: la prima che precede il ciclo ($x_{1}$), la seconda che si produce durante il ciclo ($x_{2}$) e la terza che segue il ciclo ($x_{3}$). In generale, potremo scrivere $x=x_{1}x_{2}x_{3}$.

Se a questo punto costruissimo una stringa $y=x_{1}x_{2}x_{2}x_{3}=x_{1}x_{2}^{2}x_{3}$, anch'essa verrebbe accettata dall'automa in quanto la seconda ripetizione della parte ciclica porterebbe l'automa nello stesso stato che si avrebbe senza la ripetizione stessa.

Generalizzando, è possibile immaginare di ripetere la parte ciclica della stringa per un numero arbitrario di volte, arrivando a concludere che il linguaggio riconosciuto dall'accettore a stati finiti è infinito.

Parte del solo se - In questa parte bisogna dimostrare che se l'automa accetta un linguaggio infinito, allora accetta un stringa $x\in I^{*}$ tale che $|Q|\leq |x|<2|Q|$.

Affrontiamo la dimostrazione per assurdo, immaginando che nessuna stringa riconosciuta dall'automa rispetti la condizione imposta per la sua lunghezza.

A questo punto, l'automa riconoscerebbe due tipi di stringhe: quelle che hanno lunghezza minore del numero degli stati dell'automa e quelle che hanno lunghezza almeno doppia rispetto al numero degli stati dell'automa.

Per quanto riguarda il primo tipo, il teorema dimostrato nella sezione precedente ci permette di concludere che il linguaggio generato dall'automa sarebbe finito, il che porterebbe ad una contraddizione.

Per quanto riguarda il secondo tipo di stringhe, notiamo che data la loro lunghezza devono necessariamente contenere una componente ciclica, quindi ognuna di esse si può scomporre in tre parti (come abbiamo visto finora), di cui una che si ripete ciclicamente; come al solito, indichiamo con $x_{1}$ la parte della stringa che viene prima del ciclo, con $x_{2}$ la parte ottenuta visitando ripetutamente alcuni nodi dell'automa e con $x_{3}$ la parte successiva al ciclo.

Riprendendo le stesse considerazioni viste in precedenza, anche la stringa $x_{1}x_{3}$ è accettata dal linguaggio e sicuramente $|x_{1}x_{3}|<|x|$. A questo punto, se $|x_{1}x_{3}|<2|Q|$ allora il teorema è dimostrato; in caso contrario, visto che la stringa $x_{1}x_{3}$ è più lunga del numero di stati dell'automa, sarà possibile ripetere la scomposizione che abbiamo appena svolto. Tale procedimento si può tranquillamente reiterare finché la lunghezza della stringa scomposta raggiungerà un valore più basso del numero degli stati. Ma in quella condizione avremmo una contraddizione in quanto il linguaggio riconosciuto dall'automa sarebbe finito. Questa osservazione dimostra definitivamente il teorema.

Il pumping lemma

Nelle sezioni precedenti si sono trovati tre risultati che dimostrano come alcune categorie di linguaggi si possano associare agli automi a stati finiti: il linguaggio vuoto, i linguaggi finiti ed i linguaggi infiniti.

Nel caso dell'ultima categoria, ossia per i linguaggi infiniti, sorge spontanea una domanda: sarà vero che ogni linguaggio infinito può essere riconosciuto da un automa accettore a stati finiti?

Se ciò fosse vero sarebbe utile disporre di qualche informazione in più sulla relazione tra linguaggi ed automi; se invece fosse falso, sarebbe utile disporre di uno strumento che permetta di distinguere i linguaggi infiniti che si possono associare ad accettori a stati finiti da quelli che non possono essere riconosciuti tramite questo formalismo.

La risposta a questa domanda arriva dal pumping lemma, un risultato centrale per la teoria degli automi che, sinteticamente, rappresenta una condizione necessaria affinché un linguaggio infinito possa essere riconosciuto da un accettore a stati finiti.

Il fatto che si tratti di una condizione necessaria e non sufficiente lascia immaginare che esisteranno linguaggi infiniti non riconoscibili dagli automi accettori; questa considerazione pone un limite alla capacità di riconoscimento associata agli automi a stati finiti ed apre la discussione su quali formalismi si possano usare per arrivare dove gli accettori a stati finiti non arrivano; quest'ultimo aspetto sarà all'origine degli automi a pila e delle macchine di Turing, formalismi che verranno presentati ed approfonditi nel seguito di questo corso.

Prima di enunciare e dimostrare il teorema vale la pena spendere qualche parola sul fatto che il pumping lemma è una condizione necessaria. Tutti i linguaggi riconosciuti dagli accettori a stati finiti rispettano determinate condizioni; alcune di queste sono stabilite dal pumping lemma, ma non tutte. Questo significa che un linguaggio dotato di caratteristiche compatibili con il pumping lemma potrebbe essere riconosciuto da un accettore a stati finiti; l'uso del condizionale è d'obbligo in quanto vanno soddisfatte anche condizioni che il teorema non dimostra.

Apparentemente questo rende il teorema inapplicabile per scopi pratici, ma c'è un altro aspetto da considerare: quando un linguaggio infinito non rispetta le condizioni del pumping lemma possiamo concludere che non potrà esistere un automa in grado di riconoscerlo. Da un punto di vista concettuale, quindi, il teorema ci permette di raggiungere due obiettivi:

• se un linguaggio formale è regolare sicuramente rispetta il pumping lemma;
• se il pumping lemma non è verificato, il linguaggio formale in questione non può essere riconosciuto da un accettore a stati finiti.

Dopo aver contestualizzato questo importante risultato riguardante linguaggi ed automi, veniamo alla sua enunciazione ed alla relativa dimostrazione.

Teorema

Si consideri un automa accettore a stati finiti $A=(Q,I,\delta ,q_{i},F)$ che riconosce un linguaggio formale infinito indicato con $L(A)$. Allora, per ogni stringa $x\in L(A)$ tale che $|x|\geq |Q|$ è possibile trovare uno stato $q\in Q$ ed una stringa $w\in I^{+}$ tali da verificare le seguenti condizioni:

• $x=ywz,y\in I^{*},z\in I^{*}$;
• $\delta ^{*}(q,w)=q$.

Come conseguenza, tutte le stringhe nella forma $yw^{k}z,k\in \mathbb {N}$ sono riconosciute dall'automa.

Dimostrazione

Per ipotesi la stringa $x$ ha lunghezza maggiore del numero degli stati dell'automa; visto che ogni transizione consuma un simbolo della stringa d'ingresso, questo significa che la lettura completa della stringa implica la visita per più di una volta di almeno uno degli stati; indichiamo con $q$ uno degli stati che vengono attraversati ripetutamente.

Se durante l'evoluzione dell'automa lo stato $q$ viene visitato più volte vuol dire che fa di un ciclo, ossia di una sequenza di stati che iniziano e terminano con lo stato stesso.

All'interno del ciclo si manifestano delle transizioni, ognuna delle quali consuma un simbolo della stringa d'ingresso; l'insieme dei simboli della stringa d'ingresso consumati percorrendo il ciclo costituisce una stringa $w\in I^{+}$ che non può essere vuota perché il ciclo viene eseguito almeno una volta. Questa considerazione ci permette di concludere che $\delta ^{*}(q,w)=q$, completando una parte della dimostrazione del teorema.

La presenza della stringa $w$ permette di scomporre l'accettazione della stringa $x$ in tre fasi:

1. evoluzione dallo stato iniziale fino allo stato q;
2. ripetizione del ciclo, partendo ed arrivando nello stato q;
3. raggiungimento di uno stato di accettazione a partire dallo stato q.

Ognuna delle tre fasi consuma simboli dal nastro di ingresso, quindi sarà possibile associare delle stringhe ad ogni fase, in particolare:

1. alla prima fase si associa la stringa $y$;
2. alla seconda fase si associa la stringa $w$ vista sopra;
3. alla terza fase si associa la stringa $z$.

In questo modo la stringa $x$ accettata si può anche scrivere come $x=ywz$.

Supponiamo ora che la stringa $w$ sia stata ottenuta concatenando i simboli che si ottengono percorrendo una volta sola il ciclo dell'automa. Percorrendo il medesimo ciclo per $k$ volte l'automa genererebbe la concatenazione della stringa $w$ con se stessa per $k$ volte, brevemente $w^{k}$. Logicamente, se l'automa accetta la stringa $x=ywz$ accetterà anche la stringa $t=yw^{k}z$, con $k\in \mathbb {N}$.

In questo modo il teorema è completamente dimostrato.

Uso del pumping lemma

Vediamo ora come il pumping lemma possa essere impiegato per dimostrare che un linguaggio formale non può essere riconosciuto da un automa accettore.

Per poter impiegare questo risultato dobbiamo anzitutto essere certi che sia applicabile assicurandoci che le sue ipotesi siano verificate. Più precisamente:

• bisogna essere certi che il linguaggio formale in questione sia infinito;
• bisogna disporre almeno di una stima della cardinalità dell'insieme degli stati, in modo da poter identificare una stringa più lunga del numero di stati.

Per quanto riguarda il secondo punto, spesso si procede come segue: si fissa una costante $k\in \mathbb {N}$ in modo arbitrario, poi la si sfrutta per creare una stringa $x\in L$ per la quale si possa scrivere $|x|>k$.

Nelle sezioni che seguono introdurremo due linguaggi formali e dimostreremo, grazie al pumping lemma, che non saranno accettabili da riconoscitori a stati finiti; oltre ad essere una buona occasione per vedere all'opera il pumping lemma, l'analisi della struttura dei due linguaggi formali ci consentirà di comprendere, almeno a livello intuitivo, quali caratteristiche ostacolino il loro riconoscimento tramite accettori.

Il linguaggio $a^{n}b^{n}$

Consideriamo l'alfabeto $I=\left\{a,b\right\}$ ed il linguaggio formale $L\subset I^{*}$ definito come $L=\left\{a^{n}b^{n}|n\in \mathbb {N} \right\}$.

Vogliamo capire se sia possibile costruire un automa accettore a stati finiti che sia in grado di riconoscere il linguaggio dato.

La dimostrazione si effettua per assurdo: assumendo inizialmente che il pumping lemma sia valido per il linguaggio $L$, dimostreremo che non è così.

Affinché il pumping lemma sia valido dobbiamo essere certi che le sue ipotesi siano verificate.

Il linguaggio formale che stiamo analizzando è senza dubbio infinito visto che c'è arbitrarietà nella scelta del numero naturale $n$.

Si consideri quindi un automa con $n$ stati ed una stringa $x\in L=a^{n}b^{n}$; in questo caso è evidente che $|x|>n$, dunque le ipotesi del teorema sono verificate.

È possibile scomporre la stringa $a^{n}b^{n}$ nelle tre componenti previste: $a^{n}b^{n}=xw^{k}y$.

In linea di principio la parte ciclica, ossia la stringa $w$, può essere composta in uno dei tre modi seguenti:

1. sequenza di simboli $a$, ossia $w=a^{p}$;
2. qualche simbolo $a$ seguito da qualche simbolo $b$, ossia $w=a^{p}b^{q}$;
3. sequenza di simboli $b$, ossia $w=b^{q}$.

Nel primo caso la parte ciclica si manifesta all'interno della sequenza di $a$; di conseguenza la stringa $a^{n}b^{n}$ si potrà scomporre come segue: $a^{n}b^{n}=a^{r}a^{p}a^{s}b^{n}=a^{r}wa^{s}b^{n}$, dove $r+p+s=n$; i tre esponenti sono da intendere come numeri naturali. Qualora il pumping lemma fosse verificato, la stringa $a^{r}w^{k}a^{s}b^{n}$ dovrebbe appartenere al linguaggio; dimostriamo che non è così. Possiamo riscrivere la stringa come $a^{r}w^{k}a^{s}b^{n}=a^{r}a^{kp}a^{s}b^{n}$ in cui $r+kp+s=r+p+s+(k-1)\cdot p=n+(k-1)\cdot p$; raccogliendo tutte le occorrenze di simboli $a$ in una scrittura unica avremo: $a^{n+(k-1)\cdot p}b^{n}$. Quest'ultima stringa non appartiene al linguaggio formale poiché il numero di $a$ non è lo stesso del numero di $b$ per l'arbitrarietà di $k$; il primo caso è dunque dimostrato.

Nel secondo caso $a^{n}b^{n}=a^{r}a^{p}b^{q}b^{s}=a^{r}wb^{s}$, dove $r+p=q+s=n$; come prima, vediamo cosa accade quando si considera la stringa $a^{n}b^{n}=a^{r}w^{k}b^{s}=a^{r}(a^{p}b^{q})^{k}b^{s}$. In questa stringa il numero di $a$ è dato dall'espressione $r+pk=n+p\cdot (k-1)$, mentre il numero di $b$ è $qk+s=n+q\cdot (k-1)$. In generale, quindi, il numero di $a$ è diverso dal numero di $b$; ne consegue che anche in questo caso il pumping lemma non viene rispettato.

L'ultima situazione da analizzare non fa eccezione, in quanto può essere svolta impiegando la medesima tecnica utilizzata per il primo caso.

Si può dunque concludere che il pumping lemma non è rispettato per questo linguaggio formale e che quindi non sia possibile costruire un accettore a stati finiti che lo riconosca.

Il linguaggio $wcw^{R}$

Consideriamo un insieme finito di simboli $I=\left\{a,b\right\}$ ed una generica stringa $w=\left\{a,b\right\}+$, ossia una stringa di lunghezza non nulla costituita da una successione finita di simboli presi dall'insieme $I$.

Si indichi inoltre con $w^{R}$ la stringa ottenuta da $w$ invertendo l'ordine dei simboli; se $w=w_{0}w_{1}w_{2}...w_{n}$, allora $w^{R}=w_{n}...w_{2}w_{1}w_{0}$.

Grazie a queste stringhe costruiamo il linguaggio formale $L=\left\{wcw^{R}|w=\left\{a,b\right\}^{+}\right\}$. Dimostriamo che $L$ non può essere il linguaggio macchina di nessun accettore a stati finiti.

Anche in questo caso procederemo per assurdo, ipotizzando che il pumping lemma sia valido per il linguaggio in questione ed arrivando ad una contraddizione.

Assicuriamoci anzitutto che le ipotesi del teorema siano verificate. Dato che la lunghezza delle stringhe del linguaggio formale è arbitraria il linguaggio stesso è infinito; indicando con $n$ il numero di stati dell'automa accettore possiamo scegliere una stringa ${\overline {w}}$ in modo che $|{\overline {w}}|=n$. In base a questa scelta, la stringa $x\in L|x={\overline {w}}c{\overline {w}}^{R}$ sarà tale da avere lunghezza $|x|=2n+1$, quindi $|x|>n$, come richiesto dal pumping lemma.

A questo punto, la stringa $wcw^{R}$ si potrebbe scomporre in tre sottostringhe: $wcw^{R}=xyz$.

La stringa $y$ è quella che si può ripetere per un numero indefinito di volte; questo aspetto ci permette di concludere che, qualora $y$ dovesse contenere il simbolo $c$, sicuramente $xy^{k}z\notin L$ poiché conterrebbe più di una occorrenza del simbolo $c$.

Restano quindi da indagare due situazioni: quella in cui la stringa $y$ contiene solamente caratteri che si trovano prima del simbolo $c$ e quella in cui la stringa contiene solamente caratteri che si trovano dopo $c$.

Nel primo caso, la stringa ${\overline {w}}$ si potrebbe scomporre in tre parti: ${\overline {w}}=pyq$; come conseguenza, la stringa ${\overline {w}}^{R}=q^{R}y^{R}p^{R}$ e questo rappresenta un problema: infatti, quando si ripete la stringa $y$, solamente una delle sue occorrenze potrebbe essere ripetuta, conducendo a stringhe che non possono appartenere al linguaggio.

Il secondo caso, in cui $y$ si manifesta dopo l'occorrenza del simbolo $c$, si dimostra in modo del tutto analogo.

Essendoci una contraddizione si conclude che il pumping lemma non vale per il linguaggio analizzato e, quindi, che non esiste nessun automa a stati finiti in grado di riconoscerlo.

Conseguenze del Pumping Lemma

Nella discussione antecedente alla dimostrazione del pumping lemma abbiamo accennato ad un'importante conseguenza della sua validità: il fatto che alcuni dei linguaggi infiniti non siano riconoscibili attraverso accettori a stati finiti.

Oltre ad aprire interessanti speculazioni circa possibili nuovi formalismi adatti all'accettazione di un insieme più ampio di linguaggi, il pumping lemma porta con se una spiacevole conseguenza, derivante dalla sua natura di condizione necessaria: il teorema è un ottimo strumento per indicare quali linguaggi non sono riconoscibili, ma non offre garanzie per i linguaggi riconoscibili.

La ricerca di una struttura precisa per i linguaggi accettabili da riconoscitori a stati finiti deve quindi andare oltre, puntando a precisare in che modo si possano associare linguaggi agli automi accettori.

Questa linea di ricerca ha condotto due matematici, John Myhill e Anil Nerode, alla dimostrazione di un risultato ben più profondo del pumping lemma: il loro teorema offre una descrizione accurata delle proprietà dei linguaggi riconoscibili dagli accettori a stati finiti, consentendone una definizione rigorosa.

Il teorema di Myhill e Nerode sarà oggetto della prossima sezione.

Linguaggi e automi a stati finiti

Occupiamoci ora del rapporto esistente tra i linguaggi formali e gli automi a stati finiti. L'esistenza degli automi accettori consente di mettere in relazione i due mondi; il pumping lemma dimostra che esistono linguaggi formali per i quali è impossibile costruire un riconoscitore a stati finiti. Sappiamo però che vi sono numerose situazioni in cui ad un linguaggio formale è possibile associare un automa accettore a stati finiti.

Possiamo quindi concludere che, tra tutti i linguaggi formali, alcuni possano essere associati a degli accettori a stati finiti; in linea di massima, l'insieme di tutti i linguaggi formali che possono essere riconosciuti da automi a stati finiti dovrebbe essere composto da linguaggi con caratteristiche strutturali analoghe. Il lavoro svolto da MyHill e Nerode serve per evidenziare proprio questa particolarità.

Per indagare in modo più approfondito la relazione esistente tra i due mondi seguiremo la seguente strategia:

1. dato un generico automa a stati finiti, definiremo una relazione di equivalenza tra le stringhe che esso è in grado di riconoscere;
2. dato un generico linguaggio formale, definiremo una relazione di equivalenza tra le stringhe appartenenti al linguaggio;
3. confronteremo le due equivalenze, cercando analogie che permettano di dedurre le proprietà strutturali dei linguaggi riconosciuti dagli automi accettori.

Questi sforzi consentiranno di enunciare del teorema di Myhill e Nerode, risultato che permetterà di identificare correttamente anche quella parte dei linguaggi infiniti che il pumping lemma non permette di classificare correttamente.

Stringhe equivalenti in un accettore

Si consideri un automa accettore a stati finiti $M=(Q,I,\delta ,q_{i},F)$ e due stringhe $x\in I^{*}$ e $y\in I^{*}$. Costruiamo una relazione $R_{M}(x,y)={\text{x e y terminano l'esecuzione in M nello stesso stato}}$.

Esaminiamo ora le proprietà della relazione:

• $R_{M}$ è una relazione riflessiva in quanto $R_{M}(x,x)$ è logicamente sempre vera;
• $R_{M}$ è una relazione simmetrica, infatti se $R_{M}(x,y)$ è vera, anche $R_{M}(y,x)$ è vera;
• $R_{M}$ è una relazione transitiva: se $R_{M}(x,y)$ è vera e $R_{M}(y,z)$ è vera, allora anche $R_{M}(x,z)$ è vera.

Come conseguenza $R_{M}$ è una relazione di equivalenza. Accanto a questo risultato ve ne è un altro estremamente importante: $R_{M}$ è una relazione invariante a destra; di questo ci occupiamo nella prossima sezione.

Invarianza a destra

Siano $x,y,z$ tre stringhe appartenenti al monoide libero generato sull'alfabeto d'ingresso dell'accettore a stati finiti e siano $x,y$ equivalenti secondo $R_{M}$.

La relazione $R_{M}$ è invariante a destra se e solo se qualunque stringa z si concateni a x ed y porta l'automa nel medesimo stato finale.

Più precisamente, se $x$ ed $y$ sono in relazione secondo $R_{M}$, allora le stringhe $t=xz$ e $u=yz$ sono anch'esse equivalenti secondo $R_{M}$.

Dimostriamo l'affermazione: dato che $x$ ed $y$ sono in relazione secondo $R_{M}$, sappiamo per definizione che $\delta ^{*}(q_{0},x)=\delta ^{*}(q_{0},y)$.

Per la definizione di funzione di transizione generalizzata possiamo anche scrivere $\delta ^{*}(q_{0},t)=\delta ^{*}(q_{0},xz)=\delta (\delta ^{*}(q_{0},x),z)$.

Possiamo poi sostituire $\delta ^{*}(q_{0},x)$ con $\delta ^{*}(q_{0},y)$ ottenendo $\delta (\delta ^{*}(q_{0},y),z)=\delta ^{*}(q_{0},yz)=\delta ^{*}(q_{0},u)$. Questo prova il fatto che la relazione $R_{M}$ è invariante a destra.

Significato dell'invarianza a destra

Se è vero che dal punto di vista logico dimostrare l'invarianza a destra della relazione $R_{M}$ non pone problemi, il discorso cambia quando si desidera attribuire un significato a questa proprietà.

Vale la pena, in tal caso, di immaginare l'accettore a stati finiti mentre elabora una stringa di ingresso $t=xz$, considerando la situazione in cui abbia appena terminato di elaborare il prefisso $x$. In questo caso, $x$ indica la porzione del nastro di ingresso che è già stata letta, mentre $z$ indica la parte ancora da leggere. Nell'ipotesi che la stringa $y$ sia equivalente a $x$ secondo la relazione $R_{M}$, allora l'elaborazione della stringa $y$ porterebbe l'automa nello stesso stato in cui si troverebbe dopo aver elaborato $x$. A questo punto l'automa non sarebbe più in grado di distinguere la stringa $t=xz$ dalla stringa $u=yz$ in quanto elaborando il suffisso attraverserebbe gli stessi stati.

Il fatto che due stringhe equivalenti portino l'automa ad assumere lo stesso stato significa che ogni stato dell'automa rappresenta una classe di equivalenza secondo la relazione $R_{M}$; è quindi possibile concludere che l'indice della relazione $R_{M}$ è pari alla cardinalità dell'insieme degli stati dell'automa. Visto che la relazione $R_{M}$ è invariante a destra, ogni coppia di stringhe equivalenti può essere estesa con un suffisso appropriato, che in precedenza abbiamo indicato con la lettera $z$. È dunque plausibile che esista un legame tra il numero di stati dell'automa ed il numero di suffissi; una cosa è certa: dato che l'automa di partenza è a stati finiti, l'insieme degli stati contiene un numero finito di elementi e proprio per questo motivo il linguaggio riconosciuto dall'automa conterrà stringhe dotate di un numero finito di suffissi differenti.

Grazie alla relazione $R_{M}$ è quindi possibile ipotizzare una struttura per i linguaggi riconosciuti dagli automi accettori; il quadro della situazione, però, non è ancora completo e andrà sviluppato analizzando una relazione di equivalenza simile a $R_{M}$, ma introdotta nell'insieme dei linguaggi.

Stringhe equivalenti in un linguaggio

Considerando un insieme finito di simboli indicato con la lettera $I$, un generico linguaggio formale $L$ è un sottoinsieme del monoide libero generato da $I$; in simboli possiamo scrivere: $L\subseteq I^{*}$.

Stringhe distinguibili e indistinguibili

Consideriamo due stringhe $x\in I^{*},y\in I^{*}$ ed un generico linguaggio formale $L\subseteq I^{*}$.

Le stringhe $x$ e $y$ si dicono distinguibili rispetto a $L$ se esiste almeno una stringa $z$ tale che $xz$ è una stringa di $L$ mentre $yz$ non lo è. Formalmente: $\exists z\in I^{*}:(xz\in L)\land (yz\notin L)$.

Al contrario le stringhe $x$ e $y$ si dicono indistinguibili rispetto a $L$ se comunque si scelga una stringa $z$ le stringhe $xz$ e $yz$ appartengono entrambe al linguaggio $L$, oppure nessuna delle due vi appartiene. Formalmente: $\forall z\in I^{*}:((xz\notin L)\land (yz\notin L))\lor ((xz\in L)\land (yz\in L))$.

Equivalenza delle stringhe indistinguibili

Da un punto di vista intuitivo è logico aspettarsi che due stringhe indistinguibili rispetto a un dato linguaggio formale siano equivalenti. Proprio per questo motivo ha senso definire la relazione $R_{L}(x,y):{\text{x ed y sono indistinguibili rispetto a L}}$.

Una volta posta la definizione è necessario dimostrare che la relazione appena introdotta è effettivamente un'equivalenza. La dimostrazione si ottiene semplicemente applicando la definizione di indistinguibilità delle stringhe, dunque viene lasciata come esercizio. Applicando la definizione ci si rende conto anche del fatto che la relazione $R_{L}$ è invariante a destra.

Il fatto che $R_{L}$ sia una relazione di equivalenza definita su $I^{*}$ comporta necessariamente il partizionamento di tale insieme e come sappiamo ogni sottoinsieme della partizione identifica una delle classi di equivalenza indotte dalla relazione.

In linea di principio tali classi di equivalenza possono contenere due tipi di stringhe: o stringhe che appartengono al linguaggio $L$, oppure stringhe che non gli appartengono.

È chiaro, quindi, che per raccogliere tutte le stringhe appartenenti al linguaggio in un unico insieme sarà necessario determinare l'unione di un certo numero di classi di equivalenza.

Questa osservazione ci impone di capire quante siano le classi di equivalenza da unire; per chiarire questo aspetto sarà necessario confrontare la relazione $R_{L}$ appena introdotta con la relazione $R_{M}$ che abbiamo specificato per gli accettori a stati finti.

Confronto fra $R_{M}$ e $R_{L}$

Le informazioni raccolte fino in questo punto sulla relazione $R_{L}$ evidenziano forti analogie con la relazione $R_{M}$ introdotta per gli automi a stati finiti.

Ci interessa particolarmente un aspetto riguardante le classi di equivalenza che le due relazioni inducono sull'insieme $I^{*}$. Infatti, dato che le relazioni sono definite sullo stesso insieme è possibile che inducano le medesime classi di equivalenza. La relazione definita sui linguaggi ci ha permesso di stabilire che le stringhe appartenenti al linguaggio sono l'unione di alcune delle classi di equivalenza, mentre quella riguardante gli accettori a stati finiti ci ha consentito di determinare che esiste un numero finito di classi di equivalenza.

Unendo queste due informazioni possiamo concludere che il linguaggio $L$ si può pensare come l'unione di un numero finito di classi di equivalenza indotte da $R_{L}$.

Formalizziamo questo concetto: indichiamo con $[x]$ la generica classe di equivalenza indotta dalla relazione $R_{L}$ sull'insieme $I^{*}$. Si potrà scrivere:

$L=\bigcup _{x\in L}[x]$

La discussione sulle classi di equivalenza definite sugli accettori e sui linguaggi formali ha permesso di trarre alcune conclusioni circa le proprietà possedute dai linguaggi riconosciuti mediante un automa. Tali conclusioni hanno creato le condizioni ideali per l'enunciazione del teorema di Myhill - Nerode, la cui dimostrazione servirà per dare una veste formale alle congetture fin qui solamente intuite.

Il teorema di Myhill - Nerode

Si consideri un insieme finito di simboli $I$ ed un linguaggio formale $L\subseteq I^{*}$; si consideri inoltre un automa accettore a stati finiti $M=(Q,I,\delta ,q_{i},F)$. Le tre affermazioni sottostanti sono logicamente equivalenti:

• il linguaggio $L$ è riconosciuto dall'accettore a stati finiti $M$;
• $L$ è l'unione di classi di equivalenza indotte su $I^{*}$ da una relazione di equivalenza di indice finito invariante a destra;
• la relazione di equivalenza definita su $L$: $R_{L}(x,y):\forall z\in I^{*}(xz\in L)\iff (yz\in L)$ è di indice finito.

Dimostrazione

La strategia adottata per provare il teorema di Myhill - Nerode prevede la dimostrazione di una serie di implicazioni, in particolare:

• se il linguaggio è riconosciuto dall'accettore, allora é l'unione di classi di equivalenza indotte su $I^{*}$ da una relazione di equivalenza di indice finito invariante a destra;
• se il linguaggio è l'unione di alcune classi di equivalenza indotte su $I^{*}$ da una relazione di equivalenza di indice finito invariante a destra, allora la relazione di equivalenza $R_{L}(x,y):\forall z\in I^{*}(xz\in L)\iff (yz\in L)$ è di indice finito;
• se la relazione di equivalenza definita su $L$: $R_{L}(x,y):\forall z\in I^{*}(xz\in L)\iff (yz\in L)$ è di indice finito, allora il linguaggio è riconosciuto dall'accettore.

Dimostriamo separatamente le tre implicazioni.

Prima implicazione

Per ipotesi il linguaggio $L$ è riconosciuto dall'accettore. Per dimostrare questa implicazione è sufficiente richiamare la relazione $R_{M}$ che abbiamo definito sul generico automa accettore. Abbiamo dimostrato che tale relazione è un'equivalenza invariante a destra e che il suo indice (dato dalla cardinalità dell'insieme degli stati) è finito; come conseguenza la prima implicazione è dimostrata.

Seconda implicazione

Per ipotesi il linguaggio $L$ è l'unione di alcune classi di equivalenza indotte da una relazione di equivalenza $R$ di indice finito invariante a destra. L'obiettivo è garantire che la relazione di equivalenza $R_{L}$ definita nell'enunciazione del teorema abbia anch'essa indice finito.

Le relazioni $R$ e $R_{L}$ sono definite entrambe sull'insieme $I^{*}$ e lo partizionano in classi di equivalenza. Una possibile strategia per provare l'implicazione consiste nel dimostrare che l'indice dell'equivalenza $R_{L}$ è minore o uguale a tutti gli indici delle equivalenze $R$ citate nella premessa dell'implicazione stessa.

Quando ciò si verifica si dice che $R$ è un raffinamento di $R_{L}$, intendendo con ciò che ogni classe di equivalenza di $R$ è strettamente contenuta in una classe di equivalenza di $R_{L}$.

Come conseguenza, se due stringhe sono equivalenti secondo la relazione $R$, lo saranno sicuramente anche secondo $R_{L}$.

Consideriamo quindi due generiche stringhe $x\in I^{*}$ e $y\in I^{*}$, scelte in modo che l'equivalenza $R(x,y)$ sia verificata. Dato che $R$ è invariante a destra sarà anche vero che $\forall z\in I^{*},R(xz,yz)$.

Dato che $L$ è l'unione insiemistica di classi di equivalenza indotte da $R$, potremo affermare che $(xz\in L)\iff (yz\in L)$; ma questa è proprio la definizione di $R_{L}(xz,yz)$; l'implicazione è quindi dimostrata.

Terza implicazione

In questo caso abbiamo l'ipotesi che la relazione di equivalenza definita su $L$: $R_{L}(x,y):\forall z\in I^{*}(xz\in L)\iff (yz\in L)$ è di indice finito e dobbiamo dimostrare che il linguaggio $L$ é riconosciuto da un automa accettore.

Indichiamo quindi con $M=(Q,I,\delta ,q_{i},F)$ l'automa e proponiamo una procedura per costruirlo a partire dalla partizione indotta su $I^{*}$ dalla relazione di equivalenza $R_{L}$, sapendo che è indice finito.

Per costruire l'accettore $M$ è sufficiente trovare un modo appropriato per definire i suoi elementi:

• l'insieme degli stati dell'automa coincide con l'insieme quoziente indotto dalla relazione $R_{L}$ su $I^{*}$: $Q=I^{*}/R_{L}$;
• l'alfabeto di ingresso sarà l'insieme finito di simboli sul cui monoide libero è stato costruito $L$;
• la funzione di transizione associa ad ogni classe di equivalenza $[x]$ e ad ogni simbolo d'ingresso $i\in I$ al massimo una classe di equivalenza: $\delta ([x],i)=[xi]$. È lasciata per esercizio la ridefinizione della funzione $\delta ^{*}$;
• lo stato iniziale corrisponde alla classe di equivalenza $[\epsilon ]$ in quanto la stringa di ingresso non è ancora stata letta;
• l'insieme degli stati finali è costituito da tutte le classi di equivalenza che contengono stringhe appartenenti al linguaggio: $F=\left\{[x]:x\in L\right\}$.

Conseguenze del teorema di Myhill - Nerode

La dimostrazione del teorema di Myhill - Nerode ci consente di stabilire l'equivalenza logica tra l'accettabilità di un linguaggio formale $L$ da parte di un riconoscitore a stati finiti e la finitezza dell'indice di un'equivalenza invariante a destra $R_{L}$.

Ciò significa che la finitezza dell'indice dell'equivalenza è condizione necessaria e sufficiente affinché un accettore a stati finiti possa riconoscere il linguaggio in questione.

Il teorema di Myhill e Nerode rappresenta quindi un importante passo avanti rispetto al Pumping Lemma, che é solamente una condizione necessaria.

Grazie al teorema di Myhill - Nerode è possibile valutare le caratteristiche di un linguaggio $L$ costruendo le classi di equivalenza di cui è costituito e stimando il loro numero:

• se il numero di classi di equivalenza è finito, allora esiste almeno un accettore a stati finiti in grado di riconoscere $L$;
• se non è vero che il numero di classi di equivalenza è finito, allora non esiste alcun accettore a stati finiti in grado di riconoscere $L$.

I linguaggi regolari

Il teorema di Myhill - Nerode mette la parola fine alla ricerca delle caratteristiche possedute dai linguaggi riconoscibili dagli automi a stati finiti; è anche grazie a questo risultato che possiamo definire il concetto di linguaggio regolare.

Un linguaggio formale $L$ si dice regolare se e solo se esiste un accettore a stati finiti $M$ in grado di riconoscerlo.

Uso del teorema di Myhill - Nerode

Il teorema di Myhill - Nerode è uno strumento davvero potente, in quanto permette dimostrare sia la regolarità sia la non regolarità dei linguaggi formali. In quest'ultima parte della lezione presentiamo quattro dimostrazioni (due di regolarità, due di non regolarità) che traggono vantaggio dal teorema. Si tratta di applicazioni piuttosto interessanti in quanto permettono di osservare come il teorema stesso possa essere sfruttato nelle dimostrazioni.

Applicazione del teorema ad un linguaggio regolare

Si consideri l'insieme $I=\left\{a,b\right\}$ ed il linguaggio costituito da tutte le stringhe che terminano con il simbolo $b$. Formalmente si può scrivere $L=\left\{wb|w\in I^{*}\right\}$. Vogliamo dimostrare che il linguaggio appena definito è regolare, sfruttando il teorema di Myhill e Nerode. Per raggiungere questo obiettivo è necessario anzitutto identificare le classi di equivalenza dovute al linguaggio. Come si può facilmente intuire vi saranno in tutto due classi di equivalenza:

• una classe è costituita da tutte le stringhe che terminano con il simbolo $a$;
• una classe è composta da tutte le stringhe che terminano con il simbolo $b$.

In tutto ci sono quindi due classi di equivalenza, ossia l'indice della relazione è finito. Per il teorema di Myhill e Nerode, questo significa che il linguaggio in questione è regolare.

Il linguaggio delle stringhe che terminano con la sequenza 00

Consideriamo l'insieme $I=\left\{0,1\right\}$. Tra tutte le possibili stringhe che si possono formare, siamo interessati a quelle che terminano con una coppia di zeri consecutivi. Vogliamo dimostrare che il linguaggio costituito da tali stringhe è un linguaggio regolare. Come in precedenza, identifichiamo le classi di equivalenza indotte dal linguaggio; è facile isolarne 3:

• una classe di equivalenza contiene stringhe $w$ contenenti simboli di $I^{*}$;
• una classe di equivalenza contiene stringhe $w0$, dove la stringa $w$ è costruita come nel punto precedente;
• una classe di equivalenza contiene stringhe $w00$, dove la stringa $w$ è costruita come nel punto precedente.

Dato che le classi di equivalenza sono in numero finito, l'indice della relazione è finito e, per il teorema di Myhill - Nerode, il linguaggio è regolare.

Il linguaggio $a^{n}b^{n}$

Abbiamo già dimostrato, impiegando il pumping lemma, che questo linguaggio formale non è regolare. La presente dimostrazione servirà solo come esercizio, per ribadire il risultato e per mostrare l'impiego del teorema di Myhill - Nerode nel caso dei linguaggi formali non regolari.

Consideriamo due stringhe $a^{m}\in I^{*},a^{n}\in I^{*}$ con $m\in \mathbb {N} ,n\in \mathbb {N} ,m\neq n$ e la stringa $b^{m}\in I^{*}$; concatenando quest'ultima con le due precedenti si ottengono nuove stringhe $a^{m}b^{m}$ e $a^{n}b^{m}$. Si nota immediatamente che $a^{m}b^{m}\in L$, mentre $a^{n}b^{m}\notin L$.

Come conseguenza le due stringhe $a^{m}$ e $a^{n}$ sono distinguibili e devono appartenere a due classi di equivalenza differenti. Per l'arbitrarietà nella scelta dei valori di $m,n$ si può concludere che l'indice della relazione di equivalenza sarà infinito.

Di conseguenza, per il teorema di Myhill - Nerode, il linguaggio in questione non può essere un linguaggio regolare.

Il linguaggio $wcw^{R}$

Procederemo in modo analogo a quanto visto nella sezione soprastante. Consideriamo due stringhe $w'c,w''c$ con $w'\in \left\{a,b\right\}+$ e $w''\in \left\{a,b\right\}+$, in modo che $w'\neq w''$. Consideriamo inoltre una stringa $w'^{R}\in \left\{a,b\right\}+$ scelta in modo che $w'^{R}$ sia la stringa contraria a $w'$.

Formiamo quindi due stringhe $w'cw'^{R}$ e $w''cw'^{R}$; si nota subito che $w'cw'^{R}\in L$ mentre $w''cw'^{R}\notin L$ e, di conseguenza, che le due stringhe sono distinguibili.

Per questo motivo le stringhe apparterranno a due diverse classi di equivalenza e, per l'arbitrarietà con cui sono state scelte $w'ew''$, possiamo concludere che l'indice dell'equivalenza non potrà essere finito.

Per il teorema di Myhill - Nerode, il linguaggio L non potrà essere regolare.

Conclusioni

Sebbene la dimostrazione del teorema di Myhill - Nerode abbia permesso di rispondere ad alcune domande aperte nell'ambito degli automi a stati finiti, curiosamente il suo punto di forza apre un interrogativo che richiederà un supplemento d'indagine: quando l'indice dell'equivalenza riguardante il linguaggio in esame è finito abbiamo la garanzia che esisterà almeno un accettore a stati finiti in grado di riconoscere il linguaggio.

Ciò significa che, in generale, potrebbe esistere più di un accettore a stati finiti in grado di riconoscere il linguaggio $L$; sebbene a livello logico la scelta dell'automa sia indifferente, a livello concreto potrebbero esistere delle differenze prestazionali tra automi diversi ed in questo caso sarebbe interessante disporre di un criterio che ci aiuti a identificare il migliore.

Appuntamento alla prossima lezione.

Lezione precedente: Automa a stati finiti deterministico

Corso: Materia:Informatica Teorica

Prossima lezione: Minimizzazione degli stati di un automa