Dispensa di Sintassi

Strumenti per la Definizione della Sintassi dei

Linguaggi di Programmazione1

Docente: Luca Tesei

Scuola di Scienze e TecnologieUniversita di Camerino

Anno Accademico 2012/2013

1Queste note intendono coprire gli argomenti della prima parte del modulo diProgrammazione 2012/2013, corso di Programmazione + Laboratorio, corso di Lau-rea in Informatica, Universita di Camerino, sede di Camerino. Alcuni esempi sonotratti dal libro “Compilers: Principles, Techniques, and Tools” di Alfred V. Aho,Ravi Sethi e Jeffrey D. Ullman, Addison-Wesley Pub

Indice

1 Linguaggi formali 51.1 Stringhe e linguaggi . . . . . . . . . . . . . . . . . . . . . . . 51.2 Operazioni sulle stringhe . . . . . . . . . . . . . . . . . . . . . 61.3 Operazioni sui linguaggi . . . . . . . . . . . . . . . . . . . . . 71.4 Espressioni su insiemi . . . . . . . . . . . . . . . . . . . . . . 8

2 Automi a stati finiti 112.1 Automi non deterministici . . . . . . . . . . . . . . . . . . . . 112.2 Automi finiti deterministici . . . . . . . . . . . . . . . . . . . 152.3 Costruzione dei sottoinsiemi . . . . . . . . . . . . . . . . . . . 162.4 Minimizzazione di un DFA . . . . . . . . . . . . . . . . . . . . 202.5 Progettazione di un automa . . . . . . . . . . . . . . . . . . . 21

3 Induzione e ricorsione 273.1 Ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 Costruzione induttiva . . . . . . . . . . . . . . . . . . . . . . 283.3 Chiamate ricorsive . . . . . . . . . . . . . . . . . . . . . . . . 303.4 Definizioni per induzione . . . . . . . . . . . . . . . . . . . . . 36

3.4.1 Espressioni regolari . . . . . . . . . . . . . . . . . . . . 363.5 Ragionamento induttivo . . . . . . . . . . . . . . . . . . . . . 39

4 Grammatiche libere dal contesto 434.1 Grammatiche libere dal contesto . . . . . . . . . . . . . . . . 444.2 Alberi di derivazione . . . . . . . . . . . . . . . . . . . . . . . 464.3 Scrittura di grammatiche . . . . . . . . . . . . . . . . . . . . 514.4 Ambiguita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.5 Associativita e precedenza degli operatori . . . . . . . . . . . 56

3

4 INDICE

Capitolo 1

Linguaggi formali

Cominciamo con alcune nozioni di base sui linguaggi formali. Nei capito-li successivi vedremo diversi formalismi per specificarli e tratteremo anchedella loro potenza espressiva.

1.1 Stringhe e linguaggi

Introduciamo alcune convenzioni che serviranno da qui in poi. I terminialfabeto o classe di caratteri denotano un qualsiasi insieme finito di simboli.Ad esempio l’insieme 0, 1 e l’alfabeto binario. ASCII e Unicode sonoesempi di alfabeti molto utilizzati nei computer. In genere useremo Σ (o inalcuni testi ed esercizi Λ) per denotare un alfabeto.

Una stringa su un alfabeto e una sequenza finita di simboli presi dall’alfa-beto. Nell’ambito della teoria dei linguaggi i termini “parola” o “frase” sonosinonimi di “stringa”. Stringhe generiche verranno nel seguito indicate con levariabili s, s′, s′′, . . . , s0, s1, s2, . . . oppure x, y, z, w, . . . , x′, x′′, . . . , x0, x1, . . .La lunghezza di una stringa s verra indicata con |s| ed e il numero di simbo-li che costituiscono la sequenza s. Ad esempio, banana e una stringa lunga6. La stringa vuota e denotata con ǫ (o, in alcuni testi ed esercizi, λ) eha lunghezza 0. Essa e un’astrazione matematica che serve a denotare unastringa a tutti gli effetti, ma che non contiene nessun carattere. La stringavuota e utile e comoda in molte definizioni ed e necessaria per definire lestringhe, i linguaggi e le loro operazioni come algebre che hanno una loroteoria matematica.

I seguenti sono altri termini usati frequentemente nel contesto dellestringhe e dei linguaggi, con le relative definizioni:

• Prefisso di s Una stringa ottenuta togliendo zero o piu simboli dallafine di s. Es. ban e prefisso di banana.

• Suffisso di s Una stringa ottenuta togliendo zero o piu simboli dallatesta di e. Es. nana e suffisso di banana.

5

6 CAPITOLO 1. LINGUAGGI FORMALI

• Sottostringa di s Una stringa ottenuta togliendo da s sia un suosuffisso che un suo prefisso. Es. ana e una sottostringa di banana. Sinoti che ogni prefisso o suffisso di s e anche una sottostringa di s (manon e vero il contrario). Si noti anche che s stessa e anche suo prefisso,suffisso e sottostringa.

• Prefisso, suffisso e sottostringa propri di s Una qualsiasi stringanon vuota x che sia, rispettivamente, un prefisso, un suffisso o unasottostringa di s e tale che s 6= x.

• Sottosequenza di s Una qualsiasi stringa ottenuta cancellando zeroo piu caratteri, non necessariamente contigui, da s. Es. baaa e unasottosequenza di banana.

Il termine linguaggio denota un qualsiasi insieme (finito o infinito) distringhe su un certo alfabeto fissato Σ. Questa definizione e molto generale:ad esempio l’insieme vuoto (∅ o ) e un linguaggio (chiamato linguaggiovuoto) secondo questa definizione. Un altro linguaggio particolare e il lin-guaggio ǫ (o λ), che contiene una sola stringa, la stringa vuota. Altriesempi possono essere: tutti i programmi Pascal sintatticamente ben formatio addirittura tutte le frasi in italiano che sono grammaticalmente corrette.Tuttavia c’e subito da notare che quest’ultimo linguaggio e molto difficileda definire precisamente, mentre altri linguaggi non banali possono esseredefiniti matematicamente (come faremo noi con i linguaggi di programma-zione tramite le grammatiche). Come ultima cosa si noti che la definizioneche abbiamo dato non richiede che sia associato nessun significato partico-lare alle stringhe del linguaggio. La disciplina che si occupa dei metodi perdare significato alle stringhe di un linguaggio viene chiamata generalmentesemantica. Vedremo uno di questi metodi nella seconda parte del corso.

1.2 Operazioni sulle stringhe

Definiamo una operazione fondamentale tra stringhe. Se x e y sono duestringhe, allora la concatenazione di x ed y, scritta come x ·y1, e una stringaottenuta attaccando y in fondo a x. Es. x = buon e y = giorno x · y =buongiorno. La concatenazione puo essere vista come l’analogo del prodottonell’ambito delle stringhe. L’elemento neutro per la concatenazione e lastringa vuota: ǫ · s = s · ǫ = s per ogni stringa s.

Se pensiamo alla concatenazione come ad un prodotto, possiamo definirel’analogo dell’elevamento a potenza come segue:

• s0 = ǫ per ogni stringa s

• si = s · si−1 per ogni stringa s e per ogni i > 0

1Come per la moltiplicazione fra numeri spesso il · viene omesso.

1.3. OPERAZIONI SUI LINGUAGGI 7

Ad esempio otto0 = ǫ, otto1 = otto, otto2 = ottootto, otto3 =ottoottootto. Si noti, inoltre, che anche una singola lettera e una stringa(lunga 1) e quindi l’elevamento a potenza puo essere usato anche in espres-sioni del tipo an. Specificando il valore di n otteniamo una stringa di tuttea lunga n: a0 = ǫ, a1 = a, a2 = aa, a3 = aaa, . . .

1.3 Operazioni sui linguaggi

Ci sono diverse importanti operazioni che possono essere applicate ai lin-guaggi. Per quanto riguarda questo corso ci limiteremo a considerare leseguenti:

• Unione L1 ∪ L2 = s | s ∈ L1 o s ∈ L2

• Concatenazione L1 · L2 = s1s2 | s1 ∈ L1 e s2 ∈ L22

• Esponenziazione L0 = ǫ, Li = L · Li−1 se i > 0

• Chiusura (o stella) di Kleene L∗ =⋃∞

i=0Li = L0 ∪ L1 ∪ L2 ∪ L3 ∪ · · ·

• Chiusura (o stella) positiva di Kleene L+ =⋃∞

i=1Li

Esempio 1.1 Sia L l’insieme A,B, . . . , Z, a, b, . . . , z e D l’insieme0, 1, . . . , 9. L e D possono essere visti in due modi: come alfabeti finiti ocome linguaggi (finiti) composti da parole che sono tutte lunghe un carattere.Vediamo alcuni linguaggi che possono essere definiti a partire da L e Dtramite le operazioni che abbiamo appena introdotto:

• L ∪D e l’insieme delle lettere e delle cifre

• LD e l’insieme di tutte le stringhe di lunghezza 2 formate da unalettera seguita da una cifra

• L4 contiene tutte le stringhe di lunghezza 4 che sono formate da lettere

• L∗ e un insieme infinito di stringhe ognuna delle quali ha una lun-ghezza finita ed e composta da lettere. Questo linguaggio contiene, perdefinizione, anche la stringa vuota ǫ.

• L(L ∪ D)∗ e l’insieme di tutte le stringhe di lunghezza strettamentemaggiore di 0, che iniziano con una lettera e sono composte, dopo laprima lettera, da cifre o lettere.

• D+ e l’insieme di tutte le stringhe di cifre formate da almeno una cifra

2Anche qui il · e spesso omesso.


Si noti che la stella di Kleene, in entrambe le sue versioni, puo, e losara spesso, essere applicata ad alfabeti. Infatti gli alfabeti possono esserevisti come linguaggi molto semplici: insiemi finiti di stringhe di lunghezza1. In questi casi, secondo la definizione, dato in generale un certo alfabetonon vuoto Σ, Σ∗ rappresenta tutte le stringhe di lunghezza finita, compresaquella vuota, che si possono formare usando i simboli di Σ. Σ∗ e sempre uninsieme infinito, ma che contiene parole di lunghezza finita. Inoltre Σ+ =Σ∗ − ǫ.

Esempio 1.2 Sia Σ = 0, 1. Si ha che

Σ∗ = ǫ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, . . .

Σ+ = 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, . . .

Sia ora Σ = a, b, c. Si ha che

Σ∗ = ǫ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, abc, . . .

Σ+ = a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb, abc, . . .

Tramite queste nuove nozioni possiamo dare una definizione piu precisadi linguaggio.

Definizione 1.3 (Linguaggio) Dato un alfabeto non vuoto Σ, un linguag-gio su Σ e un qualsiasi sottoinsieme di Σ∗: L ⊆ Σ∗.

Abbiamo gia visto i linguaggi banali ∅ e ǫ. Un altro linguaggio banale suΣ e Σ∗.

1.4 Espressioni su insiemi

In questa sezione vediamo un modo per specificare matematicamente alcunilinguaggi formali. Questo tipo di notazione sara presente in tutto il corso.

Un modo banale di scrivere un linguaggio e semplicemente quello dielencare le stringhe che lo compongono fra parentesi graffe. Questo metodopero e molto limitato, infatti puo essere usato solo per scrivere linguaggifiniti, cioe che contengono un numero finito di stringhe. In questo corso ilinguaggi che useremo sono invece quasi sempre infiniti.

Il mezzo piu generale per dare una specifica precisa di molti linguaggiinfiniti e rappresentato dalle espressioni su insiemi. Questo tipo di notazionee naturale poiche, effettivamente, i linguaggi formali non sono altro cheinsiemi di stringhe.

Un’espressione su insiemi non e altro che la classica notazione usata perrappresentare analiticamente gli elementi di un insieme:

1.4. ESPRESSIONI SU INSIEMI 9

x ∈ U | P (x)

dove U e un universo di oggetti dato a priori e P un predicato, una proprieta,che caratterizza tutti e soli gli elementi che fanno parte dell’insieme (cioequegli x per cui P (x) e vero).

Nel contesto dei linguaggi formali l’universo U e sempre Σ∗, dove Σ el’alfabeto dal quale si prendono i simboli per formare le parole del linguaggioche si sta definendo. Poiche Σ e spesso specificato preliminarmente e chiarodal contesto, spesso l’universo viene sottinteso e la scrittura diventa x |P (x).

La proprieta P puo venire specificata tutta dopo il simbolo |, anche sespesso, specialmente nel campo della definizione di linguaggi, la strutturadelle parole viene specificata parzialmente anche prima del simbolo |.

Per specificare la struttura possiamo usare i simboli di Σ, le operazionisu stringhe, le espressioni regolari (vedi Sezione 3.4.1), le operazioni suilinguaggi e diverse variabili. Vediamo diversi esempi che illustrano i diversimodi di usare queste notazioni.

L = an b c | n > 0

In questo caso inferiamo che Σ = a, b, c e che le parole del linguaggiosono tutte quelle che iniziano con una sequenza di a lunga almeno 1 (n > 0)e che poi continuano esattamente con una b seguita da una c. Esempi diparole del linguaggio: abc, aabc, aaabc, aaaabc, . . .. Esempi di parole che nonappartengono al linguaggio: ǫ, bc, aabac, aaaaa, aab, . . .

L = an b∗ cn | n ≥ 0

In questo caso abbiamo usato anche l’espressione regolare b∗ che e equi-valente al linguaggio b∗ (vedi Sezione 3.4.1). Il significato dei due espo-nenti n e quello usuale, cioe che in tutte le parole il numero di a e dic deve essere lo stesso e maggiore o uguale a zero (n ≥ 0). All’inter-no delle a e delle c c’e una sequenza di b lunga anche zero (b∗ con-tiene sempre ǫ). Esempi di parole nel linguaggio: ǫ (quando n = 0 eb∗ = ǫ), ac, aacc, abc, aabcc, aabbbbbcc, b, aaabccc, . . . Esempi di parole chenon appartengono al linguaggio: ab, aaabcc, abac, bbbccc, abccc, . . .

L = an (bb)m ck | n,m ≥ 0, k > 0

Questo linguaggio potrebbe essere scritto anche come a∗(bb)∗c+3 o comea∗ b2m ck | m ≥ 0, k > 0. Le variabili n,m e k non sono legate l’una all’al-tra da nessun vincolo. Esempi di parole: aaabbc, bbc, c, ccc, aaaaabbbbccc, . . .

3In tutti questi casi, e anche nel seguito, l’asterisco e il +, operatori delle espressioniregolari (Sezione 3.4.1), vanno sempre intesi come la stella di Kleene o il + sul linguaggioche contiene solo la stringa base: (bb)∗ = bb∗, c+ = c+


L = an bm ck | n,m > 0, k = m+ n

In questo caso le variabili n,m, k sono interdipendenti. Il vincolo k =m + n indica che la somma fra il numero di a e il numero di b deve essereuguale al numero di c in ogni parola del linguaggio. Esempi: aabbbccccc, abcc,abbbbbcccccc, . . . Esempi di parole non del linguaggio: c, abc, aabb, cc, . . .

