10.2 EQUIVALENZA TRA ESPRESSIONI REGOLARI, GRAMMATICHE REGOLARI E AUTOMI Sono computazionalmente più potenti gli ASF o gli ASFND? In altre parole, se con L(ASF) indichiamo la classe dei linguaggi riconoscibili con un ASF e con L(ASFND) indichiamo la classe dei linguaggi riconoscibili con un ASFND, che relazione c'è tra L(ASF) e L(ASFND)? Che linguaggi riconoscono gli ASF? Cioè che relazione hanno queste due classi con la classe dei linguaggi generati dai vari tipi di grammatiche di Chomsky?

Teorema. L(ASFND) = L(ASF). Dim. i) L(ASFND) ⊇ L(ASF) La simulazione di un ASF con un ASFND è banale, i due automi sostanzialmente coincidono ii) L(ASF) ⊇ L(ASFND) La simulazione di un ASFND con un ASF sfrutta la finitezza di P(K). Dato un ASFND AN=<Σ,K,δN,q0,F> costruiamo A'=<Σ',K',δ',q0',F'> come segue. Σ' = Σ K' è in corrispondenza biunivoca con 2K i nomi degli stati di K' sono i sottoinsiemi in [ ] K'={[qi1,....,qih] | {qi1,....,qih}∈2K} q0' = [q0] F' è l'insieme dei sottoinsiemi di K che contengono almeno un elemento di F F'={[qi1,....,qik] | {qi1,....,qik}∈2K ∧ {qi1,....,qik}∩F≠∅}

Inoltre: δ'([qi1,....,qih],a) = [qj1,....,qjk] se e solo se δN(qi1,a)∪....∪δN(qih,a) = {qj1,....,qjk} Resta da mostrare che δ'([q0],x)=Q e Q=[qj1,....,qjh] se e solo se δN({q0},x)={qj1,....,qjh} e quindi, in particolare, δ'([q0],x) ∈ F' se e solo se δN({q0},x)∩F≠∅ Ciò è vero per costruzione.

Esempio. ASFND che accetta le stringhe di {a,b}* che terminano con b. Per costruire la funzione di transizione dell'ASF visitiamo gli stati a partire da q0 δ'([q0],a) = [δN(q0,a)] = [q0] δ'([q0],b) = [δN(q0,b)] = [q0,q1] δ'([q0,q1],a) = [δN(q0,a)∪δN(q1,a)] = = [q0] δ'([q0,q1],b) = [δN(q0,b)∪δN(q1,b)] = = [q0,q1] quindi K' = {[q0],[q0,q1]} dato che F = {q1} abbiamo F' = {[q0,q1]}

NOTA BENE. Con il metodo di costruzione introdotto l'ASF può (ma non è detto) avere un numero esponenziale di stati rispetto all'ASFND di partenza. Gli ASFND sono ugualmente espressivi ma più succinti degli ASF. Esempio. Automi che riconoscono le stringhe di (a+b)*b(a+b) o di (a+b)*b(a+b)(a+b) NOTA BENE. Generalizzando a stringhe del tipo (a+b)*b(a+b)k, si passa da k+2 stati (ASFND) a O(2k) stati (ASF).

Che tipo di linguaggi riconoscono gli ASF ed ASFND? Teorema. Le seguenti classi di linguaggi sono equivalenti: L(ER): linguaggi definiti da espressioni regolari, L(ASF): linguaggi riconosciuti da ASF, L(GR): i linguaggi generati da grammatiche regolari (linguaggi regolari). Dim. i) L(ASF)⊇L(ER) Questo risultato può essere dimostrato facendo vedere che i linguaggi rappresentati da espressioni regolari sono riconoscibili con ASFND e sfruttando il fatto che le classi L(ASFND) ed L(ASF) coincidono.

Supponiamo dato l'alfabeto Σ={a,b}. La dimostrazione si effettua per induzione sulla struttura delle espressioni regolari e cioè facendo vedere che: • i linguaggi rappresentati dalle ER a, b e Λ sono riconoscibili con ASFND ed inoltre, se sono riconoscibili con ASFND i linguaggi rappresentati dalle ER e, e1 ed e2 allora anche • il linguaggio rappresentato dalla ER (e1+e2) • il linguaggio rappresentato dalla ER (e1.e2) • il linguaggio rappresentato dalla ER e* sono riconoscibili con ASFND.

La costruzione degli automi per i linguaggi Λ, {a} e {b} è banale. Per i linguaggi definiti utilizzando gli operatori +, . , e *, possiamo mostrare i seguenti lemmi.

Lemma 1. Siano dati due ASFND A1 ed A2. Esiste un ASFND che riconosce L(A1) ∪ L(A2). Dim. Siano A1=<Σ1,K1,δN1,q01,F1> ed A2=<Σ2,K2,δN2,q02,F2> i due automi che riconoscono i linguaggi L(A1) ed L(A2) L'automa che riconosce L(A1) ∪ L(A2) e' l'automa A=<Σ,K,δN,q0,F> dove: Σ=Σ1∪Σ2 K=K1∪K2∪{q0} con q0 nuovo stato iniziale F=F1∪F2 oppure F=F1∪F2∪{q0} se A1 o A2 riconosce la stringa vuota δN(q,a) = δN1(q,a) se q∈K1 a∈Σ1 δN(q,a) = δN2(q,a) se q∈K2 a∈Σ2 δN(q0,a) = δN1(q01,a)∪δN2(q02,a) a∈Σ NOTA BENE. L'automa risultante potrebbe non essere deterministico anche se lo sono A1 e A2

Lemma 2. Siano dati due ASFND A1 ed A2. Esiste un ASFND che riconosce L(A1) ° L(A2). Dim. Dati gli automi A1=<Σ1,K1,δ1,q01,F1> ed A2=<Σ2,K2,δ2,q02,F2> che riconoscono L(A1) e L(A2), l'ASFND che riconosce il linguaggio L(A1)°L(A2) e' l'automa <Σ,K,δ,q0,F> dove: Σ = Σ1∪Σ2 K = K1∪K2 se ε∉L(A2) allora F = F2 altrimenti F= F1∪F2 q0 = q01 δN(q,a)=δ1(q,a) se q∈K1-F1 e a∈Σ1 δN(q,a)=δ1(q,a)∪δ2(q02,a) se q∈F1e a∈Σ δN(q,a)=δ2(q,a) se q∈K2 e a∈Σ2

Lemma 3. Sia dato un ASFND A. Esiste un ASFND che riconosce L(A)*. Dim. Dato l'automa A = <Σ,K,δ,q0,F> che riconosce L(A). L'ASFND che riconosce il linguaggio L(A)* e' l'automa A' = <Σ,K∪{q0'},δ',q0',F∪{q0'}> δ'(q,a) = δ(q,a) se q∈K-F δ'(q,a) = δ(q,a)∪δ(q0,a) se q∈F δ'(q0',a) = δ(q0,a)

Torniamo ora all'equivalenza dei formalismi per la definizione dei linguaggi regolari. ii) L(GR)⊇L(ASF) Sia dato un automa A = <Σ,K,δ,q0,F>. La grammatica corrispondente è la grammatica G=<VT, VN, P, S> dove: VT = Σ VN = {Ai | per ogni qi∈K} S = A0 Per ogni regola di transizione δ(qi,σ) = qj costruiamo la produzione Ai→σAj e se qj∈F anche Ai→σ. Inoltre, se q0∈F (ε appartiene al linguaggio) inseriamo in VN anche A0' e per ogni A0→aAi aggiungiamo le regole A0'→aAi e A0'→ε. In tal caso l'assioma diventa A0'.

Per verificare che la costruzione è corretta dobbiamo dimostrare che esiste la derivazione Ai⇒∗xAj se e solo se δ(qi,x) = qj e che esiste la derivazione Ai⇒∗x se e solo se δ(qi,x) = qj e qj∈F. Quindi in particolare la grammatica genera la stringa x se e solo se l'automa la riconosce (δ(q0,x) = qj e qj∈F). La prova consiste di due parti: - prima parte (⇒): se x è riconosciuta dall'automa A allora essa è generata dalla grammatica G - seconda parte (<=): se x è generata dalla grammatica G allora essa è riconosciuta dall'automa A. Dimostriamo solo la prima parte. La prova può essere effettuata per induzione sulla lunghezza della stringa x.

Se |x|=1 allora sia x=a, supponiamo sia δ(qi,a) = qj allora per costruzione Ai→aAj e

se qj∈F abbiamo Ai→a Se x=ya e |y|=n≥1 allora se il risultato è valido

per y è valido anche per x; infatti se δ(qi,ya) = δ(δ(qi,y),a) = qj e δ(qi,y) = qk, per ipotesi induttiva Ai⇒∗yAk e per costruzione Ak→aAj (se qj∈F anche Ak→a);

quindi Ai⇒∗yaAj=xAj ed, eventualmente, Ai⇒∗x

Nel caso che q0∈F ed ε∈L usiamo A0'⇒ε

iii) L(ER)⊇L(GR) (accenno di dimostrazione) Sia data una grammatica G=<VT, VN, P, S>. Inizialmente, supponiamo per semplicità che il linguaggio non contenga ε. Possiamo costruire l'espressione regolare che rappresenta L(G) nel seguente modo. 1. Si trasforma la grammatica in un sistema di equazioni sul monoide sintattico, contenenti simboli terminali e variabili (le variabili assumono valore sull'insieme delle espressioni regolari). Ogni equazione è del tipo: <variabile>=<espressione regolare estesa> dove una espressione regolare estesa è una espressione regolare in cui al posto di simboli terminali possiamo avere variabili. Ad esempio: A = (a+bA)* + bb.