L1 = an b c+ | n > 0L = dx an | x ∈ L1, n ≥ 0

Qui abbiamo usato un sottolinguaggio L1 per definire un altro linguaggioprincipale L. Il linguaggio L ha parole che cominciano con una d seguita dauna qualsiasi parola del linguaggio L1 seguita a sua volta da una sequenzadi a anche vuota. Si noti che la variabile n in L1 e quella in L non hannonessun rapporto tra di loro, poiche hanno scope diverso, cioe il loro significatoe circoscritto all’interno delle parentesi graffe di ognuna delle due espressioniinsiemistiche che le usano. Esempi: daabccccaaaaaaaa, dabc, daabccca, . . ..Non appartenenti: ǫ, dbcaaa, daab, aaabcaaaa, . . .

L = s1 d s2 · · · sk d | k > 0, si ∈ a, b, c∗∀i ∈ 1, . . . , k

Abbiamo usato, in questo esempio, una sequenza numerata di varia-bili che denotano stringhe (si) ognuna delle quali puo essere una stringaqualunque di un altro linguaggio, a, b, c∗ (potevamo usare anche un sot-tolinguaggio come nell’esempio precedente). Dato che k > 0 allora alla finedi ogni si deve essere presente una d.

Esempi di stringhe appartenenti:aabbcd, d, dddd, aacdaabbdbcabdabacd, . . .

Esempi di stringhe non appartenenti: abcac, bcdabac, . . ..Infine, vedremo che spesso i linguaggi che specificheremo sono divisi per

“casi”, cioe il linguaggio che vogliamo descrivere risulta dall’unione di diversilinguaggi componenti ognuno dei quali rappresenta un caso. In questo casoe sufficiente utilizzare la normale unione insiemistica. Ad esempio:

L = an b c | n > 0 ∪ bn c a | n ≥ 0 ∪ d+ (c|b) am | m > 0

Si noti che la n del primo insieme e la n del secondo, ancora una vol-ta, non hanno nessun rapporto: una qualsiasi potrebbe essere rinominatasenza cambiare il linguaggio definito. Si noti inoltre che nell’ultimo in-sieme abbiamo usato l’or delle espressioni regolari4. Esempi di stringhe:abc, bca, ca, dc, ddb, . . .

4(c|b) indica o una c o una b (vedi Sezione 3.4.1).

Capitolo 2

Automi a stati finiti

In questo capitolo definiamo gli automi a stati finiti non deterministici edeterministici. Essi sono dei riconoscitori di stringhe di un certo linguag-gio. Dopo la definizione degli automi vedremo un algoritmo importante: lacostruzione dei sottoinsiemi per trasformare un automa non deterministicoin deterministico.

2.1 Automi non deterministici

Definiamo la classe degli automi finiti non deterministici NFA (dall’ingleseNon-deterministic Finite Automata).

Un NFA puo essere specificato graficamente tramite un grafo diretto1

in cui i nodi, disegnati come cerchi, vengono chiamati ‘stati’ (generalmentenumerati), le frecce etichettate sono transizioni, lo stato iniziale e il nodoche ha una freccia entrante (con opzionalmente scritto start) e gli stati finalisono i nodi che hanno una doppia cerchiatura. Ogni freccia deve essereetichettata da un simbolo di un alfabeto finito Σ o da un insieme di simbolidi Σ. Le transizioni di quest’ultimo tipo sono un’abbreviazione che denotaun insieme di transizioni, tutte con la stessa sorgente e la stessa destinazione,etichettate ognuna con un simbolo diverso dell’insieme.

Un esempio di NFA si trova in Figura 2.1. L’automa ha 4 stati: 0, 1, 2, 3,Σ = a, b, lo stato iniziale e 0 e l’unico stato finale e lo stato 3. Le frec-ce rappresentano le transizioni: ad esempio la freccia etichettata a, b cheparte dallo stato 0 e va nello stato 0 rappresenta due transizioni: una eti-chettata con a, l’altra con b, tali che entrambe che partono da 0 e ritornanoin 0 (questo tipo di transizioni vengono chiamate anche self-loop). Esisteun’altra transizione uscente dallo stato 0 ed etichettata con a, ma e diversadalla precedente poiche lo stato di destinazione e 1.

1Cioe un diagramma formato da diversi punti o nodi collegati da frecce. Se il grafonon e diretto allora i nodi sono collegati da semplici linee.

11

12 CAPITOLO 2. AUTOMI A STATI FINITI

start a b1 2 30b

a,b

Figura 2.1: Un NFA.

Piu formalmente possiamo definire gli NFA nel modo seguente. Sia Σun alfabeto finito.

Definizione 2.1 (NFA) Un NFA su Σ e una tupla 〈S,Σ,move , s0, F 〉 do-ve:

• S e un insieme finito di stati

• Σ e l’alfabeto dei simboli

• s0 ∈ S e lo stato iniziale

• F ⊆ S e l’insieme degli stati di accettazione o stati finali

• move : (S × Σ) −→ ℘(S) e una funzione che specifica per ogni stato se per ogni simbolo x di Σ le transizioni etichettate x dallo stato s adun insieme, anche vuoto, di stati di destinazione (c’e una transizioneper ogni stato di destinazione).

Il simbolo ℘(S), usato nella definizione, rappresenta l’operazione di ‘po-werset’ su un insieme S. Tale operazione restituisce un insieme contenentetutti i sottoinsiemi di S. Ad esempio: ℘(a, b) = , a, b, a, b.

Nell’automa in Figura 2.1 S e l’insieme 0, 1, 2, 3, Σ = a, b, lo statoiniziale e 0 e l’unico stato finale e 3 (F = 3). Le transizioni indica-no che move(0, a) = 0, 1. Inoltre move(0, b) = 0, move(1, a) = ,move(1, b) = 2, move(2, a) = , move(2, b) = 3 e move(3, a) =move(3, b) = .

Un NFA puo riconoscere le stringhe di un certo linguaggio. Per chiarirein quale modo un NFA accetta una stringa definiamo la nozione di camminoetichettato.

Definizione 2.2 (Cammino etichettato) Sia N = 〈S,Σ,move , s0, F 〉 unNFA. Un cammino etichettato di lunghezza k ≥ 0 su N e una sequenza

s0x0−→ s1

x1−→ s2x2−→· · · sk−1

xk−1−→ sk dove:

• s0 e lo stato iniziale

• ∀i ∈ 0, 1, . . . , k − 1. si+1 ∈ move(si, xi)

2.1. AUTOMI NON DETERMINISTICI 13

La stringa x0x1 · · · xk−1 si chiama stringa associata al cammino ed e ingenerale una stringa di Σ∗. Se k = 0 allora il cammino e costituito solodallo stato iniziale e la stringa associata e la stringa vuota ǫ.

Si noti che un cammino di lunghezza k consiste di una sequenza di k+1stati dell’automa ed ha una stringa associata lunga k.

Definizione 2.3 (Stringa accettata) Sia N = 〈S,Σ,move , s0, F 〉 un NFA.Una stringa α ∈ Σ∗ e accettata dall’automa N se e solo se esiste un

cammino etichettato s0x0−→ s1

x1−→ s2x2−→· · · sk−1

xk−1−→ sk su N tale che α e la

stringa associata al cammino e lo stato sk e uno stato finale (in formulesk ∈ F ∧ α = x0x1 · · · xk−1). Se lo stato iniziale e anche di accettazioneallora anche la stringa vuota ǫ e accettata dall’automa.

Possiamo ora introdurre la nozione di linguaggio accettato dall’automa.

Definizione 2.4 (Linguaggio accettato) Sia N = 〈S,Σ,move , s0, F 〉 unNFA. Il linguaggio accettato dall’automa e l’insieme

L(N) = α ∈ Σ∗ | α e accettata da N

Esempio 2.5 Consideriamo l’automa in Figura 2.1.

0a

−→ 0a

−→ 1b

−→ 2b

−→ 3e un cammino etichettato la cui stringa associata e aabb. Lo stato in cuiil cammino termina, 3, e anche uno stato finale e quindi questa stringa eaccettata dall’automa.

Essendo l’automa non deterministico, tuttavia, esiste un altro camminoetichettato con la stringa precedente:

0a

−→ 0a

−→ 0b

−→ 0b

−→ 0in questo caso lo stato 0 non e finale e quindi questo cammino non portaall’accettazione della stringa. Si noti che, comunque, la definizione richiedeche ci sia almeno un cammino etichettato che termina in uno stato finaleper determinare se la stringa associata e accettata o no.

Consideriamo la stringa abab per la quale esistono due cammini etichet-tati:

0a

−→ 0b

−→ 0a

−→ 0b

−→ 00

a−→ 0

b−→ 0

a−→ 1

b−→ 2

nessuno dei due cammini e di accettazione e quindi la stringa non e accet-tata.

Consideriamo invece la stringa abc. In questo caso non esiste nessuncammino etichettato che ha questa stringa associata. Quindi sicuramentenon e accettata.

Facendo altri esempi e considerando la struttura dell’automa e facileconvincersi che il linguaggio accettato e

s abb | s ∈ a, b∗


a1

0start

a

b

a

b

2 c

Figura 2.2: Un NFA.

La costruzione di un cammino etichettato per una data stringa puo esserevista come un algoritmo di riconoscimento di stringhe. Ad esempio, suppo-niamo che vogliamo controllare se la stringa aba fa parte del linguaggioaccettato dall’automa di Figura 2.2. Partiamo dallo stato iniziale e mante-niamo un insieme di stati “correnti”. All’inizio questo insieme e 0 datoche 0 e l’unico stato in cui mi posso trovare all’inizio mentre sto cercandodi costruire un cammino etichettato per la stringa aba.

Consideriamo ora il primo simbolo della stringa: a. A questo punto guar-diamo quali sono gli stati in cui possiamo andare seguendo una transizioneetichettata a uscente da uno qualsiasi degli stati correnti. L’insieme deglistati che posso raggiungere con la prima a e 0, 1 poiche dallo stato 0 cisono due transizioni uscenti etichettate con a (move(0, a) = 0, 1). Questoe il nuovo insieme di stati correnti.

Eliminiamo il primo simbolo dalla stringa in esame e consideriamo quelloseguente: b. A partire da ogni stato in 0, 1 controlliamo in quali stati possoandare seguendo transizioni etichettate con b. Si ha che move(0, b) = 0, 2e move(1, b) = . Il nuovo insieme di stati correnti sara quindi 0, 2.

Eliminiamo il simbolo b e passiamo al successivo e ultimo: a. Dato chemove(0, a) = 0, 1 e move(2, a) = , si ha che il nuovo insieme degli staticorrenti e 0, 1.

A questo punto la stringa di input e stata letta tutta e non ci rimaneche controllare se nell’insieme di stati correnti sia presente almeno uno statofinale. Questo e vero poiche 1 e finale e quindi possiamo concludere che lastringa aba e accettata dall’automa.

Un cammino etichettato che porta all’accettazione della stringa e ilseguente:

0a

−→ 0b

−→ 0a

−→ 1

Consideriamo invece la stringa ac. A partire da uno degli stati in 0possiamo arrivare, con una a, nell’insieme di stati 0, 1. Eliminiamo laprima a e consideriamo la c seguente. A questo punto si ha che move(0, c) =

2.2. AUTOMI FINITI DETERMINISTICI 15

e move(1, c) = . Entrambi sono vuoti. In una situazione come questal’automa si dice bloccato poiche non puo andare avanti a costruire camminipossibili per tutto l’input. Ricordando la definizione di stringa accettatavediamo che in questo caso non esiste nessun cammino etichettato per lastringa e che quindi l’automa non accetta.

Procedendo con altre prove si puo inferire che il linguaggio accettatodall’automa in Figura 2.2 e

s an | s ∈ a, b∗, n > 0 ∪ s b cn | s ∈ a, b∗, n ≥ 0

2.2 Automi finiti deterministici

La definizione di automa che abbiamo dato e quella piu generale, cioe quelladi automa non deterministico. Diamo ora una caratterizzazione degli automideterministici DFA (Deterministic Finite Automata).

Definizione 2.6 (Automa deterministico) Un automa finito determi-nistico (DFA) e una tupla 〈S,Σ,move , s0, F 〉 dove:

• S e un insieme finito di stati.

• Σ e un alfabeto finito di simboli.

• move: (S × Σ) −→ ∪ s | s ∈ S e una funzione di transizionetale che per ogni stato s ∈ S e per ogni simbolo x ∈ Σ l’insieme deglistati move(s, x) o e vuoto oppure contiene un solo stato.

• s0 ∈ S e lo stato iniziale.

• F ⊆ S e l’insieme degli stati finali.

Si noti che l’unica differenza con la definizione di NFA e sulla funzionedi transizione move. Detto a parole un automa e deterministico se da ognistato non escono mai due transizioni etichettate con lo stesso simbolo.

La nozione di cammino etichettato e di accettazione per un DFA e ana-loga a quella di un NFA. Dato che in un DFA, dato uno stato e un simbolo,e possibile al piu una transizione etichettata con quel simbolo, si ha che perogni stringa accettata da un DFA esiste un unico cammino etichettato conla stringa e che termina in uno stato finale.

L’algoritmo di riconoscimento di una data stringa e uguale a quello di unNFA, ma in questo caso ad ogni passo l’insieme degli stati correnti contieneuno ed un solo stato.

Esempio 2.7 Consideriamo l’automa disegnato in Figura 2.3. Esso e unautoma deterministico che accetta lo stesso linguaggio dell’automa di Figu-ra 2.1, cioe s · abb | s ∈ a, b∗. L’unico cammino di accettazione per lastringa aabb e


b b

a b b 3210

a a

a

Figura 2.3: Un automa deterministico.

0a

−→ 1a

−→ 1b

−→ 2b

−→ 3

Il cammino di accettazione per la stringa abaabb e:

0a

−→ 1b

−→ 2a

−→ 1a

−→ 1b

−→ 2b

−→ 3

Nel caso degli automi deterministici determinare se una stringa e accet-tata o no e piu semplice. Si possono verificare solo due casi:

1. La stringa non ha nessun cammino etichettato corrispondente. Inquesto caso non e accettata.

2. La stringa ha un cammino etichettato e sappiamo che e l’unico. Bastaguardare l’ultimo stato di tale cammino: se e di accettazione allora lastringa e accettata, altrimenti no.

2.3 Costruzione dei sottoinsiemi

Gli automi deterministici e quelli non deterministici hanno lo stesso potereespressivo. Questo significa che se un linguaggio puo essere accettato da unNFA allora esiste anche un DFA che lo accetta, e viceversa.

E’ chiaro che l’algoritmo di riconoscimento di una certa stringa di unDFA e piu immediato poiche non bisogna tener traccia di un insieme distati (il cammino di accettazione, se esiste, e unico). D’altra parte, da unpunto di vista di progettazione, il non determinismo rende piu facile scrivereun automa e/o determinare che tipo di linguaggio accetta, oltre a permetteredi scrivere automi piu concisi.