Per impostare il sistema procediamo nel seguente modo: • raggruppiamo le produzioni che hanno lo stesso non terminale a sinistra • ad ogni produzione A → a1B1|a2B2|....|anBn|b1|b2|....|bm associamo l'equazione A = a1B1+a2B2+....+anBn+b1+b2+....+bm NOTA BENE. Il sistema ottenuto è composto da equazioni lineari destre, con monomi dalla struttura semplice.

Esempio. Alla grammatica A → aA|bB B → bB|c corrisponde il sistema A = aA+bB B = bB+c

2. Si risolvono le equazioni mediante • sostituzione, ad esempio, date A = aA + bB + c B = aA + c otteniamo A = aA + b(aA + c) + c B = aA + c che semplificando diviene: A = (a + ba)A + bc+ c B = aA + c

• eliminazione della ricursione (punto fisso), ad esempio, data l'equazione A = aA + b la soluzione e' A = a*b. NOTA BENE. Sostituendo otteniamo a*b = a(a*b)+b = a+b+b = a*b Più in generale, se le αi e le βi sono a loro volta espressioni regolari estese: A = α1A+α2A+....+αnA+β1+β2+....+βm (A non occorre in αi e βi) si risolve con A = (α1+α2+....+αn)*(β1+β2+....+βm)

In conclusione, applicando le regole di sostituzione ed eliminazione della ricursione possiamo risolvere ogni sistema di equazioni lineari destre → quindi possiamo determinare il linguaggio associato alla variabile corrispondente all'assioma. → quindi possiamo determinare l'espressione regolare che descrive il linguaggio generato dalla grammatica data.

Esempio. Sia data la grammatica con assioma A che genera il linguaggio delle stringhe che contengono un numero pari, diverso da 0, di a: A →bA | aB | b B →aA | bB | a A = bA + aB + b B = bB + aA + a Si elimina la ricursione nella seconda equazione B = b*(aA + a) si sostituisce nella prima A = bA + ab*(aA + a) + b si semplifica A = bA + ab*aA + ab*a + b si fattorizza A = (ab*a+b)A + ab*a + b e si elimina di nuovo la ricursione A = (ab*a+b)*(ab*a + b) = (ab*a+b)+.

Esempio. La grammatica regolare S → aS|bA|ε A → aA|bS|ε può essere modificata rimuovendo le ε-produzioni che non sono sull'assioma S → aS|bA|ε|b A → aA|bS|a L'espressione regolare equivalente può essere costruita nel seguente modo: A = aA+(bS+a) A = a*(bS+a) S = aS+bA+b+ε S = aS+b(a*(bS+a))+b+ε S = aS+ba*bS+ba*a+b+ε S = (a+ba*b)S+ba*a+b+ε S = (a+ba*b)*(ba*a+b+ε) S = (a+ba*b)*(ba*a+b) + (a+ba*b)*