Basta ad esempio guardare i due automi delle Figure 2.1 e 2.3 che ac-cettano lo stesso linguaggio. Il primo e non deterministico nello stato 0 especifica in maniera naturale che si possono riconoscere a o b in qualsiasinumero ed ordine prima di passare ad una stringa finale obbligatoria abb. Ilsecondo invece deve esplicitare una sorta di backtracking, cioe gli stati de-vono tenere traccia dei vari casi possibili: la prima a che incontra potrebbe

2.3. COSTRUZIONE DEI SOTTOINSIEMI 17

essere quella della stringa finale obbligatoria e quindi l’automa entra nellostato 1. Se il simbolo seguente non e una b allora l’automa continua a ciclarenello stato 1. Nello stato 2, se il simbolo seguente non e l’ultima b l’automaritorna nello stato 1 ad aspettare di leggere un’altra a possibile candidataad essere il primo simbolo della stringa finale obbligatoria. Infine nello stato3 l’automa deve ritornare nello stato 0 o 1 se ci sono ancora simboli b oa, rispettivamente. Questo perche i simboli letti precedentemente potreb-bero essere il prefisso di una stringa che poi terminera con la stringa finaleobbligatoria.

In questa sezione formalizziamo un algoritmo noto come costruzionedei sottoinsiemi (subset construction) che serve per costruire, a partire daun NFA dato, un DFA equivalente che simula il non determinismo, ma edeterministico.

Per specificare l’algoritmo useremo uno pseudo-codice in cui le strutturedati vere e proprie non saranno specificate (in ogni caso non e difficile imple-mentare questi algoritmi in un linguaggio di programmazione: basta definirele opportune strutture dati e le varie funzioni/procedure che specifichiamo).

Algoritmo 2.1 (Subset construction) Costruzione di un DFA a partireda un NFA.

Linguaggio: Pseudocodice.

Input: Un automa non deterministico N .

Output: Un automa deterministico equivalente D.

Sia s0 l’unico stato non marcato di DStates ;while c’e’ uno stato non marcato T in DStates do

beginmarca T ;for each simbolo di input x ∈ Σ do

beginU := move(T, x);if U non e’ in DStates then

beginaggiungi U , non marcato, a DStates ;

endDtran(T, x) := U ;

endend

lo stato iniziale di D e’ s0gli stati finali di D sono tutti quelli che contengono almeno uno stato finale di N


L’algoritmo e uno dei classici algoritmi di calcolo di un punto fisso (ilcalcolo di un insieme definito induttivamente) e ha la proprieta di terminaresempre in un numero finito di passi. In pratica partiamo da un insieme distati DStates contenente solo uno stato iniziale non marcato. Ad ogni passoselezioniamo uno stato non marcato da DStates e ne calcoliamo le transizioniuscenti aggiungendo a DStates , non marcati, eventuali nuovi stati trovati.Prima o poi, dato che il numero di stati possibili e finito (il numero dielementi di ℘(S) e 2|S|, cioe due elevato al numero di elementi di S, chesono gli stati dell’automa N e sono in numero finito per definizione) non cisaranno piu stati non marcati da considerare e l’algoritmo terminera.

Esso costruisce la funzione di transizione Dtran simulando, attraversoinsiemi di stati di N , i comportamenti di N “in parallelo” dovuti al nondeterminismo.

All’interno dell’algoritmo viene utilizzata la funzione move, che specifi-chiamo matematicamente:

move: (℘(S) × Σ) −→ ℘(S)

tale chemove(T, x) =

⋃

s∈T

move(s, x)

In pratica si mettono in uno stesso insieme tutti gli stati raggiungibili conuno stesso simbolo x a partire da uno stato qualunque di T .

Esempio 2.8 Consideriamo come automa N di partenza quello in Figu-ra 2.1. Il linguaggio accettato, come sappiamo, e s · abb | s ∈ a, b∗. Ap-plichiamo l’algoritmo della costruzione dei sottoinsiemi e troviamo il DFAD equivalente.

Lo stato iniziale di D e per definizione 0 poiche 0 e lo stato iniziale diN . Chiamiamo questo insieme, per convenienza, A. A e il primo stato nonmarcato che fa parte di DStates.

Alla prima iterazione selezioniamo per forza lo stato A e lo marchiamo.Calcoliamo:

• move(A, a) = 0, 1 Chiamiamo questo nuovo stato B = 0, 1

• move(A, b) = 0 = A

Con una b ritorniamo nello stato iniziale e con una a andiamo un uno statonuovo B (non si trova attualmente in DStates) che, seguendo l’algoritmo,va inserito non marcato in DStates.

In generale, una funzione di transizione di un NFA o di un DFA puoessere rappresentata, oltre che graficamente come abbiamo visto, anche conuna tabella in cui le righe sono gli stati e le colonne sono i simboli dell’al-fabeto. La cella ad una riga T e ad una colonna x della tabella e l’insiemedi stati che risulta da move(T, x).

2.3. COSTRUZIONE DEI SOTTOINSIEMI 19

La tabella che rappresenta la parte di Dtran calcolata fino a questo puntoe la seguente:

Stato a b Marcato

A = 0 B A Si

B = 0, 1 No

Procediamo scegliendo uno stato non marcato. Anche questa volta la sceltaobbligata e B e calcoliamo:

• move(B, a) = 0, 1 = B

• move(B, b) = 0, 2 Chiamiamo questo nuovo stato C = 0, 2

Anche questa volta per il simbolo a non e stato generato nessuno stato nuovo,mentre per b e stato generato il nuovo stato C che inseriamo non marcato inDStates. La tabella parzialmente costruita fino a questo punto e la seguente:

Stato a b Marcato

A = 0 B A Si

B = 0, 1 B C Si

C = 0, 2 No

Continuando ad applicare l’algoritmo si arriva a generare un ulteriore statoD = 0, 3 dopodiche non si generano piu nuovi stati e l’algoritmo termina.La tabella finale e la seguente:

Stato a b Marcato

A = 0 B A Si

B = 0, 1 B C Si

C = 0, 2 B D Si

D = 0, 3 B A Si

L’unico stato finale e D poiche e l’unico che contiene uno stato finale di N ,cioe 3. L’automa e disegnato in Figura 2.4. Si noti che questo e lo stessoautoma di Figura 2.3 a meno di ridenominazione degli stati (0=A, 1=B,2=C, 3=D).

Per concludere osserviamo che in tutte le caselle della tabella dell’esem-pio abbiamo ottenuto un insieme di stati da inserire. Tuttavia questo non


b b

a b b

a a

a

DA B C

Figura 2.4: L’automa deterministico risultante dalla costruzione deisottoinsiemi.

si verifica sempre: se otteniamo, per una certa casella, move(T, x) = al-lora significa che nell’automa risultante D, a partire dallo stato T , non c’enessuna transizione uscente etichettata con x. Graficamente questo significache non c’e nessuna freccia uscente da T con etichetta x. Nella rappresen-tazione con una tabella si inserisce l’insieme vuoto o si lascia l’entratavuota.

2.4 Minimizzazione di un DFA

La facilita di simulazione di un DFA rispetto a quella di un NFA e compen-sata dal fatto che il DFA in genere ha un numero maggiore di stati. E lecitochiedersi, in quest’ottica, se e possibile, dato in certo DFA, trovarne unoequivalente, ma che abbia un numero minore di stati. La risposta e sı, edesiste un algoritmo che trova un DFA equivalente ad un DFA dato e tale chel’automa risultato ha un numero minimo di stati. Qui minimo si riferisceagli stati necessari per poter accettare il linguaggio accettato dall’automadi partenza. Inoltre si ha che l’automa minimo e unico a meno di rinomi-nare gli stati (in altre parole se trovo due automi minimi esiste sempre unafunzione bigettiva fra gli stati dei due che rispetta tutte le transizioni).

In questo corso non vediamo questo algoritmo, ma e bene sapere cheesiste la nozione di minimalita e di equivalenza di stati. Si osservi ad esempiol’automa deterministico di Figura 2.5. E facile convincersi che anche questoautoma accetta il linguaggio s·abb | s ∈ a, b∗ come quello risultante dallacostruzione dei sottoinsiemi in Figura 2.4. Il numero di stati di quest’ultimo,pero, e minore del numero di stati dell’altro. L’algoritmo di minimizzazione,partendo dall’automa con piu stati, avrebbe riconosciuto che gli stati A e Csono equivalenti e li avrebbe unificati in un unico stato fornendo inoltre ladimostrazione, per come e costruito, che l’automa di Figura 2.4 e minimo.

2.5. PROGETTAZIONE DI UN AUTOMA 21

a

b

a

a

b

A B

C

EDb

a

b

a

b

start

Figura 2.5: Un automa deterministico per s · abb | s ∈ a, b∗.

2.5 Progettazione di un automa

In molti esercizi viene richiesto di scrivere un automa che accetti un certolinguaggio dato. Il linguaggio puo essere stato specificato sia in manieraformale (con un’espressione su insiemi o con un’espressione regolare, Sezione3.4.1) oppure in maniera informale tramite una descrizione a parole e conl’ausilio di esempi.

In entrambi i casi, se si vuole affrontare il problema partendo col piedegiusto, e bene assicurarsi di aver capito esattamente che tipo di linguaggioviene richiesto. Se questo e vero si e sicuramente in grado di scrivere alcunestringhe del linguaggio e, soprattutto, di individuare i “casi particolari”:le stringhe piu corte, quelle piu anomale, quelle che hanno una strutturaprecisa che si ripete, ecc.

Quando si e sicuri di aver compreso il linguaggio si puo passare al pro-getto dell’automa. In questa fase bisogna cercare di trovare un modo dicombinare gli strumenti che ci da la teoria degli automi per ottenere lestringhe richieste. A ben guardare gli strumenti sono molto semplici: sta-ti, transizioni con cui consentire o impedire (non mettendo la transizione)cammini, stati di accettazione e una forma molto semplice di ricorsione checi permette di iterare delle transizioni su un certo stato o su un certo ciclodi stati.

La prima cosa da fare e cercare di trovare un algoritmo con cui si voglionoaccettare tutte e sole le stringhe del linguaggio. Un errore tipico e quellodi preoccuparsi di far accettare all’automa tutte le stringhe del linguaggio e


non preoccuparsi di non fare accettare stringhe che non sono nel linguaggio.Un altro errore tipico e quello di costruire l’automa seguendo alcuni esempidi stringhe e non la definizione di tutto il linguaggio: in questo caso l’automarisultante di solito accetta tutte le stringhe di esempio, ma non ne accettaaltre che sono comunque nel linguaggio.

Per evitare questi problemi e bene seguire una metodologia che guidialla soluzione. La prima raccomandazione di questa metodologia e quella dipartire dagli stati per elaborare un algoritmo. Gli stati di un automa possonoastrarre qualunque tipo di informazione, a qualunque livello di dettaglio. Sipuo decidere, quindi, di rappresentare con uno stato una qualsiasi situazione.Dopo questo primo passo, tenendo ben presente i diversi significati che sisono dati ai diversi stati dell’automa, si raccomanda di passare a scrivere letransizioni tra di essi in maniera coerente con la logica dell’algoritmo che sie pensato. Il tocco finale e riconoscere gli stati di accettazione.

Facciamo alcuni esempi classici per illustrare questa metodologia. Siconsideri il seguente problema: costruire un automa che accetti tutte e solele stringhe di 0, 1∗ che hanno un numero pari di occorrenze del simbolo 1.

Per prima cosa riflettiamo sul linguaggio. Zero e da considerarsi nume-ro pari e quindi sicuramente l’automa deve accettare tutte le stringhe checontengono zero occorrenze del simbolo 1, cioe che contengono solo simboli0. In particolare puo accettare anche la stringa vuota ǫ poiche questa con-tiene sicuramente zero occorrenze del simbolo 1. Delle stringhe che invececontengono qualche simbolo 1 osserviamo subito che non ci importa comesono dislocati questi 1 all’interno della stessa. In particolare, essi potrebberoessere tutti attaccati oppure occorrere qua e la fra diversi simboli 0 messia piacere. Non e questo che ci interessa: ci interessa la parita del numerodelle loro occorrenze.

Avendo, in questo modo, inquadrato per bene il linguaggio possiamopassare a cercare un algoritmo per l’accettazione delle stringhe descritte.Il fatto che le occorrenze del simbolo 0 non influenzano la nostra decisionesull’accettazione o no della stringa ci induce a pensare che sicuramente, inqualsiasi stato si trovi l’automa, possiamo inserire una transizione uscenteetichettata con 0. Questo significa che la vera logica dell’automa deve esserebasata solo sulle occorrenze dei simboli 1.

Mettiamoci nei panni dell’automa che riceve una stringa in ingresso edeve decidere se accettarla o no. Pensiamo all’algoritmo che potrebbe se-guire. Possiamo pensare che alla prima occorrenza di un simbolo 1 l’automadeve ricordare questa informazione in un certo stato poiche questo significache, per il momento, c’e un numero dispari (1) di occorrenze di simboli 1.Quindi, se la stringa si conclude qui, o al limite dopo alcune occorrenze delsimbolo 0, non possiamo accettarla. Comunque la stringa potrebbe non es-sere terminata e quindi l’automa deve poter continuare a guardare i prossimisimboli in ingresso.


Ad una eventuale occorrenza successiva di un simbolo 1 l’automa dovradi nuovo ricordare la cosa poiche, se dopo la prima occorrenza il numero disimboli 1 era dispari, ora il numero di simboli 1 e pari e quindi, allo statoattuale delle cose, la stringa puo essere accettata. Dobbiamo fare in modoche questo avvenga se la stringa si conclude qui oppure se si conclude dopoun certo numero di occorrenze di soli simboli 0.

Se la stringa continua, a questo punto, ci ritroviamo nella situazione ini-ziale: se arriva un simbolo 1 bisogna cambiare stato e ricordare che attual-mente la stringa non puo essere accettata. E se arriva un 1 successivamentel’automa deve di nuovo cambiare lo stato e ricordare che attualmente lastringa puo essere accettata.

A questo punto e chiara la logica dell’algoritmo: si oscilla tra i due statifino a quando la stringa non termina e a quel punto si guarda lo stato in cuisi e per decidere se accettare o no.

Formalizziamo questa idea con gli strumenti che ci danno gli automi.Innanzitutto, alla luce della nostra idea, definiamo due stati p e d. Lo statop ricorda l’informazione: “fino a questo momento la stringa di ingresso con-tiene un numero pari di simboli 1” mentre lo stato d ricorda l’informazione:“fino a questo momento la stringa di ingresso contiene un numero dispari disimboli 1”.

All’inizio, quando l’automa non ha ancora letto nessun simbolo dellastringa in ingresso, vale l’enunciato associato allo stato p poiche zero occor-renze di 1 sono un numero pari. Pertanto p e il candidato perfetto per esserelo stato iniziale dell’automa.

Passiamo a definire le transizioni fra questi stati stando bene attenti apreservare la logica degli stessi, cioe a fare in modo che l’informazione ad essiassociata rimanga sempre vera. Esaminiamo la situazione stato per stato.

Consideriamo lo stato p e mettiamoci nei panni dell’automa che legge ilprimo simbolo della stringa che gli e rimasta da analizzare. Assumiamo percostruzione che l’informazione associata allo stato sia vera e impegnamocia scrivere le transizioni in modo tale che resti vera. Siccome l’alfabeto Σ el’insieme 0, 1 l’automa puo prevedere zero, una o piu2 transizioni uscentidallo stato d etichettate con 0 o 1.

Consideriamo il simbolo 0. Abbiamo detto che l’occorrenza di tale sim-bolo non cambia niente rispetto alla logica degli stati. In particolare, inquesto caso, si vede benissimo che l’informazione associata a p, cioe “fino aquesto momento la stringa di ingresso contiene un numero pari di simboli1”, non e influenzata dall’occorrenza attuale di un simbolo 0, che comunquepuo occorrere liberamente. Pertanto ci sara una transizione uscente da petichettata con 0 e lo stato di destinazione deve essere per forza p stesso!Diversamente, infatti, l’automa dovrebbe andare in d asserendo erroneamen-

2Ad esempio se l’automa e non deterministico.


1

p d

0

1

0

Figura 2.6: L’automa costruito per riconoscere stringhe con parita di 1.

te di aver letto un numero dispari di 1. Non c’e bisogno di altre transizionietichettate con 0.

Consideriamo il simbolo 1. Sappiamo che anche 1 puo occorrere libera-mente in qualsiasi punto della stringa in ingresso, ma ogni volta che occorrelo stato dell’automa deve cambiare. Stiamo assumendo di trovarci nello sta-to p e quindi, con la transizione etichettata 1, dobbiamo andare in d. Si notiche la logica degli stati e rispettata perche l’informazione associata allo statod e vera dopo l’esecuzione di questa transizione (questo perche noi stiamoassumendo che l’informazione associata a p sia vera prima della transizione).Per quanto riguarda lo stato p non ci sono altre considerazioni da fare.

Per lo stato d si fanno gli stessi ragionamenti considerando, pero, chequesta volta si parte dall’assunzione che siano stati letti un numero disparidi 1. Quindi, all’occorrenza di 0, come in p, l’automa non cambia stato, maall’occorrenza di 1 l’automa deve ritornare in p per preservare la logica deglistati.

Rimangono solo da definire, a questo punto, gli stati finali. E chiaro chein questo automa l’unico stato che puo essere considerato di accettazione e p.Questo perche la consegna dice che l’automa deve accettare solo le stringhecon un numero pari di 1 e p e proprio lo stato in cui questo e sempre vero.

Si noti che, in generale, assegnare uno stato s come di accettazione nonimplica che un automa che si trova in s non possa continuare a leggere unastringa in ingresso e continuare quindi a costruire un cammino. E essenzialeinvece accertarsi che se l’automa si ferma in uno stato di accettazione allorala stringa letta fino a quel momento sia sempre una stringa del linguaggioassegnato.

Nel nostro esempio questo e vero perche una volta che l’automa e entratonello stato p la stringa letta fino a quel momento puo essere sicuramenteaccettata. La stringa inoltre puo continuare con diverse occorrenze di simboli0 e rimanere sempre una stringa del linguaggio assegnato. Solo leggendo un1 si cambia stato e si potra accettare la stringa solo se proseguendo, allafine, si ritornera in p.

L’automa che abbiamo costruito e raffigurato in Figura 2.6.


i

0

1

1

01

0 0

Figura 2.7: L’automa costruito per stringhe senza 1 consecutivi.

Facciamo un altro esempio. Supponiamo di voler scrivere un automa cheaccetti il linguaggio, sempre sull’alfabeto 0, 1, di tutte le stringhe che noncontengono mai due simboli 1 consecutivi.

Di nuovo ci va bene qualunque stringa di soli simboli 0 e quindi anchela stringa vuota. Per quanto riguarda i simboli 1 essi di nuovo possonooccorrere in qualunque posizione, ma mai due volte di seguito. Per poterrealizzare questo vincolo possiamo pensare di ricordare negli stati qual el’ultimo simbolo che e stato letto nella stringa di ingresso. Essendoci solo duesimboli, creiamo due stati: lo stato 0 che ricorda l’informazione: “l’ultimosimbolo letto e 0” e lo stato 1 a cui e associata l’informazione: “l’ultimosimbolo letto e 1”.

Come stato iniziale, pero, nessuno dei due va bene poiche entrambi pre-suppongono che ci sia un simbolo letto precedentemente. Non c’e proble-ma: possiamo creare tutti gli stati che vogliamo e quindi ne creiamo uno,chiamiamolo i, che serve solo a fare da stato iniziale.

Adesso costruiamo le transizioni di conseguenza. Dallo stato iniziale ipartira una transizione etichettata con 0 verso lo stato 0 e una etichettatacon 1 verso lo stato 1. In questo modo l’informazione sugli stati diventa veraal primo passo dell’automa. Facciamo inoltre in modo che non ci sia la possi-bilita di ritornare nello stato i (questo perche l’abbiamo costruito solo comestato iniziale e un uso diverso potrebbe confondere la nostra progettazione).

Nello stato 0 non ci sono vincoli su quale simbolo puo occorrere. Ciosignifica che c’e una transizione uscente etichettata con 0 ed una etichettatacon 1. Per rispettare la logica degli stati, ovviamente, la prima deve ritornarenello stato 0 mentre la seconda deve andare nello stato 1.

Nello stato 1 bisogna esprimere il vincolo assegnato dal linguaggio.

In generale sappiamo che un automa accetta una stringa se e solo seriesce a costruire per essa almeno un cammino che termina in uno stato diaccettazione. Pertanto abbiamo due modi per non fare accettare una stringaad un automa: fare in modo che tutti i suoi cammini terminino in uno stato


non di accettazione oppure impedire la costruzione di un cammino per lastringa.

In questo caso utilizziamo la seconda possibilita: semplicemente impe-diamo all’automa di costruire cammini per stringhe che hanno due simboli1 consecutivi. Per far questo basta non mettere nessuna transizione uscentedallo stato 1 etichettata con 1. Per il simbolo 0 invece inseriamo la transi-zione uscente e, per rispettare la logica degli stati, questa transizione deveritornare nello stato 0.

Manca solo la specifica degli stati finali. In questo caso qualunque stringache abbia un cammino sull’automa va bene poiche abbiamo escluso tutte esole le stringhe non accettabili impedendo all’automa di costruire camminiper esse. Quindi tutti gli stati sono di accettazione.

L’automa e disegnato in Figura 2.7. Si noti che, da un punto di vista diottimizzazione, lo stato i e inutile poiche perfettamente equivalente allo stato0. Pertanto sarebbe possibile scrivere un automa per lo stesso linguaggiocon soli due stati. Non essendo stato richiesto un automa minimo non cidobbiamo preoccupare di questo aspetto. L’automa con lo stato iniziale i inpiu va benissimo.

Capitolo 3

Induzione e ricorsione

In questo capitolo introduciamo due nozioni centrali per questo corso e perl’informatica in generale.

3.1 Ricorsione

L’induzione e la ricorsione sono due concetti strettamente legati. Una defi-nizione viene detta ricorsiva se ‘l’oggetto che si vuole definire compare anchenell’espressione che dovrebbe definirlo’. E chiaro che un’espressione del gene-re deve essere data molto accuratamente, poiche puo definire effettivamentequalcosa solo nel caso in cui suggerisce una costruzione induttiva.

L’esempio classico di definizione ricorsiva e quella della definizione dellafunzione fattoriale. La funzione fattoriale fatt deve prendere un certo nu-mero naturale n e restituire il numero risultante dalla moltiplicazione di tuttii numeri da 1 a n (n compreso). Quindi, ad esempio, fatt(4) = 1·2·3·4 = 24.Nel caso in cui n sia uguale a zero la definizione introduce per convenzioneche fatt(0) = 1. Questo risulta comodo per dare le definizioni e rispettaanche certe logiche in taluni contesti matematici.

La funzione fatt e spesso definita in questo modo:

fatt(n) =

1 se n = 0n · fatt(n− 1) se n > 0

Si capisce subito, semplicemente leggendo il testo, che la definizione ericorsiva: a destra dell’equazione compare il simbolo fatt che e proprio l’og-getto che stiamo definendo. Ma allora come e possibile che questa definizionesia ben posta?

In effetti questa equazione potrebbe non avere nessuna soluzione (cioepotrebbe non esistere nessuna funzione matematica fra numeri naturali che,sostituita a fatt nell’equazione, renda vera l’uguaglianza). Pero in questocaso una soluzione c’e e possiamo calcolarla costruttivamente! Questo accadetutte le volte che si da una definizione ricorsiva corretta.

27

28 CAPITOLO 3. INDUZIONE E RICORSIONE

Per convincersi della bonta della definizione basta seguirne la semplicelogica: se dobbiamo calcolare il fattoriale di zero sappiamo che esso e sempre1 per convenzione. Invece, se n e maggiore di zero, il suo fattoriale e lamoltiplicazione di n per n− 1, per n− 2, e cosı via fino a 1 (che, non a caso,e anche il fattoriale di zero). Ma il risultato di n−1·n−2 · · · 1 e esattamenteil fattoriale di n− 1. Cosicche basta semplicemente dire che per calcolare ilfattoriale di n basta moltiplicare n per il fattoriale di n− 1.

A questo punto possiamo spingerci oltre questa considerazione intuitivae cercare di capire esattamente come la definizione funzioni e vedere pre-cisamente cio che viene definito. In altre parole cerchiamo di descrivererigorosamente in che modo la soluzione, cioe la funzione fatt, puo esserecalcolata.

3.2 Costruzione induttiva

Lo strumento che possiamo utilizzare per trovare la soluzione che ci inte-ressa e l’induzione o costruzione, che dir si voglia. Una definizione ricorsivacorretta contiene sempre almeno un caso base. Un caso base rappresentaun punto di partenza per iniziare una costruzione. Naturalmente possonoesserci piu casi base, nel qual caso abbiamo un insieme di punti di partenza.Un caso base si riconosce facilmente: nella sua definizione non viene usatol’oggetto che si sta definendo, ma viene dato direttamente un risultato. Nelnostro caso c’e un unico caso base che ci dice che quando dobbiamo calcolareil fattoriale di zero, la risposta e 1.

Per comodita rappresentiamo la funzione fatt che vogliamo calcolarecome un insieme di coppie di numeri naturali. Ogni coppia (n,m) in questoinsieme rappresenta il fatto che fatt(n) = m. Per avere la nostra soluzionedobbiamo ottenere un insieme in cui ci sia una e una sola coppia (n,m) pertutti gli n naturali. Naturalmente questo e un insieme infinito, ma vedremoche il fatto che sia definito induttivamente ci da la possibilita di calcolarlo inmaniera incrementale esattamente fino al punto che ci serve in pratica (cioecalcolare il fattoriale di un certo numero n dato).

Ogni costruzione induttiva parte dai casi base e procede per passi succes-sivi costruendo soluzioni parziali che diventano sempre piu grandi ad ognipasso. Nel nostro esempio abbiamo un solo caso base che ci dice che la cop-pia (0, 1) deve essere inclusa nell’insieme che rappresenta la funzione fatt

poiche dice chiaramente che fatt(0) = 1. Quindi al primo passo, senza averfatto niente di piu che leggere la definizione e trovare i casi base abbiamocalcolato la soluzione parziale

(0, 1)

Entriamo adesso nella logica del cosiddetto passo induttivo o passo dicostruzione. Innanzitutto dobbiamo formalmente riconsiderare i casi base e

3.2. COSTRUZIONE INDUTTIVA 29

considerare la soluzione parziale ottenuta nel passo precedente (c’e semprealmeno un passo precedente a questo). La soluzione parziale che abbiamoattualmente e (0, 1) che coincide con l’informazione ottenuta dal caso ba-se e che, abbiamo detto, indica fatt(0) = 1. Dobbiamo quindi guardare icasi induttivi della definizione. Nel nostro esempio abbiamo solo un casoinduttivo che ci dice che fatt(n) = n · fatt(n − 1). Come possiamo utiliz-zare questa informazione avendo a disposizione la nostra soluzione parziale?Attualmente conosciamo solo fatt(0) e possiamo quindi concludere, sosti-tuendo nella definizione n con il valore 1, una sola cosa in piu: cioe chefatt(1) = 1 · fatt(1 − 1) = 1 · fatt(0) = 1 · 1 = 1. E quindi la nostrasoluzione parziale e aumentata! Attualmente e l’insieme

(0, 1), (1, 1)

Il passo induttivo deve essere ripetuto fino a che non si giunge alla solu-zione totale. Nel nostro caso sappiamo che la soluzione e un insieme infinitoe che quindi c’e bisogno di un numero infinito di passi per arrivarci. Questonon succede sempre: se l’oggetto che si sta definendo ricorsivamente e finitoallora prima o poi la soluzione parziale smette di crescere ad ogni passo. Inaltre parole si arriva ad una certa soluzione parziale per cui, applicando ipassi induttivi in tutti i modi possibili, non si ottiene nessuna nuova infor-mazione. Cio significa che quella particolare soluzione parziale e la soluzionefinale che stavamo cercando1.

Facciamo ancora alcuni passi induttivi. A partire da (0, 1), (1, 1) pos-siamo inferire di nuovo sia la coppia (0, 1) dal caso base sia la coppia (1, 1)dalla coppia (0, 1). Questo, pero, non aumenta la soluzione parziale. Dallacoppia (1, 1) viene invece fuori qualcosa di nuovo: fatt(2) = 2·fatt(2−1) =2 · fatt(1) = 2 · 1 = 2. La nuova soluzione parziale e

(0, 1), (1, 1), (2, 2)

Al passo successivo si puo rigenerare tutta la soluzione parziale cheavevamo piu un nuovo elemento, a partire dalla coppia (2, 2): fatt(3) =3 · fatt(3− 1) = 3 · fatt(2) = 3 · 2 = 6. La nuova soluzione parziale e

(0, 1), (1, 1), (2, 2), (3, 6)

Ci si puo facilmente convincere che andando avanti meccanicamente inquesto modo ad ogni passo aggiungiamo sempre e solo una coppia nuova (n+1, (n+1) ·m) se al passo precedente avevamo aggiunto la coppia (n,m). Lasoluzione finale si trova dopo un numero infinito di passi. Esiste una teoriamatematica che assicura che essa esiste. Questo pero solo se la definizione e

1La teoria matematica che descrive tutto questo processo ci dice che la soluzione chesi trova sia nel caso finito che in quello infinito e quella minima. Potrebbero cioe, in certicasi, esistere altre soluzioni.


data in maniera corretta, in modo cioe da suggerire un processo costruttivocrescente analogo a quello che abbiamo visto.