10.3 PROPRIETA’ DI CHIUSURA E ‘PUMPING LEMMA’ PER I LINGUAGGI REGOLARI Proprietà fondamentale dei linguaggi regolari Teorema. Per ogni linguaggio regolare L esiste una costante n tale che se z∈L e |z|≥n allora esistono tre stringhe u, v, w, tali che z=uvw con |uv|≤n, |v|≥1 e uviw∈L, i=0,1,.... Dim. Basata sui cicli (eventuali) del diagramma degli stati.

Supponiamo che A=<Σ,K,δ,q0,F> sia l'ASF che riconosce L con il minimo numero di stati. Sia n=|K|. Supponiamo esista z∈L con |z|≥n (se no il teorema e' banale) Abbiamo che δ(q0,z)∈F Sia qi0, qi1,....,qi|z| la sequenza di stati attraversati da A durante il riconoscimento di z, qi0=q0 e qi|z|∈F Dato che |z|≥n, allora esiste almeno uno stato attraversato 2 volte (in base al pigeonhole principle!). Consideriamo un prefisso t di z tale che |t|=n e sia ty = z. Anche durante la scansione di t esiste almeno uno stato che viene attraversato due volte. Sia j il minimo indice tale che qij è attraversato 2 volte, sia u il più breve prefisso di t (e di z) tale che δ(q0,u)= qij e sia t=ux.

Sia ora v il più breve prefisso (non vuoto) di x tale che δ(qij,v)= qij e sia t = uvs e z = uvw. In base alle ipotesi fatte abbiamo che |uv|≤|t|=n Poiche' δ(q0,u) = qij e δ(qij,w) = qi|z| abbiamo che, δ(q0,uw) = qi|z|, quindi uw ∈ L inoltre, se i≥1: δ(q0,uviw) = δ(δ(q0,u),viw) = δ(qij,viw) = δ(δ(qij,v),vi-1w) = δ(qij,vi-1w) = .... = δ(qij,w) = qi|z| e quindi anche uviw ∈ L per ogni i.

NOTA BENE. Il "pumping lemma" consente di mostrare in modo ragionevolmente rapido la non regolarità di un linguaggio dato Esempio. Il linguaggio L={anbn| n≥0} non è regolare. Infatti, per il pumping lemma, per stringhe sufficientemente lunghe, se L contiene anbn=uvw dovrebbe contenere uviw i=1,2,3,4,.... • se v=ah allora L dovrebbe contenere am-hahibm • se v=bh allora L dovrebbe contenere ambhibm-h • se v=ahbk allora L dovrebbe contenere am-h(ahbk)ibm-k In tutti e tre i casi si tratta di stringhe che non fanno parte di L.

Esercizio. Dimostrare mediante il "pumping lemma" che il linguaggio delle stringhe palindrome di lunghezza pari non è regolare. NOTA BENE. Nella dimostrazione precedente assume un valore fondamentale il fatto che nel "pumping lemma" si dimostri anche che per le stringhe u e v vale |uv| ≤ n, cioè che la stringa che viene "pompata" sia relativamente vicina all'inizio. Esercizio. Dimostrare che il linguaggio delle stringhe palindrome ed il linguaggio delle stringhe palindrome di lunghezza pari non sono regolari.

Con la stessa tecnica del pumping lemma possiamo dimostrare come esercizio i due seguenti risultati: Teorema. Se il linguaggio L riconosciuto da un ASF con n stati non è vuoto esiste una stringa x in L di lunghezza |x| < n. Teorema. Se il linguaggio L riconosciuto da un ASF con n stati è infinito esiste una stringa x in L di lunghezza n ≤|x|<2n. I risultati precedenti ci dicono che è possibile decidere se un linguaggio regolare è • vuoto, • finito, • infinito.

Proprietà di chiusura dei linguaggi regolari Abbiamo visto in precedenza che l'insieme dei linguaggi regolari è chiuso rispetto a: • unione • concatenazione • iterazione. Teorema. L'insieme dei linguaggi regolari su Σ è il più piccolo insieme contenente Λ e {σi}, σi∈Σ, che sia chiusa rispetto a unione, concatenazione e iterazione.