Vediamo un esempio in cui il processo costruttivo viene specificato inmaniera errata:

foo(n) =

1 se n = 0n · foo(n+ 1) se n > 0

Osserviamo la definizione ricorsiva della funzione foo. Quale processo di co-struzione suggerisce? Possiamo provare a partire come per fatt dalla coppia(0, 1) che viene data dal caso base. Nel passo induttivo pero non siamo ingrado di dedurre niente di nuovo dalla soluzione parziale (0, 1): per ot-tenere foo(1) infatti dovremmo conoscere gia una coppia (2,m), che invecenon c’e! Quindi dobbiamo subito fermarci e dichiarare che il massimo cheabbiamo potuto ricavare e foo(0) = 1. L’obiettivo di definire una funzionefoo per tutti i numeri naturali non e stato raggiunto. Quello che abbiamodefinito e una funzione parziale che da un valore solo per zero.

3.3 Chiamate ricorsive

Naturalmente possiamo scrivere un programma che calcola la funzione fattper ogni numero naturale. Basta far eseguire al programma la costruzio-ne che abbiamo visto fino ad arrivare ad ottenere la coppia (n, fatt(n)).Tuttavia, il processo che abbiamo descritto risulta molto inefficiente: adogni passo si devono ricalcolare molte cose che gia si sono calcolate prece-dentemente. In realta basterebbe calcolare ogni volta solo la coppia nuova!Vediamo quindi un modo piu efficiente di applicare le definizioni ricorsive.

Le definizioni ricorsive, oltre all’interpretazione costruttiva che abbiamodescritto finora, hanno sempre anche un’altra possibile interpretazione chepossiamo chiamare ‘dall’alto verso il basso’. Nell’interpretazione costruttivainfatti noi partiamo dal basso (dai casi base) per costruire passo dopo passoun qualcosa che, alla fine, diventera l’oggetto definito induttivamente. Inmolti casi pero, come ad esempio per il caso del fattoriale in cui l’obiettivo eessere capaci di calcolare un valore a partire da un dato numero n, e conve-niente adottare una visione diversa in cui la definizione ricorsiva suggerisceuna scomposizione in problemi piu piccoli.

Cerchiamo di spiegare questo modo di vedere adottando sempre l’esem-pio del fattoriale. Consideriamo la stessa definizione di fatt data sopracome il punto di partenza di un algoritmo che debba risolvere il problemadi calcolare il fattoriale di un certo numero n dato in input. Quali sono ipassi dell’algoritmo suggeriti dalla definizione? Proviamo a fare un esempioponendo l’input n = 3.

Per capire bene in che modo possiamo fare il calcolo, e in che modoviene poi fatto effettivamente dai programmi eseguibili, dobbiamo pensare

3.3. CHIAMATE RICORSIVE 31

di operare in ogni momento in un certo ‘ambiente’ ben definito in cui eimmagazzinata l’informazione sul valore di n per il quale dobbiamo calcolarefatt(n) e in cui c’e uno spazio vuoto in cui andremo a scrivere dei risultatiintermedi che ci serviranno fino al momento di ‘uscire’ e terminare la nostraesecuzione.

All’inizio, quindi, nel nostro ‘ambiente’ memorizziamo che dobbiamo cal-colare il fattoriale del valore 3 e riserviamo lo spazio per un valore interme-dio che ci servira durante il calcolo. Rappresentiamo il nostro ambientecome una scatola con dentro il valore e un quadratino vuoto per il valoreintermedio:

3

Per andare avanti nel calcolo dobbiamo guardare la definizione ricorsiva.Essa ci puo dare una risposta immediata nel caso in cui dovessimo calcolareil valore del fattoriale di zero. Guardando il nostro ambiente sappiamo chenon e questo il caso e quindi passiamo all’altro caso. La definizione ci diceche possiamo calcolare quello che ci serve per il nostro valore n = 3 solo sesappiamo il valore di fatt(n − 1), cioe fatt(2). Questo, se consideriamol’ordine dei numeri naturali come misura di grandezza, e un problema piupiccolo di quello che stiamo affrontando attualmente.

Il fatto che il problema che si pone e analogo ma in qualche modo piu‘piccolo’ rispetto a quello attuale ci permette, vedremo, di riuscire a risolvereil problema intero innescando un processo di scomposizione. Infatti e ragio-nevole pensare che se il problema da risolvere diventa sempre piu piccoloallora alla fine diventera un caso base che si puo risolvere facilmente. Nelnostro esempio la strategia e quindi di cercare di raggiungere il problemafatt(0) e da lı poi fare tutti i conti seguendo rigorosamente la definizionericorsiva.

Dato che il problema piu piccolo che abbiamo posto e analogo al nostroproblema principale, cioe e sempre quello di calcolare un fattoriale, il truccoche adottiamo e il seguente:

Sospendiamo momentaneamente la nostra esecuzione e creiamouna nuova istanza di algoritmo per il calcolo del fattoriale conil suo proprio ambiente. Dentro questo ambiente pero inseriamocome input il valore del problema piu piccolo, in questo esempio3-1=2. A questo punto facciamo partire la nuova istanza e aspet-tiamo fiduciosi che ci dia una risposta, ricordandoci di porre talerisposta nello spazio che abbiamo riservato nel nostro ambienteper il valore intermedio.


Se la definizione ricorsiva e corretta questa nuova istanza ci dara sicu-ramente una risposta, e sara la risposta corretta! A quel punto bastera,seguendo la definizione ricorsiva, moltiplicare il nostro valore di input n = 3con il valore del risultato intermedio (che abbiamo detto sara fatt(n − 1),cioe fatt(2)) per ottenere il risultato!

Prima di andare avanti per vedere come avviene precisamente il calcolodel valore intermedio, adottiamo un altro semplice ma ingegnoso trucco:impiliamo sulla scatola del nostro problema principale (quella con dentro 3)la scatola generata per la nuova istanza. Il punto fondamentale e propriol’impilare. In informatica la pila (stack in inglese) e un oggetto che si usamoltissimo. La caratteristica principale di una pila e che un nuovo elementopuo essere inserito solo sopra quello che e stato inserito precedentemente eche un elemento puo essere tolto solo se si trova sopra a tutti gli altri nellapila (se pensiamo ad una pila di piatti si intuiscono facilmente i problemirelativi ad un inserimento e ad una rimozione ‘nel mezzo’).

La pila ci permette di gestire senza errori l’ordine di esecuzione dellecosiddette chiamate ricorsive, cioe le varie istanze dello stesso algoritmo chevengono create via via con il compito di risolvere problemi sempre piu piccoli.In genere si disegna una pila come una sequenza di oggetti che crescono versol’alto. Rispettiamo questa convenzione e vediamo quindi come si presentala pila degli ‘ambienti’ nel momento attuale del nostro calcolo:

3

2

A questo punto ragioniamo dal punto di vista della nuova istanza. Essanon ha nessun bisogno di sapere le istanze attualmente presenti. Deve sem-plicemente affrontare il suo problema, cioe il calcolo di fatt(2). Essendocomunque un’istanza dello stesso algoritmo fara la stessa cosa che abbiamofatto nell’istanza precedente: dapprima controlla se puo risolvere subito ilproblema utilizzando il caso base e, non essendo questo il caso, crea unanuova istanza di se stessa che risolva per lei il problema, piu piccolo, del cal-colo di fatt(2−1), cioe fatt(1), che e proprio cio che gli serve per risolvereil suo problema. La pila di scatole quindi cresce e diventa:


3

2

1

Notiamo come a questo punto nessuna delle istanze che sono presenti hacalcolato il benche minimo valore. Si sono solo limitate a creare l’istanzaper il problema piu piccolo che a loro interessa. Si noti inoltre che in ognimomento l’istanza ‘attiva’, cioe quella che e in esecuzione, e quella il cuiambiente si trova in testa alla pila di ambienti. In questo momento quindie l’istanza con input n = 1 ad essere attiva. Essa, come le sue precedenti,non e in grado di risolvere il suo problema e genera la relativa istanza percalcolare fatt(1− 1), cioe fatt(0). La situazione e quindi la seguente:

3

2

1

0

L’istanza attualmente attiva e finalmente in grado di risolvere il suo pro-blema! Esso corrisponde proprio al caso base e quindi, senza ulteriori passi,essa termina la sua esecuzione e ‘comunica’ che il risultato e 1=fatt(0).


A questo punto entra in gioco il meccanismo della pila. Quando unaistanza termina la sua esecuzione il meccanismo prevede che il suo ambiente,che si trova sicuramente in testa alla pila, venga tolto e buttato via. L’istanzail cui ambiente si viene a trovare in testa alla pila dopo questa operazionediventa quindi l’istanza attiva. Si noti che questa corrisponde esattamenteall’istanza che aveva creato quella attualmente terminata e che era in attesaproprio del risultato che e stato comunicato. Quindi ora, come specificatosopra, essa copia tale valore nello spazio del suo ambiente relativo al valoreintermedio:

3

2

1

1

All’istanza non resta altro che applicare la definizione ricorsiva e molti-plicare il suo input (n = 1) per il valore intermedio che corrisponde a proprioa fatt(n− 1), cioe fatt(1− 1), cioe fatt(0). Il risultato e quindi 1 · 1 = 1.L’istanza puo terminare e comunicare che il risultato e 1.

A questo punto di nuovo interviene il meccanismo della pila e vieneriattivata l’istanza sottostante. Essa si preoccupa di copiare il risultatodel calcolo della istanza che lei aveva generato nel suo spazio per il valoreintermedio:

3

2

1

Difatti fatt(1) e proprio 1. L’istanza procede quindi a moltiplicare il suoinput per il risultato intermedio ottenendo come risultato che fatt(2) = 2.


Poi termina e comunica tale risultato. Il meccanismo della pila entra inazione e si riattiva la prima istanza, quella che aveva dato il via a tutto, checopia il risultato nel suo ambiente:

3

2

Finalmente siamo arrivati in fondo al calcolo. L’istanza corrente molti-plica 3·2 ottenendo come risultato fatt(3) = 6. Dopo di questo essa terminae comunica tale risultato. Essendo la pila di scatole diventata vuota non c’enessun’altra cosa da fare. Il nostro algoritmo, basato sulla definizione ri-corsiva, ha portato a termine il suo compito e ha calcolato correttamente ilrisultato.

E facile convincersi che facendo partire l’algoritmo su un altro input ilprocedimento puo essere facilmente ripetuto in maniera meccanica. Se ilnumero in input e n possiamo prevedere che la pila, durante l’esecuzione,crescera fino a diventare alta n + 1 per poi cominciare a decrescere finoa ridiventare alta 1. In quella istanza (la prima del nostro procedimento)si potra calcolare direttamente il valore di fatt(n), terminare svuotandocompletamente la pila e comunicare il risultato.

Esercizio 3.1 Provare a fare il calcolo, disegnando la pila, di fatt(4) efatt(5).

Il meccanismo che abbiamo visto e quello che viene effettivamente usatonei linguaggi di programmazione per calcolare le funzioni ricorsive. C’e dadire che tutti i linguaggi di programmazione di alto livello che permettono ladefinizione di funzioni ricorsive si occupano automaticamente della gestionedella pila. In altre parole essi permettono di specificare direttamente la fun-zione come definizione ricorsiva, con l’intesa che poi al momento del calcoloutilizzeranno il meccanismo delle chiamate ricorsive cosı come l’abbiamovisto per calcolare il risultato. Questo rappresenta un grande vantaggioper i programmatori, poiche essi non devono prevedere nella scrittura delprogramma la presenza della pila e la sua gestione.

Ricapitolando, abbiamo visto come la ricorsione e l’induzione siano duestrumenti molto potenti sia per dare definizione precise di oggetti con unacerta struttura sia per definire algoritmi che fanno dei calcoli su questestrutture.

Durante tutto il corso incontreremo molte definizioni induttive e moltialgoritmi definiti ricorsivamente. Uno degli obiettivi di questo corso e pro-prio quello di imparare a scrivere definizioni induttive e algoritmi ricorsiviche risolvano correttamente un dato problema.


3.4 Definizioni per induzione

Durante il corso useremo spesso una tecnica di definizione chiamata defini-zione per induzione o induttiva. Le definizioni induttive sono molto frequentinella teoria dei linguaggi e in generale in tutta l’informatica. Basti pensa-re ad esempio che la sintassi dei linguaggi di programmazione viene datatramite una definizione induttiva basata sul formalismo delle grammatichelibere dal contesto (che vedremo). La ragione per cui questa tecnica e cosıusata in questi ambiti e legata al fatto che essa

• permette di definire insiemi infiniti di oggetti tramite un numero finitodi regole

• si adatta perfettamente alla definizione di oggetti (nel nostro casostringhe di linguaggi formali, ma in generale si usa per definire og-getti matematici e ‘informatici’ piu complessi come funzioni, domini,strutture dati, ecc.) che hanno una struttura ben precisa, univoca egeneralmente ricorsiva

Queste definizioni vengono anche chiamate definizioni costruttive o perinduzione strutturale proprio perche l’enfasi e sul fatto che gli oggetti chevengono definiti hanno una certa struttura e che questa struttura si basasulla costruzione di nuovi oggetti a partire da oggetti dati inizialmente ocostruiti precedentemente in un processo ideale che si svolge passo dopopasso.

3.4.1 Espressioni regolari

In questa sezione definiamo un formalismo alternativo a quello degli automiper specificare i linguaggi regolari. L’insieme delle espressioni regolari su uncerto alfabeto Σ e definito tramite una definizione induttiva.

Definizione 3.2 (Espressioni Regolari) Sia Σ un alfabeto finito. L’in-sieme delle espressioni regolari su Σ e costituito da tutte e sole le espressionigenerate induttivamente come segue.

1. ǫ e una espressione regolare

2. Se a e un simbolo di Σ allora a e un’espressione regolare

3. Siano r ed s due espressioni regolari. Allora:

(i) (r)|(s) e una espressione regolare

(ii) (r)(s) e una espressione regolare

(iii) (r)∗ e una espressione regolare

(iv) (r) e una espressione regolare

3.4. DEFINIZIONI PER INDUZIONE 37

Questa definizione si presenta in maniera differente rispetto alla defini-zione ricorsiva che abbiamo analizzato nella Sezione 3.1. Tuttavia e soloquestione di presentazione. Il meccanismo a cui ci appelliamo e lo stesso epossono essere applicate sia la visione costruttiva sia la visione ‘dall’alto albasso’. Usiamo la visione costruttiva per capire che tipo di insieme abbiamodefinito.

Prendiamo Σ = a, b e costruiamo l’insieme partendo dall’insieme vuotoe calcolando soluzioni intermedie via via piu grandi ad ogni passo. All’inizioabbiamo l’insieme vuoto. Utilizzando i casi base 1. e 2. otteniamo l’insiemedi espressioni regolari ǫ, a, b. I casi induttivi (3.) non danno luogo anessuna espressione perche richiedono di avere gia a disposizione una o dueespressioni regolari per formarne delle altre. La prima soluzione parziale equindi:

ǫ, a, b

Applichiamo il passo induttivo. Per comodita chiamiamo ERn la solu-zione parziale costruita al passo n (n numero naturale). Poniamo ER0 =ǫ, a, b.

In generale, per costruire ERn+1, dobbiamo prendere le espressioni chesono gia in ERn ed inserirle in ERn+1. Poi, usiamo le regole i-iv per aggiun-gerne di nuove prendendo come espressioni r ed s (le variabili usate nelladefinizione) tutte le combinazioni possibili di quelle gia costruite nei passiprecedenti (cioe quelle che troviamo in ERn).

Calcoliamo ER1. Utilizzando la regola (i) e assegnando alle variabili red s tutte le combinazioni di valori possibili otteniamo le espressioni (ǫ)|(ǫ),(ǫ)|(a), (ǫ)|(b), (a)|(ǫ), (a)|(a), (a)|(b), (b)|(ǫ), (b)|(a) e (b)|(b).

Da (ii), alla stessa maniera, si ottengono le espressioni (ǫ)(ǫ), (ǫ)(a),(ǫ)(b), (a)(ǫ), (a)(a), (a)(b), (b)(ǫ), (b)(a) e (b)(b).

Da (iii) si ottengono le espressioni (ǫ)∗, (a)∗ e (b)∗. Da (iv) si ottengonole espressioni (ǫ), (a) e (b). Quindi, la seconda soluzione parziale e:

ER1 =

ǫ, a, b, (ǫ)|(ǫ), (ǫ)|(a), (ǫ)|(b), (a)|(ǫ), (a)|(a), (a)|(b), (b)|(ǫ),(b)|(a), (b)|(b), (ǫ)(ǫ), (ǫ)(a), (ǫ)(b), (a)(ǫ), (a)(a), (a)(b), (b)(ǫ),(b)(a), (b)(b), (ǫ)∗ , (a)∗, (b)∗, (ǫ), (a), (b)

Per calcolare ER2 basta ripetere i passi i-iv prendendo pero, questavolta, tutte le espressioni che abbiamo in ER1 come possibili istanziazionidi r ed s. E facile rendersi conto che il processo puo andare avanti all’infinitoe puo generare sempre nuove espressioni regolari su a, b. Quindi esistonoinfinite espressioni regolari su a, b e sono tutte e sole quelle che possonovenire generate, prima o poi, in questo processo.

Esercizio 3.3 Completare ER1 e calcolare ER2.

La definizione che abbiamo dato comporta un uso eccessivo delle paren-tesi. Le parentesi servono in generale, nelle espressioni, a dare la struttura