La classe dei linguaggi regolari è chiusa anche rispetto alla complementazione Teorema. Il complemento di un linguaggio regolare e' regolare Dim. Dato l'ASF A=<Σ,K,δ,q0,F> che riconosce L, l' ASF che riconosce il linguaggio complementare è l'automa A'=<Σ,K,δ,q0,K-F> Ogni stringa che porta A in uno stato finale porta A' in uno stato non finale, per cui L(A')=Σ*-L(A) Corollario. La classe dei linguaggi regolari è chiusa rispetto all'intersezione. Dim. Banale sfruttando la chiusura rispetto a unione e complementazione e usando la legge di De Morgan

Come ulteriore conseguenza delle proprietà di chiusura e delle proprietà derivanti dal pumping lemma possiamo dimostrare che per le grammatiche regolari (ed ovviamente anche per espressioni regolari, ASF ed ASFND) è decidibile l'equivalenza. Si noti che per altre classi di linguaggi (ad esempio per i linguaggi CF) tale proprietà non è decidibile. Teorema. Dati due automi A1=<Σ1,K1,δ1,q01,F1> e A2=<Σ2,K2,δ2,q02,F2> è possibile decidere se L(A1) = L(A2)

Dim. Si può facilmente mostrare, prima di tutto, che i lingaggi regolari sono chiusi rispetto alla differenza simmetrica; infatti se indichiamo con Δ la differenza simmetrica di L(A1) ed L(A2) abbiamo: Δ(L(A1), L(A2)) = L(A1)\L(A2)∪L(A2) \L(A1) dove S\Z, cioè la differenza tra due insiemi S e Z, può essere espressa come l’intersezione di S con il complemento di Z. Successivamente possiamo osservare che L(A1)=L(A2) se e solo se Δ(L(A1), L(A2)) è vuoto.

NOTA BENE. Un'ulteriore conseguenza dei risultati precedenti è che per gli ASF esiste un algoritmo banale di minimizzazione del numero degli stati: dato un ASF con n stati, infatti, è sufficiente enumerare tutti gli automi con 1, 2, ..., n-1 stati e verificare se sono equivalenti a quello dato. Un algoritmo meno banale e più efficiente per la minimizzazione del numero degli stati di un ASF si può trovare sul libro di testo.

Teorema di Myhill - Nerode Dato un linguaggio L consideriamo la relazione di equivalenza su Σ*:

x RL y ⇔ (∀z∈Σ* xz∈L ⇔ yz∈L) Teorema. L è regolare se e solo se RL ha indice finito, cioè il numero di classi di equivalenza della relazione è finito.

Dim. La dimostrazione si articola in due parti. Se L è regolare dimostriamo che RL ha indice finito costruendo una relazione di equivalenza più fine di RL e dimostrando che la nuova relazione ha indice finito. Se RL ha indice finito dimostriamo che L è regolare costruendo un automa che riconosce L.

i) L regolare -> RL indice finito Costruiamo l'ASF A=<Σ,K,δ,q0,F> che riconosce L e definiamo una nuova relazione binaria RM su Σ*

x RM y ⇔ δ(q0,x)=δ(q0,y) cioè, due stringhe sono equivalenti se portano nello stesso stato di K a partire da q0 • RM ha indice finito, pari, al più a |K| • se x RM y allora ∀z∈Σ* xz RM yz, infatti se δ(q0,x)=δ(q0,y) allora anche δ(q0,xz)=δ(q0,yz) • se x RM y allora x RL y, infatti se δ(q0,x)=δ(q0,y) allora anche δ(q0,xz)=δ(q0,yz) e quindi xz∈L ⇔ yz∈L Quindi l'indice di RL è minore o uguale dell'indice di RM a sua volta finito

ii) RL indice finito -> L regolare Definiamo un automa che riconosce L. Ad ogni classe [x] della relazione RL associamo lo stato q[x] Poniamo q0=q[ε] F = {q[x]| x∈L} d(q[x],σ)=q[xσ] L'automa riconosce L che quindi è regolare.

NOTA BENE Il teorema di Myhill-Nerode fornisce una ulteriore importante caratterizzazione dei linguaggi regolari e può anch’esso essere usato per verificare se un linguaggio è o non è regolare. Infatti se si verifica che per un dato linguaggio L la relazione RL non ha indice finito si può dedurre che L non è un linguaggio regolare. Esercizio. Dimostrare che il linguaggio L = {anbn | n ≥ 1} non è regolare utilizzando il teorema di Myhill-Nerode.