della composizione delle varie operazioni. Si pensi ad esempio alle espres-sioni aritmetiche: se non ci fossero le regole di precedenza che conosciamodovremmo scrivere espressioni come ((3 + (4 + (7 ∗ 5))) + (3 ∗ 2) invece chesemplicemente 3+4+7∗5+3∗2. Nell’Esempio 4.9 vedremo come dare delleregole di precedenza e associativita che ci permetteranno di scrivere espres-sioni regolari con molte meno parentesi, allo stesso modo delle espressioniaritmetiche.

Ogni espressione regolare su Σ definisce in maniera univoca un certolinguaggio su Σ. Definiamo induttivamente il linguaggio denotato da ogniespressione regolare:

Definizione 3.4 (Linguaggio denotato) Sia Σ un alfabeto finito. Datauna qualsiasi espressione regolare su Σ, il linguaggio da essa denotato edefinito induttivamente come segue:

1. ǫ denota il linguaggio ǫ

2. Se a e un simbolo di Σ allora a denota il linguaggio a

3. Siano r ed s due espressioni regolari qualsiasi su Σ che denotano ilinguaggi L(r) ed L(s) rispettivamente. Allora:

(i) (r)|(s) denota il linguaggio L(r) ∪ L(s)

(ii) (r)(s) denota il linguaggio L(r) · L(s)

(iii) (r)∗ denota il linguaggio L(r)∗

(iv) (r) denota il linguaggio L(r)

Il teorema di Kleene assicura che l’insieme di tutti i linguaggi denotabilida espressioni regolari e esattamente lo stesso dell’insieme di tutti i linguaggiaccettati da automi a stati finiti, cioe l’insieme dei linguaggi regolari.

Esempio 3.5 Vediamo un esempio di associazione del linguaggio denotatoad alcune espressioni regolari. Per trovarlo basta capire la struttura delleespressioni tramite le parentesi e applicare le regole della definizione. SiaΣ = a, b.

• (a)|(b) denota il linguaggio a, b

• (a|b)(a|b) denota il linguaggio aa, ab, ba, bb,denotabile anche con (((a)(a)|(a)(b))|(b)(a))|(b)(b)

• a∗ denota il linguaggio ǫ, a, aa, aaa, aaaa, . . .

• (a|b)∗ denota il linguaggio di tutte le stringhe formate dalla concatena-zione di un numero qualsiasi di a e b messe in un qualsiasi ordine, piula stringa vuota. Ad esempio ǫ, aab, baababa, a, b, bbbb, aaaa, abab, . . ..

Se due espressioni regolari denotano lo stesso linguaggio diciamo chesono equivalenti.

3.5. RAGIONAMENTO INDUTTIVO 39

3.5 Ragionamento induttivo

In questa sezione vediamo come usare la ricorsione per risolvere i problemiadottando la tecnica risolutiva del ragionamento induttivo.

Si tratta di un modo di ragionare e di porre i problemi che comportal’assunzione di una ipotesi, chiamata ipotesi induttiva, che viene usata comeelemento chiave per la risoluzione del problema.

Una ipotesi induttiva, in generale, dice semplicemente che la chiamataricorsiva su un problema analogo a quello dato, ma di dimensione piu piccola,funziona e da un risultato corretto.

Naturalmente, come per la definizione ricorsiva della funzione fattoriale,questo modo di procedere puo far sorgere forti dubbi ad una visione superfi-ciale. Tuttavia noi sappiamo che in realta ci sara la gestione di una pila chesi occupera di attivare istanze dell’algoritmo su istanze sempre piu piccoledel problema fino ad arrivare ai casi base per poi far decrescere la pila ecalcolare i risultati via via. Se siamo convinti del funzionamento di questomeccanismo non dovremmo avere nessun problema ad assumere come veral’ipotesi induttiva!

Per poter applicare questa tecnica c’e bisogno di individuare una dimen-sione del problema e una scomposizione dello stesso che porti a problemi didimensione piu piccola. Per far questo e necessario operare su oggetti ma-tematici come i numeri naturali o gli insiemi, oppure su strutture chiamatestrutture dati ricorsive. In informatica ne troviamo diverse: liste, pile, code,alberi.

Una lista e esattamente quello che ci si aspetta dal nome: un elencoordinato di oggetti. Perche e una struttura dati ricorsiva? Basta notare chese togliamo da una lista l’elemento iniziale e consideriamo il resto otteniamosempre una lista, ma di dimensioni ridotte! Introduciamo una notazione edefiniamo, ad esempio, tutte le liste formate da numeri naturali:

Definizione 3.6 (Liste di numeri naturali) L’insieme di tutte le listedi numeri naturali e definito induttivamente come segue:

(i) nil e una lista di numeri naturali vuota

(ii) Se ℓ e una lista di numeri naturali e n un numero naturale allora n: : ℓe una lista di numeri naturali.

Per comodita possiamo introdurre anche una notazione non ricorsiva:rappresentiamo la lista vuota con [ ] e una lista non vuota con gli elementitra parentesi quadre separati da virgole: [4] (nell’altra notazione: 4: :nil ),[4,0](4: : (0: :nil )), [2,4,6,7] (2: : ℓ dove ℓ = [4,6,7]).

Sulle liste si possono porre moltissimi problemi e si puo dire che, in varieforme, sono una delle strutture piu usate nei programmi informatici.


Proviamo ora a scrivere in pseudocodice una funzione ricorsiva che risolveun problema molto comune sulle liste, cioe calcolarne la lunghezza.

Per utilizzare il ragionamento induttivo dobbiamo usare l’operazione checi permette di ottenere una lista piu piccola da una data, cioe quella di isolarel’elemento iniziale. Formuliamo quindi il problema in questi termini:

Se ho una lista ℓ allora questa puo essere la lista vuota nil oppureuna lista del tipo m: : ℓ′, dove ℓ′ e una lista piu piccola di ℓ. Nelprimo caso la lunghezza e zero, nel secondo caso la lunghezza ela lunghezza di ℓ′ piu uno.

L’ipotesi induttiva in questo caso da uno strumento decisivo: se ho lalista ℓ = m: : ℓ′ e chiamo ricorsivamente la funzione su ℓ′ ottengo comerisultato effettivamente la lunghezza di ℓ′. A quel punto trovare la lunghezzadi ℓ e molto semplice:

La funzione length e spesso definita in questo modo:

length(ℓ) =

0 se ℓ = nil1 + length(ℓ′) se ℓ = m: : ℓ′

Come si vede anche da questo semplice esempio l’ipotesi induttiva e ilragionamento induttivo sono decisivi per la risoluzione del problema. Unavolta ben impostati questi due elementi la soluzione richiede solo un piccoloadattamento finale al problema principale posto in input (in questo caso ℓ).

Esempio 3.7 Scriviamo una funzione ricorsiva che risponde sı se una datalista ℓ contiene un dato elemento n, no altrimenti.

Se la lista e vuota allora non contiene l’elemento, se la lista e m: : ℓ′ em = n allora la lista contiene l’elemento, se invece n 6= m allora bisognavedere se ℓ′ contiene l’elemento m.

search(n, ℓ) =

no se ℓ = nilsı se ℓ = m: : ℓ′ e m = nsearch(n, ℓ′) se ℓ = m: : ℓ′ e m 6= n

Consideriamo ora la seguente definizione induttiva di tutte le pile chepossono contenere cifre binarie nelle loro posizioni:

1. La pila vuota, indicata con Ω, e una pila

2. Se σ e una pila e b ∈ 0, 1 allora b.σ e una pila

Esercizio 3.8 Si imposti la procedura costruttiva che permette di trovarepasso dopo passo tutte le pile definite da questa definizione (si arrivi almenofino al quarto passo di costruzione).

3.5. RAGIONAMENTO INDUTTIVO 41

p

q q r

p

r

p

Radice

Etichetta

Foglia

Figli

Figura 3.1: Un esempio di albero.

Gli alberi sono strutture ricorsive. Un albero e formato da nodi, ognunoetichettato con qualche informazione (ad esempio un simbolo). Ogni nodopuo avere un certo numero di figli che sono altri nodi. Se un nodo non hafigli viene detto foglia. Il nodo iniziale (che non ha padre) viene detto radice(si veda la Figura 3.1).

Ogni nodo di un albero puo essere visto a sua volta come la radicedi un albero piu piccolo (chiamato sottoalbero). Cerchiamo una notazioneadatta e definiamo induttivamente l’insieme di tutti gli alberi i cui nodi sonoetichettati da un simbolo dell’insieme p, q, r.

Un modo classico e quello di rappresentare un albero generico come unacoppia (a, ℓ) dove a e il simbolo che fa da etichetta alla radice e ℓ e una lista(anche vuota) dei sottoalberi, a loro volta rappresentati come coppie.

Ad esempio, per rappresentare in questo modo l’albero di esempio dellaFigura 3.1 scriviamo: (p, [(q, []), (q, []), (r, [(p, [(r, [])]), (p, [])])]).

Diamo la definizione induttiva:

(i) (x, []) dove x ∈ p, q, r e un albero.

(ii) Se T1, T2, . . . , Tn, (n > 0) sono alberi e x ∈ p, q, r allora (x, [T1, T2, . . . , Tn])e un albero.

Esercizio 3.9 Si provi a fare almeno tre passi di costruzione di soluzioniparziali basate sulla definizione induttiva data.

Scriviamo ora una funzione ricorsiva che, dato un albero qualsiasi diquelli della definizione data, calcoli il numero dei nodi di quell’albero chesono etichettati con p o con r.


Per risolvere questo problema possiamo applicare il seguente ragiona-mento induttivo.

Se l’albero T dato in input e una foglia, cioe T = (x, []), allorase x = p oppure x = r possiamo rispondere 1, altrimenti 0. Seinvece l’albero non e una foglia, cioe T = (x, [T1, T2, . . . , Tn]),allora possiamo applicare la funzione ricorsivamente su tutti isottoalberi sommando i risultati. Alla fine, per ottenere il ri-sultato complessivo per il problema T , aggiungiamo 1 se x = poppure x = r.

La funzione e la seguente:

countpr(T ) =

1 se T = (x, []), x = p o x=r0 se T = (q, [])1 +

∑

n

i=1countpr(Ti) se T = (x, [T1, T2, . . . , Tn]), x = p o x=r

∑

n

i=1countpr(Ti) se T = (q, [T1, T2, . . . , Tn])

Capitolo 4

Grammatiche libere dal

contesto

Ogni linguaggio di programmazione ha delle regole che prescrivono la strut-tura sintattica dei programmi ben formati del linguaggio. Ad esempio inPascal un programma corretto e formato da blocchi, i blocchi sono formatida statements, gli statements da espressioni, le espressioni dai token e cosıvia.

Noi conosciamo gia gli automi come strumento per descrivere dei lin-guaggi, ma vedremo che essi offrono dei meccanismi troppo semplici perpoter specificare esattamente le regole sintattiche dei costrutti dei linguaggidi programmazione.

La sintassi dei linguaggi di programmazione richiede un formalismo piupotente. Essa puo essere ed e convenientemente specificata tramite gram-matiche libere dal contesto (context-free grammars). Lo stesso formalismoviene a volte chiamato anche notazione BNF (Backus-Naur Form).

Le grammatiche offrono vantaggi significativi sia ai progettisti dei lin-guaggi di programmazione che ai loro implementatori. Vediamo i principali:

• Una grammatica da una specifica sintattica precisa e relativamentefacile da capire di un linguaggio.

• Per alcune classi di grammatiche si possono costruire automaticamentedegli analizzatori efficienti che determinano se un certo programmasorgente e sintatticamente ben formato e, in caso positivo, ne rendonodisponibile la struttura gerarchica ad albero. Inoltre il processo dicostruzione dell’analizzatore stesso riesce a rilevare ambiguita nelladefinizione della grammatica o ad individuare alcuni costrutti criticidifficili da analizzare. Questo tipo di problemi possono facilmentepassare inosservati nella fase iniziale di progetto di un linguaggio equesta possibilita e un valido supporto per i progettisti.

43

44 CAPITOLO 4. GRAMMATICHE LIBERE DAL CONTESTO

• Una grammatica ben progettata impone una struttura al linguaggioe questa struttura e utile per la traduzione, da parte del compilatore,dei costrutti in codice oggetto. Questo processo di traduzione puoessere fatto automaticamente dando le specifiche giuste ai generatoriautomatici di analizzatori.

• Un linguaggio puo evolvere nel tempo acquisendo nuovi costrutti e/oeseguendo nuove operazioni. Questi nuovi costrutti possono essereaggiunti piu facilmente se il linguaggio e stato implementato sulla basedi una grammatica.

In questo capitolo introdurremo le grammatiche libere dal contesto e lerelative nozioni di albero di derivazione e ambiguita.

4.1 Grammatiche libere dal contesto

Partiamo definendo formalmente gli oggetti che servono per specificare unagrammatica.

Definizione 4.1 Una Grammatica libera dal contesto e una tupla G =〈Σ, V, S, P 〉 dove:

• Σ e un insieme finito dei simboli di alfabeto o Simboli Terminali

• V e un insieme finito di simboli che rappresentano Categorie Sintat-tiche o simboli non terminali

• S ∈ V e un simbolo di categoria sintattica indicato come iniziale oprincipale

• P e un insieme finito di regole, chiamate Produzioni, della forma

A → X1X2 · · ·Xk

dove:

– A ∈ V e la testa o parte sinistra della produzione

– ∀i ∈ 1, . . . , k. Xi ∈ (V ∪Σ). La stringa X1X2 · · ·Xk ∈ (V ∪Σ)∗

si chiama corpo o parte destra della produzione.

Il corpo di una produzione puo anche essere vuoto. In questo caso laproduzione viene scritta A → ǫ.

In alcuni testi l’operatore ::= e usato a posto della freccia → nellascrittura delle produzioni. Le due notazioni sono equivalenti.

4.1. GRAMMATICHE LIBERE DAL CONTESTO 45

Esempio 4.2 Prendiamo un alfabeto Σ = a, b di simboli terminali. Pren-diamo un insieme S,A di simboli non terminali. Prendiamo S come sim-bolo iniziale. Con questi ingredienti possiamo scrivere molti insiemi P diproduzioni. Ad esempio un possibile P potrebbe essere:

S → a, S → aSS, S → ASab, S → bSa,A → aSa,A → bba,A → aASa,A → bS,A → Aa,A → aA

Oppure piu semplicemente: S → aSb, S → aA,A → aA,A → ǫ.Si noti che le produzioni hanno restrizioni solo nella parte a sinistra dellafreccia, dove e obbligatorio che ci sia uno e uno solo simbolo non termi-nale. Nella parte destra invece ci puo essere una qualunque stringa, anchevuota, di simboli terminali o no. Quindi ad esempio aA → abS non e unaproduzione.

Il compito principale di una grammatica e quello di generare stringhe disimboli terminali. Il processo di generazione delle stringhe avviene tramitela costruzione di alberi di derivazione.

Prima di tutto fissiamo alcune convenzioni di notazione che ci permet-teranno di illustrare piu chiaramente i concetti che introdurremo via via nelseguito. Associamo degli insiemi di simboli a certi tipi di oggetti formaliche tratteremo spesso. In questo modo eviteremo di dover specificare, ognivolta che useremo un simbolo nuovo, che cosa quel simbolo sta ad indicare.

1. I seguenti simboli indicano simboli terminali della grammatica:

• Lettere minuscole all’inizio dell’alfabeto:

a, b, c, . . . , a′, a′′, . . . , a1, a2, . . .

• Simboli di operatori: +, −, ∗, . . .

• Simboli di punteggiatura come virgole, punti e virgola, due punti,punti, . . .

• Le cifre 0,1,. . . ,9.

• Stringhe in grassetto come id o if.

2. I seguenti simboli indicano simboli non terminali della grammatica:

• Lettere maiuscole all’inizio dell’alfabeto:

A,B,C, . . . , A′, A′′, . . . , A1, A2, . . .

• La lettera S che in genere indica il simbolo iniziale della gram-matica (a meno che non sia specificato diversamente)

• Stringhe in minuscolo e in corsivo come ad esempio expr o stmt.


• Stringhe qualsiasi tra < e > come ad esempio < OP > oppure< AB >.

• Parole in carattere monospace con eventuali underscore per se-parare: Decl, Com, Stat List, Method Declaration List.

3. Le lettere maiuscole alla fine dell’alfabeto:

X,Y,Z, . . . ,X ′,X ′′, . . . ,X1,X2, . . .

rappresentano un simbolo terminale o non terminale, cioe simbolinell’insieme Σ ∪ V .

4. Le lettere minuscole alla fine dell’alfabeto:

u, v, w, x, y, z, . . . , u′, x′, . . . , x1, v2, . . .

rappresentano stringhe di soli simboli terminali (anche vuote), cioeelementi di Σ∗.

5. Le lettere minuscole dell’alfabeto greco:

α, β, δ, γ, . . . , α′, α′′, . . . , β1, γ2, . . .

rappresentano stringhe, anche vuote, formate da simboli terminali onon terminali, cioe elementi di (V ∪Σ)∗. Tramite le convenzioni vistefino ad ora, vediamo che una generica produzione della grammaticapuo essere indicata con A → α.

6. Se A → α1, A → α2, . . . , A → αk sono tutte le produzioni con lo stessosimbolo a sinistra A (le chiamiamo A-produzioni), allora possiamoscrivere equivalentemente A → α1 | α2 | · · · | αk. Le αi, i = 1, 2, . . . , ksono chiamate alternative per A.

7. A meno che non si specifichi diversamente, assumeremo che la partesinistra della prima produzione data per una grammatica sia il simboloiniziale.

4.2 Alberi di derivazione

Il modo piu semplice di generare una stringa da una grammatica e quello dicostruire un albero di derivazione.

Definizione 4.3 (Albero di derivazione) Sia G = 〈Σ, V, S, P 〉 una gram-matica libera dal contesto. Un albero di derivazione di G e un albero in cui inodi sono etichettati con i simboli della grammatica Σ∪ V e sono rispettatele seguenti proprieta:

4.2. ALBERI DI DERIVAZIONE 47

1. La radice dell’albero e etichettata con il simbolo iniziale S

2. Ogni foglia dell’albero e etichettata con un simbolo terminale

3. Ogni nodo interno dell’albero e etichettato con un simbolo non ter-minale A i cui figli, presi da sinistra a destra, sono etichettati coni simboli X1 X2 · · ·Xn della parte destra di una qualche produzioneA → X1X2 · · ·Xn in P .

La stringa w che si ottiene concatenando i simboli associati alle fogliedi un albero di derivazione, percorrendo i nodi dell’albero da sinistra versodestra, si chiama stringa associata all’albero di derivazione. Diciamo ancheche un albero e un albero di derivazione per w se w e la sua stringa associata.

Nel contesto dell’analisi sintattica l’albero di derivazione viene anchechiamato parse tree.

Si noti che la precedente definizione fissa in maniera precisa e rigorosa ilmodo di costruire gli alberi di derivazione di una certa grammatica e, quindi,le relative stringhe.

Consideriamo la grammatica

G = 〈a, b, S,A, S, S → aS, S → bAa,A → aA,A → b〉

Proviamo a costruire un albero di derivazione. Innanzitutto la regoladice che la radice deve essere etichettata con il simbolo iniziale, in questocaso S.

A questo punto ci troviamo con un albero in cui l’unico nodo e una fogliaed e etichettato con il simbolo non terminale S. Questo non e ammesso dalladefinizione precedente: per poter arrivare a costruire un albero di derivazionedobbiamo espandere questo nodo.

Il punto 3 della definizione ci dice che ogni nodo interno, cioe espanso,deve avere come figli i simboli della parte destra di una produzione in cui latesta e il simbolo non terminale che etichetta il nodo stesso. In questo casoil simbolo e S.

Per decidere quali sono i figli possiamo scegliere tra due produzioni:S → aS oppure S → bAa. Scegliamo la prima e costruiamo i figli di questonodo come indicato nella definizione (in genere negli alberi di derivazionenon si disegnano i nodi degli alberi come cerchi, ma si mettono solo i simboliche li etichettano):

S

SaA questo punto abbiamo una foglia etichettata con il simbolo terminale a,

che non e quindi ulteriormente espandibile. Invece il nodo appena generatoetichettato con S e ancora espandibile. Di nuovo possiamo scegliere qualeproduzione utilizzare per espanderlo. Possiamo scegliere di nuovo la prima:


S

Sa

a S

Ci troviamo nella stessa situazione e potremmo continuare ad espanderel’albero in questo modo quante volte vogliamo. Per questo esempio, a questopunto, scegliamo l’altra produzione che ha come simbolo di testa S, cioeS → bAa:

S

Sa

a S

b A a

Adesso l’unico nodo espandibile e etichettato con A. Quindi dobbiamoscegliere tra le due produzioni che hanno come simbolo di testa A, cioeA → aA e A → b. Scegliamo la prima:

S

Sa

a S

b A a

a A

Di nuovo, possiamo scegliere quale produzione applicare:

4.2. ALBERI DI DERIVAZIONE 49

S

Sa

a S

b A a

a A

Aa

Ancora:S

Sa

a S

b A a

a A

Aa

Aa

A questo punto possiamo decidere di usare la seconda produzione:


S

Sa

a S

b A a

a A

Aa

Aa

bL’albero attuale non ha piu foglie etichettate con simboli non terminali,

quindi e, secondo la definizione, un albero di derivazione della grammaticadata.

Per conoscere la stringa associata a questo albero basta concatenare tuttii simboli terminali partendo dalla foglia piu a sinistra fino alla foglia piu adestra. In questo caso: aabaaaba.

Esercizio 4.4 Costruire altri alberi di derivazione della grammatica data edeterminare le stringhe associate.

Esempio 4.5 Consideriamo la seguente grammatica:

E → E + E | E ∗ E | (E) | −E | id

I simboli terminali sono (, ),+, ∗,−, id. L’unico simbolo non terminale e Eche e, ovviamente, anche il simbolo iniziale.

L’albero in Figura 4.1 e un albero di derivazione la cui stringa associatae id+ id ∗ id.

Tramite gli alberi di derivazione e la nozione di stringa associata pos-siamo definire precisamente cosa si intende per linguaggio generato da unagrammatica.

Definizione 4.6 (Linguaggio generato) Sia G = 〈Σ, V, S, P 〉 una gram-matica libera dal contesto. Il linguaggio generato da G e indicato con L(G)ed e l’insieme delle stringhe di w ∈ Σ∗ tali che esiste un albero di derivazionedi G la cui stringa associata e w.

4.3. SCRITTURA DI GRAMMATICHE 51

E

E + E

id

E * E

id id

Figura 4.1: Un albero di derivazione per id+ id ∗ id.

Ad esempio, il linguaggio generato dalla grammatica usata precedente-mente come esempio per fare alberi di derivazione e

L = an b am ba | n,m ≥ 0

4.3 Scrittura di grammatiche

Il formalismo delle grammatiche libere dal contesto mette a disposizione po-chi e semplici strumenti per la descrizione dei linguaggi, ma questi meccani-smi, se ben usati e combinati, permettono di definire quasi tutti i costruttidei tipici linguaggi di programmazione.

In questa sezione analizziamo da un punto di vista piu concreto questimeccanismi e vediamo quali sono le tecniche di base per usarli.

Innanzitutto c’e da notare che se non ci sono definizioni ricorsive (diretteo indirette) nelle produzioni di una grammatica allora subito possiamo direche il linguaggio generato e un insieme finito. Infatti e grazie alla ricorsioneche possiamo generare un numero infinito di parole con un numero finito diproduzioni.

Ad esempio la grammatica

S → aA|bBA → ab|cB → ba|c

non contiene ricorsione e il linguaggio generato e semplicemente l’insiemeaab, ac, bba, bc.

La ricorsione puo essere diretta o mutua. La ricorsione e diretta quandoin una produzione il simbolo di testa e usato anche all’interno del corpoalmeno una volta. Un esempio di ricorsione diretta e quello nella produzioneA → aA nella seguente grammatica:


S → aA|bBA → aA|cB → ba|c

L’introduzione di questa ricorsione ha incrementato il linguaggio generatodi un numero infinito di parole. Il linguaggio ora e bba, bc∪an c | n > 0.

Il precedente e un esempio classico (chiamato ricorsione semplice a destrao ricorsione di coda) con il quale si possono generare parole del tipo x an ydove n puo essere positivo o anche zero e x e y sono delle stringhe prefissoe suffisso. Vediamo tutti i casi:

• Poniamo n ≥ 0, x = ǫ, y = b. Le produzioni che possiamo scrivere sonoS → aS | b. In questo modo il caso n = 0 e generato direttamente conil caso base della ricorsione (S → b) e il caso ricorsivo genera tutte lealtre stringhe con n > 0 a terminando con il caso base b.

• Poniamo n > 0, x = ǫ, y = b. Le produzioni che possiamo scriveresono S → aS | ab. Inserendo nel caso base una a evitiamo di scriveresolo una b e otteniamo che n > 0 in tutte le stringhe generate.

• Poniamo n > 0, x = b, y = ǫ. Questa volta dobbiamo inserire, all’iniziodelle stringhe, qualcosa di diverso dalle a. Ci sono due modi per farlo:

1. Utilizzare una ricorsione a sinistra (cioe il simbolo di testa si trovaall’inizio del corpo della produzione): S → Sa | ba. Il caso n > 0ci ha obbligato a inserire una a nel caso base.

2. Utilizzare un simbolo non terminale in piu per inserire il prefissoe poi generare, con ricorsione a destra, le a: S → bA, A → aA | a.Nel caso n ≥ 0 qui metteremmo, come caso base della ricorsionedestra su A, la stringa vuota: S → bA, A → aA | ǫ.

• Poniamo n ≥ 0, x = b, y = c. Nel caso di un prefisso e di un suffissosiamo obbligati a usare un simbolo in piu per il prefisso: S → bA,A → aA | c. Anche qui, per n > 0, avremmo messo come caso baseac.

Un’altra applicazione molto usata della ricorsione diretta e quella chepotremmo chiamare “centrale” e che mette il simbolo che ricorre all’internodi due stringhe di terminali, in modo da generare, nelle chiamate ricorsive,un numero uguale di simboli a destra e a sinistra. L’esempio classico e:S → aSb | ab che genera il linguaggio an bn | n > 0. Il caso base, inquesto tipo di applicazione, rappresenta la stringa che va a finire all’internodei simboli generati in numero uguale.

Facciamo un altro esempio: una grammatica per il linguaggio a2n bb cn |n ≥ 0 e S → aaSc | bb. La ricorsione “centrale” e usata per generare

4.3. SCRITTURA DI GRAMMATICHE 53

eventuali copie di aa e c in numero uguale e il caso base bb puo venire usatosubito (n = 0) o dopo alcune applicazioni della prima produzione (n > 0).

Ovviamente e possibile usare insieme e annidare i due tipi principali diricorsione diretta che abbiamo visto. Ad esempio nella grammatica

S → aSb | cBB → bB | dd

viene annidata una ricorsione destra (con un prefisso c e un suffisso dd) all’in-terno di una ricorsione “centrale”. Il risultato e il linguaggio an c bm dd bn |n,m ≥ 0. Si noti che le b generate dalla ricorsione “centrale” sono in ugua-le numero delle a, mentre quelle interne hanno un numero di occorrenzeindipendente.

Le varianti di questo schema possono riguardare i casi base e i prefis-si/suffissi. Ad esempio, volendo specificare lo stesso linguaggio, ma conn > 0, saremmo costretti a inserire sia una a che una b anche nella secondaproduzione in questo modo:

S → aSb | acBbB → bB | dd

Il caso m > 0, invece ci avrebbe portato a

S → aSb | cBB → bB | bdd

Un altro caso interessante e quello in cui le b interne non hanno suffisso:

S → aSb | cBB → bB | ǫ

Ora il linguaggio si puo scrivere anche come an c bm | m ≥ n > 0poiche le b interne si sommano a quelle alla fine delle stringhe. Dato che leb finali sono sempre in egual numero alle a iniziali si ha che il vincolo m ≥ nesprime esattamente la situazione. Se il caso base di B fosse b invece che ǫallora avremmo che c’e sempre almeno una b interna e, di nuovo, potremmoesprimere la cosa con il vincolo m > n.

La mutua ricorsione e meno usata della ricorsione diretta poiche e menochiara e puo indurre facilmente in errore. Vediamone solo un esempio:

S → aAA → bBB → bA | c

Come si vede non c’e ricorsione diretta in nessuna produzione, ma laproduzione di A chiama B e una produzione di B chiama A. Il caso base esolo nelle produzioni di B. In questi casi si puo semplificare trasformando


la grammatica in una equivalente con ricorsione diretta. Basta sostituire, aposto di A, la parte destra della sua unica produzione:

S → abBB → bbB | c

Il linguaggio e a b2n+1 c | n ≥ 0.Per concludere ricordiamo solamente che di fronte alla richiesta di dare

una grammatica per un certo linguaggio e bene cercare sempre di dividerele stringhe del linguaggio in diversi casi, ognuno riconducibile a uno schemanoto: ricorsione destra, sinistra o “centrale”.

Facciamo un esempio finale. Supponiamo di voler dare una grammaticaper il seguente linguaggio:

L = an b cm d am | n ≥ 0,m > 0 ∪ bk a2n | k, n ≥ 0

Innanzitutto possiamo notare che il linguaggio e gia naturalmente divisoin due casi dall’unione. Il primo caso e riconducibile a una ricorsione destracon suffisso (an b) seguita da una ricorsione centrale (cm dam) e il secondocaso e la semplice giustapposizione di due ricorsioni destre:

S → A | BCA → aA | bcDaD → cDa | dB → bB | ǫC → aaC | ǫ

4.4 Ambiguita

Una questione importante che riguarda le grammatiche libere dal contestonel loro uso come generatori di linguaggi di cui viene effettuato il parsing el’ambiguita.

Intuitivamente possiamo vedere la scrittura di una grammatica come ladefinizione di un algoritmo (ricorsivo) per generare le stringhe di un linguag-gio. Questo algoritmo usa le produzioni e costruisce un albero di derivazioneper una certa stringa data. E facile vedere che durante la generazione di unastringa l’algoritmo (cioe la grammatica) impone certe scelte che riflettono lastruttura delle produzioni. La questione dell’ambiguita puo essere vista in-tuitivamente nel seguente modo: la grammatica e ambigua se le produzionipermettono, in almeno un caso, di seguire almeno due strade differenti pergenerare una stessa stringa. Si noti che basta che esista una sola stringa percui questo e vero e tutta la grammatica diventa ambigua. Da questo ap-proccio intuitivo si puo anche ricavare una giustificazione del fatto che fare ilparsing di grammatiche ambigue risulta molto difficoltoso: il parser che cer-ca di analizzare una stringa che puo essere generata in due (o piu) modi non

4.4. AMBIGUITA 55

sa decidere quale strada seguire, fra le possibili, nella ricostruzione dell’al-bero. Inoltre la struttura “troppo libera” delle produzioni rende difficoltosal’analisi anche delle stringhe che hanno un solo albero di derivazione.

Dopo questa premessa informale definiamo formalmente quando unagrammatica e ambigua:

Definizione 4.7 (Ambiguita) Una grammatica libera dal contesto G sidice ambigua se e solo se esiste una stringa w ∈ L(G) tale che esistono duealberi di derivazione T e T ′ di G con le seguenti proprieta:

• T e T ′ sono diversi

• T e T ′ hanno w come stringa associata

Di converso, G non e ambigua se per ogni stringa w ∈ L(G) esiste unoed un solo albero di derivazione di G che ha w come stringa associata.

Esempio 4.8 Consideriamo la seguente grammatica:

E → E +E | E ∗ E | (E) | id

Questa grammatica e ambigua poiche per la stringa id+ id ∗ id esistonoi due alberi di derivazione mostrati in Figura 4.2.

Un indizio che indica spesso che una grammatica e ambigua e il fattoche in almeno una produzione e usata la ricorsione “doppia”, cioe il simboloa sinistra della produzione occorre almeno due volte nella parte destra. Eindicativo soprattutto se la grammatica genera un linguaggio con operatoribinari come quello dell’esempio precedente.

In generale e molto difficile dimostrare che una grammatica non e ambi-gua poiche bisogna dimostrare l’unicita dell’albero di derivazione per tuttele stringhe del linguaggio. Dimostrare invece l’ambiguita e semplice: bastaesibire un controesempio, cioe una stringa per cui esistono almeno due alberidi derivazione diversi. Per capire se una grammatica e ambigua oppure no ebene innanzitutto cercare di capire il linguaggio generato dalla stessa e poicapire come vengono generate le stringhe: se c’e un algoritmo che imponedelle scelte per ogni tipo di stringa generabile oppure se le produzioni lascia-no abbastanza liberta tanto da consentire che una certa stringa o un certogruppo di stringhe possano essere generate seguendo diverse strade.

Nella pratica, se si vuole scrivere una grammatica non ambigua perun certo linguaggio, e utile progettare le produzioni in modo tale che lagenerazione di ogni stringa del linguaggio debba seguire una ed una solastrada.

Se una grammatica risulta essere ambigua e deve essere usata per genera-re un parser e bene che sia disambiguata. Infatti molti metodi per generareparser (tra cui tutti quelli che vedremo noi) falliscono se la grammatica cheviene considerata e ambigua.


E

E E

+

id id

E E

id *

E

E E

id id

E E

id+

*

(a) (b)

Figura 4.2: Due alberi di derivazione diversi per la stringa id+ id ∗ id.

La disambiguazione di una grammatica consiste nella riscrittura delle sueproduzioni (anche introducendo o togliendo simboli non terminali) in modotale da lasciare inalterato il linguaggio generato e da avere un solo alberodi derivazione per tutte le stringhe, anche quelle per le quali esistevano piualberi di derivazione associati nella grammatica di partenza.

4.5 Associativita e precedenza degli operatori

La struttura di un albero di derivazione per una certa stringa e molto im-portante nel contesto del parsing e dei compilatori in generale. Infatti, seuna frase di un linguaggio di programmazione viene strutturata in manie-ra corretta rispetto alla sua semantica, la traduzione della stessa risultaestremamente semplice.

Per capire meglio questo aspetto facciamo l’esempio classico delle espres-sioni aritmetiche. Possiamo pensare di usare l’albero di derivazione di unacerta espressione aritmetica per calcolarne il valore. Si consideri ad esempiol’albero in Figura 4.2(a) per la stringa id + id ∗ id. L’osservazione fonda-mentale e che ogni nodo interno etichettato E corrisponde ad una sottoe-spressione il cui valore puo essere calcolato in base ai valori associati ai nodifigli. Ad esempio se il nodo ha un unico figlio etichettato id allora il valoread esso associato e il valore associato all’identificatore in memoria (stiamoparlando della semantica di esecuzione del programma). Se il nodo ha trefigli etichettati con E+E rispettivamente allora il suo valore sara la sommadel valore associato al primo figlio E con il valore associato al secondo figlioE (questi valori sono calcolati ricorsivamente). In questo modo il valoreassociato alla radice e il valore dell’espressione aritmetica.

A questo punto e chiaro perche la struttura dell’albero si rivela fonda-mentale: deve rispecchiare le regole (semantiche) di valutazione delle espres-sioni aritmetiche affinche il valore associato alla radice sia quello giusto. Noi

4.5. ASSOCIATIVITA E PRECEDENZA DEGLI OPERATORI 57

conosciamo queste regole: sono regole di associativita e di precedenza. Adesempio, l’albero di Figura 4.2(b) non puo essere usato per valutare l’espres-sione perche la sua struttura non rispetta la precedenza dell’operatore ∗ dimoltiplicazione rispetto all’operatore + di addizione.

In questa sezione vediamo come esprimere l’associativita e la precedenzafra operatori binari (cioe che prendono due argomenti) con le produzionidella grammatica. L’esempio che useremo via via sara quello delle espressioniaritmetiche con l’addizione, la sottrazione, la moltiplicazione, la divisione ele parentesi tonde fra numeri formati da una sola cifra (per semplificare latrattazione e non introdurre dettagli inutili).

Innanzitutto chiariamo bene cosa intendiamo per associativita e prece-denza.

• Associativita. Prendiamo ad esempio l’operatore +. In una espressio-ne come 3+5+7 non e chiaro a quale + deve essere associato il numero5 poiche ne ha uno a destra e uno a sinistra (+ e un operatore binarioe quindi per essere applicato ha bisogno di due operandi: uno alla suadestra e uno alla sua sinistra in notazione infissa). La regola di asso-ciativita specifica proprio questo punto: se si stabilisce che il + associaa sinistra allora il 5 viene associato al + alla sua sinistra e la strutturasottintesa dell’espressione di cui sopra e la stessa di (3 + 5) + 7 (dovela struttura e stata esplicitata con l’uso delle parentesi). Nel caso diassociativita a destra la struttura sarebbe stata 3 + (5 + 7).

• Precedenza. Prendiamo due operatori classici con precedenza diver-sa: + e ∗. In una espressione come 3 + 5 ∗ 7 ancora una volta non echiaro a quale operatore deve essere associato il 5 centrale. La regoladi precedenza risolve questo punto ponendo gli operatori su livelli di-versi di precedenza. Se, come e di solito, il ∗ ha precedenza maggioredel + allora il 5 viene associato al ∗ e quindi la struttura esplicitatadell’espressione e 3 + (5 ∗ 7).

Per scrivere una grammatica le cui produzioni riflettano le scelte di prece-denza e associativita bisogna innanzitutto definire i vari livelli di precedenza.In ogni livello di precedenza bisogna inserire uno o piu operatori che hannola stessa precedenza (ad esempio il + ed il − nelle espressioni aritmetiche)e per ogni livello si indica se l’associativita deve essere a destra o a sinistra.Per ogni livello definito si crea un simbolo non terminale della grammati-ca. Illustriamo il procedimento di costruzione delle produzioni con l’esempiodelle espressioni aritmetiche. Prendiamo i seguenti livelli di precedenza fragli operatori aritmetici:

1. Fattori (simbolo F), cioe gli operandi. Hanno il maggiore livello diprecedenza per definizione.


2. Termini (simbolo T), cioe applicazione di ∗ o /. Hanno la stessa prece-denza, inferiore a quella dei fattori. L’associativita e a sinistra (comee di solito nei linguaggi)

3. Espressioni (simbolo E), cioe applicazione di + e −. Hanno la prece-denza piu bassa di tutti. L’associativita e a sinistra.

Per il livello piu alto si scrivono semplicemente le produzioni:

F → 0 | 1 | · · · | 9 | (E)

Si noti che una espressione tra parentesi e da considerarsi come un operandopoiche le parentesi forzano l’interpretazione di una espressione permettendodi eludere le regole di precedenza e associativita se occorre.

Nel livello successivo l’associativita a sinistra e espressa mediante la ri-corsione a sinistra nelle produzioni. Una produzione ricorsiva a sinistraprovoca infatti l’addossamento a sinistra degli alberi di derivazione che lausano e questa struttura corrisponde proprio alla regola semantica di calcolocon l’associativita a sinistra. Le produzioni sono:

T → T ∗ F | T/F | F

Si noti che un fattore puo essere sempre visto come un termine (produzioneT → F ).

Per il successivo e ultimo livello si ha:

E → E + T | E − T | T

In generale ogni elemento di un livello puo essere visto come elemento dellivello successivo (in questo caso particolare si guardi la produzione E → T ).

Attraverso l’imposizione delle regole di precedenza e di associativita ab-biamo ottenuto una grammatica non ambigua per le espressioni aritmetiche.In Figura 4.3 e mostrato un albero di derivazione per l’espressione 3+4+5∗7.

Esempio 4.9 La scrittura delle espressioni regolari secondo la definizioneche abbiamo dato nella Sezione 3.4.1 ha il difetto di generare espressioni controppe parentesi, molte volte inutili e che rendono difficile la lettura. Per eli-minare questo inconveniente evitiamo di mettere tra parentesi singoli simbolie assegniamo precedenza e associativita ai tre operatori che costruiscono leespressioni regolari, come segue:

1. L’operatore unario ∗ lega maggiormente. Quindi ad esempio ab∗ staper (a)((b)∗), cioe la stella si riferisce solo a b e la a deve essereconcatenata a b∗. Essendo un operatore unario non c’e associativita.

2. La concatenazione e il secondo operatore che lega maggiormente ed eassociativo a sinistra

4.5. ASSOCIATIVITA E PRECEDENZA DEGLI OPERATORI 59

E

E + T

E +

T

F

F

4

3

T F*T

F

5

7

Figura 4.3: Un albero di derivazione per l’espressione 3 + 4 + 5 ∗ 7.

3. L’operatore che lega meno di tutti e l’or (|). Ad esempio, quindi, a|abva inteso come a|(ab). L’associativita anche qui e a sinistra.

Con queste convenzioni, per fare un altro esempio, l’espressione(a)|((b)∗(c)) puo essere scritta come a|b∗c. Entrambe denotano il linguaggiodelle stringhe che o sono a oppure sono una sequenza, eventualmente vuota,di b seguite da una c. Ancora, l’espressione regolare ((a)|(b))∗ deve esserescritta (a|b)∗ poiche il simbolo | lega meno della stella.

La grammatica che realizza queste regole, per le espressioni regolari sua, b e la seguente:

R → R|C | CC → CS | SS → S∗ | FF → a | b |′′ǫ ′′ | (R)

Il simbolo ǫ nella terza produzione per F e stato messo tra virgolettepoiche rappresenta un simbolo vero e proprio dell’alfabeto da cui si costrui-scono le espressioni regolari, ad esempio (c|ǫ)d. In questo caso, quindi, laproduzione F →′′ǫ ′′ non va considerata come la produzione F → ǫ con ilsignificato usuale.

Dispensa di Sintassi

Documents

Transcript of Dispensa di Sintassi