Linguaggi Formali e Automi

28

Click here to load reader

Transcript of Linguaggi Formali e Automi

Page 1: Linguaggi Formali e Automi

LINGUAGGI FORMALI E AUTOMI

Dispensa Universitaria

Page 2: Linguaggi Formali e Automi

Quest'opera è stata rilasciata sotto la licenza Creative Commons Attribuzione - NonCommerciale - Condividi allo stesso modo. Per leggere una copia della licenza visita il sito webhttp://creativecommons.org/licenses/publicdomain/ o spedisci una lettera a CreativeCommons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Page 3: Linguaggi Formali e Automi

LinguaggioUn linguaggio si basa sul concetto di alfabeto che è un insieme composto dasimboli:

={a1,a2,a3,a4. ...an}

La giustapposizione di questi simboli permette di generare gli elementi dellinguaggio, ossia le parole o stringhe.

La giustapposizione è un'operazione tale che avendo due simboli w e z alloraw∗z=wz . Di conseguenza l w∗z =l w l z . Il prodotto di giustapposizione godedella proprietà associativa ma NON di quella commutativa.

● Associativa: x∗y ∗z=x∗ y∗z

● Commutativa: x∗y≠ y∗x

Una parola o stringa è quindi una composizione di simboli dell'alfabeto e la sualunghezza l w è il numero di simboli che la compongono. Una parola con l w =0 èdetta parola vuota ed è rappresentata da .

Un linguaggio L non è altro che un sottoinsieme di TUTTE le possibili parolegenerabili da un alfabeto . Tale insieme infinito è chiamato *. Quindi:

L⊆ *

In particolare ∈ *, ma ∉ +. + è quindi un sottoinsieme di * contenentetutte le parole possibili esclusa la parola vuota. è il linguaggio vuoto.

Per mezzo del prodotto di giustappozione sono generati casi speciali all'interno di unastessa parola.

● Prefisso di y è quella stringa x tale che y=xz

● Suffisso di y è quella stringa x tale che y=zx

● Fattore di y e quella stringa x tale che y=zxw

Dati due linguaggi si possono applicare le operazioni booleane: Unione, Intersezione,Complemento.

Page 4: Linguaggi Formali e Automi

Due importanti nozioni basate sul prodotto di giustapposizione tra linguaggi riguardanoinoltre il prodotto, la potenza e la chiusura di Kleene.

● Prodotto: L1∗L2={xy∣x∈L1e y∈L2}

● Potenza: L0={} oppure L3=L∗L∗L=L2∗L oppure Ln=L∗Ln−1

● Chiusura di Kleene: L *= L0∪L1∪L2∪..... Ln e L += L1∪L2∪..... Ln

Il prodotto di linguaggi è commutativo solamente su alfabeti unari ossia con un soloelemento eventualmente moltiplicato per se stesso.

In conclusione:

● L * è un linguaggio ottenuto moltiplicando tra loro in tutti i modi possibili tutte leparole del linguaggio L unitamente alla parola vuota ottenendo in questo modo uninsieme infinito.

● L + è lo stesso di L * escludendo la parola vuota.

La fattorizzazione di una parola secondo un dato linguaggio è la scomposizione dellastessa in “sottoparole” presenti nel linguaggio.

Dato un linguaggio L += {0,10} e una parola 0010100 , la sua fattorizzazione è:

0∗0∗10∗10∗0

In questo esempio in particolare la fattorizzazione è unica, nel senso che non èpossibile fattorizzare la parola 0010100 in altro modo. In questo caso abbiamodunque trovato un codice.

● Un codice ha dunque la proprietà esistenziale di univoca decifrabilità.

Formalmente:

Un linguaggio L in cui ogni parola di L + è decomponibile in un unico modo comeprodotto di parole di L è detto codice .

● Ogni linguaggio prefisso è anche un codice. Viceversa non vale che ogni codice èanche prefisso. Questo semplicemente perchè non avendo alcuna parola compostada altre parole, il modo per decomporla è unico.

● Ogni linguaggio con parole di lunghezza uguale è sempre un codice prefisso. Questoperchè ogni parola ha una sua composizione specifica diversa una dall'altraassicurata dal fatto che ogni parola ha sempre lunghezza n .

Page 5: Linguaggi Formali e Automi

RappresentazioniI linguaggi L possono essere descritti e quindi rappresentati in due modi.

1. Se il linguaggio è finito, elencando tutti gli elementi

2. Altrimenti in modo intensivo per mezzo di una proprietà P w del linguaggiostesso tale che L={w∣P w =TRUE } .

Ci sono due sistemi di rappresentazione intensiva: il sistema riconoscitivo e quellogenerativo. I linguaggi possono ammettere entrambi o solamente uno di essi.

Page 6: Linguaggi Formali e Automi

RiconoscitoreIl sistema riconoscitivo funziona in modo da riconoscere se una parola w appartieneo no ad un linguaggio L per mezzo di un algoritmo chiamato riconoscitore che ricevein input la parola w e ritorna 1 se w∈L e 0 se w∉L .

Non tutti i linguaggi ammettono un riconoscitore. Un linguaggio che ammette unriconoscitore è definito ricorsivo o decidibile.

Ci sono due classi di linguaggio ricorsivi, chiamate linguaggi regolari e linguaggiacontestuali. Queste classi ammettono un riconoscitore chiamato rispettivamenteautoma a stati finiti e automa a pila.

Come abbiamo detto non tutti i linguaggi ammettono un riconoscitore. Questi linguaggivengono chiamati ricorsivamente numerabili. Sono classificati ricorsivamentenumerabili i linguaggi che restituiscono 1 se w∈L e vanno in loop se w∉L .

● I linguaggi ricorsivi sono un sottoinsieme dei linguaggi ricorsivamente numerabili.Questo perchè dato un riconoscitore per un linguaggio ricorsivo è facile, una voltaricevuto l'output relativo al caso w∉L , costruire una procedura che entra in loop.

● Il contrario non può essere, perchè è impossibile capire quando un algoritmo èentrato in loop.

Page 7: Linguaggi Formali e Automi

GeneratoreIl secondo modo per descrivere un linguaggio è il sistema generativo. Questo sistemasi basa sul concetto di calcolo logico. Un calcolo logico non riconosce se w∈L , ma nericerca la dimostrazione! Quindi un calcolo logico V x , d riceve in input un parolax , una dimostrazione d e ritorna in output 1 se w∈L e 0 se w∉L . Ossia in altre

parole restituisce 1 se la dimostrazione d permette di affermare che la frase/parolax è vera.

Il calcolo logico ha tre proprietà fondamentali:

● La dimostrazione d verifica in un tempo finito se è o no la dimostrazione di unafrase f .

● Se d è la dimostrazione di f allora f deve essere una affermazione vera(correttezza del calcolo logico) ossia f ∈L .

● Se f è un'affermazione vera allora deve esserci una sua dimostrazione(completezza del calcolo logico) ossia ∃d f ∈L .

Formalmente un calcolo logico è una funzione V :∗xU∗{0,1} . Il calcolo logicolavora di conseguenza nel campo di * e in quello di U * che non è altro chel'insieme infinito delle possibili dimostrazioni.

Vediamo adesso come mai i linguaggi ricorsivamente numerabili ammettono sempre uncalcolo logico corretto e completo. Prendiamo la funzione:

function L (x)

{

n = 1

while (V(x,d)=0)

n = (n+1)

return (1)

}

Nel caso w∈L questa la funzione termina, altrimenti va il loop. Siamo quindipienamente nel caso di linguaggi ricorsivamente numerabili. Dal momento che poiquesta funzione o restituisce 1 oppure non termina, il calcolo logico risulta esserecorretto e completo perchè V x , d =1 sempre se w∈L .

Dato un linguaggio L , se un calcolo logico è corretto e completo per L allora perforza di cose L∈{x∣∃d V x , d =1} .

Page 8: Linguaggi Formali e Automi

Non solamente i linguaggi ricorsivamente numerabili ammettono calcoli logici, però unlinguaggio NON ricorsivamente numerabile ammetterà un calcolo logico al più correttoma incompleto.

Se noi ad esempio forziamo l'uscita dal ciclo while ad un certo numero n (questo perrispettare il fatto di lavorare su linguaggi non ricorsivamente numerabili e quindi chenon ammettono un loop) avremo un calcolo logico completo perchè effettivamentew∈L , ma incompleto in quanto non abbiamo avuto abbastanza tempo da trovare unadimostrazione tale che V x , d =1 .

Page 9: Linguaggi Formali e Automi

GrammaticheUn sistema generativo sono le grammatiche. Una grammatica è una quadrupla

⟨ ,Q , P , S ⟩● eQ sono due alfabeti rispettivamente di simboli terminali e di metasimboli.

● P è l'insieme di regole di produzione

● S è un simbolo chiamato assioma

Innanzi tutto a differenza dei simboli, i metasimboli o simboli NON terminali sonoespressioni atte alla generazione del linguaggio e non sono parole appartenenti allinguaggio.

Le regole di produzione sono essenziali per la creazione di un linguaggio in quantodettano come è possibile articolare un insieme di simboli e metasimboli al fine diottere un linguaggio più completo e complesso.

In generale le regole si produzione sono dichiarate nel seguente modo:

con e due parole di simboli e/o metasimboli tali che

∈∪Q ∗e ∈∪Q ∗.

Infine l'assioma non è altro che il simbolo o il metasimbolo di partenza.

La rappresentazione

⇒G

indica poi la possibilità di derivare un simbolo da un simbolo secondo lagrammatica G in un sol passaggio. Mentre

⇒G∗

indica che si può derivare da con un numero finito di derivazioni.

Proprio grazie alla derivazione possiamo notare come le grammatiche siano calcolilogici in cui la dimostrazione d è la derivazione stessa.

Per ipotesi un linguaggio L è generato da una grammatica solamente se L èricorsivamente numerabile, ma allora L è generabile da una grammatica solamentese per L esiste un calcolo logico corretto e completo.

Un linguaggio L G generato da una grammatica di tipo G è l'insieme delle parolesull'alfabeto derivabili dall'assioma S , ossia:

L G ={w∣w∈∗e S⇒G∗w}

Con grammatiche equivalenti si intende il caso in cui date due grammatiche G1 eG2 :

LG1=LG2

Page 10: Linguaggi Formali e Automi

ClassificazioneLe regole di produzione sono usate per la classificazione delle grammatiche. A secondadel tipo di regola esiste un tipo di grammatica.

Una classificazione importante è l'omonima proposta da Chomsky.

1. Grammatica di tipo 0: qualsiasi tipo di regole di produzione

2. Grammatica di tipo 1: regole di produzione del tipo con l l . E'possibile la regola S purchè S sia l'assioma, ed S non compaia in nessun altraregola.

3. Grammatica di tipo 2: regole di produzione del tipo A con A rigorosamenteun metasimbolo

4. Grammatica di tipo 3: regole di produzione del tipo A B , A oppureA . Dove A e B sono metasimboli e un simbolo.

Una grammatica G genera un linguaggio LG e per questo motivo, laclassificazione delle grammatiche genera a sua volta la classificazione dei linguaggi.

Un linguaggio L è di tipo k (con K = 0,1,2,3) se esiste una grammatica di tipo k che lo ha generato, ossia tale che L=L G .

Si indica con Rk la classe di linguaggi di tipo k. In particolare, secondo laclassificazione di Chomsky, le classi di linguaggi formano tra loro sottoinsiemi proprinel seguente modo:

R3⊆R2⊆R1⊆R0

Riprendendo alcune definizioni fatte precedentemente sui linguaggi si può dire che:

● R0 sono tutti i linguaggi ricorsivamente numerabili.

● R1 sono tutti i linguaggi contenstuali.

● R2 sono tutti i linguaggi acontenstuali.

● R3 sono tutti i linguaggi regolari.

Possiamo notare subito come i linguaggi regolari e acontestuali, introdotti per ilsistema riconoscitivo, siano linguaggi particolari che ammettono anche un sistemagenerativo.

Page 11: Linguaggi Formali e Automi

Parlando in generale non è sempre detto che un linguaggio sia generato da una solagrammatica. Ci possono essere linguaggi generati da classi di grammatiche piùgenerali. Un esempio di ciò sono le grammatiche di tipo 3 e la grammatica lineare adestra.

Una grammatica lineare a destra ha regole di produzione del tipo A x B , A ycon x , y parole. Una grammatica di tipo 3 è anche una lineare a destra, ma ilviceversa non è sempre detto.

Dato infatti una grammatica lineare a destra con regole di produzioneA123 ...mB e A123 ...m , possiamo costruire una grammatica

equivalente introducendo nuovi metasimboli M 1,M 2,M 3 ...M m e sostituendo connuove regole del tipo A123 ...mB .

Alla fine otterremo una grammatica con regole di produzione A B , A ,A e AB . A causa dell'ultima regola la grammatica non è di tipo 3, ma per ogni

derivazione F⇒G∗H possiamo considerare tutte quelle per cui F⇒G∗A e B⇒G∗Haggiungendo la regola F H . Questo perchè è possibile nella grammatica unaderivazione F⇒G∗A⇒G B⇒G∗H che equivale a dire appunto F H .Aggiungiungiamo poi la regola F/ per ogni F per cui F⇒G∗A⇒G/ . Aquesto punto abbiamo una grammatica di tipo 3.

Altri esempi di equivalenza sono dati dalla possibilità di generare un linguaggio di tipo3 da una grammatica di tipo 3 contenente però solamente regole A B e A .Ciò si ottiene introducendo un nuovo metasimbolo M e una nuova regola M esostituendo la regola A con AM . Quindi:

● Se L è di tipo 3 allora è generato da una grammatica di tipo 3 con regole del tipoA B e A .

Il contrario, ossia generare una grammatica equivalente con regole solamente del tipoA B e A non è sempre detto perchè in generale date queste regole allora∉L . Però:

● Se L è di tipo 3 con ∈L , allora L=L '∪{} dove L ' è generato da unagrammatica di tipo 3 con regole del tipo A B e A .

Page 12: Linguaggi Formali e Automi

Automi a statiUn automa a stati A è un sistema

A=⟨ ,Q , , q0 , F ⟩

dove:

● Q è un insieme di stati

● è un alfabeto finito

● è la funzione di transizione

● q0 è lo stato iniziale

● F è l'insime degli stati finali

Se l'insieme Q è finito l'automa prende il nome di automa a stati finiti.

Un esperimento su questo sistema avviene in due fasi:

1. Viene dato come input un messaggio composta da una parola w∈ *.

2. Si osserva il valore di ouput se questo è 1 allora la parola w è accettata altrimentiscartata.

Un sistema simile è conoscibile solamente per mezzo di esperimenti, ossia ilcomportamento del sistema è descritto dalle parole accettate. Questo sistema èquindi un riconoscitore di linguaggio.

Più nel particolare un sistema di questo tipo è composta da un numero finito di stati:

1. Ad ogni istante il sistema si trova su uno stato specifico q∈Q . Per modificare ilsuo stato si deve mettere in ingresso un nuovo messaggio in modo tale da poterassociare il sistema ad un nuovo stato, ossia ad uno stato futuro o prossimo. Lalegge che descrive questa procedura prende il nome di funzione di transizione : xQQ . Per esempio se il sistema è nello stato q ed arriva un messaggio la sua funzione sarà q , .

2. Inizialmente il sistema si trova sempre in uno stato iniziale q0∈Q .

3. L'output del sistema è invece rappresentato dalla funzione di uscita :Q{0,1} ese il sistema finisce in uno stato q allora q . Il sistema inoltre può usciresolamente da uno stato finale. La totalità di questo stati forma l'insieme degli statifinali F={q∣q=1} .

Il linguaggio LA riconosciuto dall'automa A

LA={w∣w∈∗e∗q0 ,w}={w∣w∈∗e∗q0 ,w=1}

Un automa a stati può essere rappresentato graficamente con un diagramma permezzo di cerchi (che rappresentano gli stati) e archi (che rappresentano le possibilitransizioni tra stato e stato). Lo stato iniziale è rappresentato con una freccia iningresso, mentre quello finale con un cerchio concentrico.

Page 13: Linguaggi Formali e Automi

Esempio: A=⟨S ,Q , , q1 , F ⟩

● S = {a.b}

● Q = {q1,q2}

● F = {q2}

● :{a ,b}x {q1 , q2}{q1 , q2} descritto dalla tabella:

d a b

q1 q1 q2

q2 q2 q1

Il diagramma a stati sarà:

In questo esempio possiamo notare come ogni parola dell'alfabeto induca uncambiamento di stato. In particolare le parole accettare saranno quelle che portanoda dallo stato iniziale allo stato finale.

q1 q2

a a

bb

Page 14: Linguaggi Formali e Automi

OsservabilitàDato un automa a stati si dice che un suo stato q è osservabile se q=q0 ,w . Ossiase è possibile che l'automa raggiunga lo stato q avendo in ingresso un input w .

Nell'esempio sopra lo stato q3 è inosservabile! Gli stati inosservabili sono tantoirrilevanti da poter essere soppressi rendendo l'automa osservabile. Infatti se tutti glistati dell'automa sono osservabili, allora l'automa è definito anch'esso osservabile.

q1 q2

a a

bb

q3

Page 15: Linguaggi Formali e Automi

IndistinguibilitàDati due stati q1 e q2 , si definiscono indistinguibili – si scrive q1≈q2 - se

q1 ,w=q2 ,w

Ossia se, dato come ingresso una parola w , gli stati q1 e q2 portano entrambi aduno stesso stato q3 , allora non è possibile empiricamente conoscere ilcomportamento dell'automa e quindi gli stati si definiscono indistinguibili.

Al contrario, quando

q1 ,w ≠q2 ,w

sono distinguibili!

L'indistinguibilità gode delle proprietà:

● riflessiva: q1≈q1

● simmetrica: q1≈q1q2≈q1

● transitiva: q1≈q2 e q2≈q1⇒q1≈q3

Dato un automa indistinguibile è possibile costruire un automa distinguibile. Infatti glistati indistinguibili, tra loro, formano classi di equivalenza. Per esempio se q1≈q2esiste una classe di equivalenza [q1]≈. La classe comprende q1 ,q2 e tutti glieventuali stati equivalenti.

In particolare una generica classe di equivalenza [q1]≈ , può essere vista come unsingolo stato. Prendendo quindi ogni classe di equivalenza e usandole come singolistati otterremo un automa i cui stati sono tutti distinguibili tra loro ottenendo diconseguenza un automa distinguibile.

Page 16: Linguaggi Formali e Automi

Sintesi di automaGli automi pienamente indistinguibili sono quelli più vicini al concetto di automagigante GL in cui ogni parola ha il suo stato finale. In un automa gigante diverse parolecorrispondono a diversi stati. In particolare data una parola w il suo stato si indicheràcon [w ] .

Inoltre per quanto riguarda un automa gigante, l'insieme dei suoi stati sarà infinitoperchè le parole w∈ * sono infinite.

Un automa minimo GM è invece l'esatto contrario ed è un automa distinguibile aventeovviamente più stati per singola parola.

● In generale dato un automa A che riconosce un linguaggio L , il relativo automaminimo ha un insieme di stati non più numeroso di quello di A .

Per raggiungere l'automa minimo da un automa gigante è necessario effettuarel'operazione vista nel precedente paragrafo, ossia identificare gli stati indistinguibiliper poi sopprimerli uno ad uno.

Per costruire un GM da un GL si devono eseguire le seguenti operazioni:

● Considerare un GL

● Scorrere il GL dalla radice , visitando l'albero in ampiezza. Quando si arriva ad ungenerico nodo [w] , cui arriva un arco etichettato dal nodo [w ] , se questo èindistinguibile da un nodo [ x ] precedentemente analizzato allora collegare il nodo[w ] ad [ x ] , con un arco e sopprimere il nodo [w] .

● Mantenere il nodo iniziale e i nodi finali [ x ] se x∈L .

Page 17: Linguaggi Formali e Automi

ASF e G3Gli automi a stati finiti sono riconoscitori per grammatiche di tipo 3. Vediamo adessocome da una grammatica 3 sia possibile costruire un automa a stati finiti e ilviceversa.

● Per un linguaggio L riconosciuto da un automa a stati finiti, esiste una grammaticaG di tipo di 3 tale che L=L G .

avendo l'automa:

A=⟨Q , , , q0 , F ⟩

si costruisce la grammatica G :

G=⟨S ,Q , P , q0 ⟩

in modo tale che:

● L'insieme dei metasimboli coincide con gli stati dell'automa

● L'assioma è lo stato iniziale

● qk qj è una regola di produzione se qj=qk ,w

● qk è una regola di produzione se qk∈F

Esempio:

Il linguaggio riconosciuto da questo automa è anche generabile dalla grammatica conassioma q0 e con le seguenti regole di produzione:

● q0aq1

● q1aq2

● q2aq1

● q2

q2aaq0 q1a

Page 18: Linguaggi Formali e Automi

Al contrario possiamo dire che data una grammatica di tipo 3 è possibile costruire unautoma a stati finiti.

Prendiamo una grammatica di tipo 3

G=⟨S ,Q , P , S ⟩

che supponiamo contenga tali regole:

● A B

● A

Possiamo costruire un grafo associato con:

● Metasimboli in Q come vertici del grafo.

● Un arco etichettato tra A e B se esiste una regola A B .

● Assioma S .

● Vertice finale A se esiste una regola A .

Esempio:

Abbiamo questa grammatica:

● q0 aq0→

● q0 aq1→

● q1 bq0→

● q0 e→

Costruiamo il nostro grafo associato:

Interpretando i metasimboli come stati ci accorgiamo che l'automa associato non è unautoma a stati finiti. Infatti ci sono due archi etichettati a e quindi non esiste più ununico stato prossimo.

Un automa di questo tipo esce dal campo deteministico ed entra in quelloprobabilistico prendendo il nome di automa non deterministico.

q1q1q0

a

ba

Page 19: Linguaggi Formali e Automi

Formalmente:

● Un automa a stati finiti non determinitico A è un sistema

A=⟨Q , , R , q0 , F ⟩

dove Q è un insieme finito di stati, è un alfabeto finito, R:Q x xQ0,1 è larelazione di transizione, q0∈Q è lo stato iniziale, F⊆Q è l'insieme di stati finali.

R:Q x xQ0,1 è rappresentata dalla relazione

R '⊆q , , q ' sse R q , , q ' =1

ossia R' è sottoinsieme di Q x xQ con elementi solamente quelli conR q , , q ' =1 ossia quelli aventi arco .

Detto ciò R:Q x xQ0,1 è

R ' ' :QxP Q

con P Q l'insieme delle parti di Q e

R' ' :q ,={q '∣R q , , q ' =1}

ossia, dato un messaggio , la funzione di transizione R ' ' descrive un passaggio aduno stato appartentente al sottoinsieme sopradescritto R' .

In altre parole un grafo non deterministico può essere rappresentato da un automaetichettato i cui vertici sono gli stati q ed esiste un arco tra q e q ' se e solo seR q , , q ' =1 .

Per esempio se R q1 , , q2=1 allora q2=q1 , . In tal caso la relazione R èequivalente alla funzione per l'automa a stati finiti : xQQ .

● Una qualsiasi parola w è riconosciuta da un automa a stati non deterministicosolamente se questa parola induce un qualsiasi cammino dallo stato iniziale ad unostato finale.

Page 20: Linguaggi Formali e Automi

Per ogni linguaggio L riconosciuto da un automa a stati non deterministico esiste unautoma a stati finiti che lo riconosce.

Per ricavare un automa deterministico da un non deterministico prima di tuttoprendiamo in considerazione l'insieme degli stati dell'automa non deterministico.Nell'esempio precedente abbiamo K=q0 ,q1 . L'insieme dell parti rappresenta ilnumero di stati del nuovo automa deterministico in relazione agli stati di quello nondeterministico. In questo caso è P K = , q0 , q1 ,q0q1 .

L'associazione tra stati è dettata dalle regole di produzione della grammatica. Peresempio si ha q0 aq0 e q0 aq1. Queste due regole vengono tradotte nel nuovo→ →automa deterministico con la regola q0 aq0q1 ossia dallo stato q0 di P(K) si passa a→quello q0q1.

In conclusione a questo capitolo:

1. L è generato da una grammatica di tipo 3

2. L è riconosciuto da un automa a stati finiti

sono due affermazioni equivalenti tale che 1 implica 2 e 2 implica 1.

Page 21: Linguaggi Formali e Automi

Espressioni regolariI linguaggi regolari oltre ad essere generati da grammatiche di tipo 3 e riconosciuti daautomi a stati finiti, possono essere denotati da espressioni regolari.

Dato un alfabeto le espressioni regolari sono definite induttivamente:

● ∅ , , con ∈ sono espressioni regolari

● Se p ,q sono espressioni regolari allora pq , p∗q , p * sono espressioniregolari

Ad ogni espressione regolare è associato – e si dice denota - un linguaggio, adesempio:

● ∅ denota il linguaggio vuoto

● denota il linguaggio {}

● denota il linguaggio {}

Con p ,q che denotano L1 , L2 allora:

● pq denota L1∪L2

● p∗q denota L1∗L2

● p * denota L *

Le espressioni regolari denotano linguaggi in modo composizionale ossia avendo comelinguaggi-base ∅ , {} , {} si possono denotare linguaggi complessi sottoponendolialle operazioni di unione, prodotto e chiusura.

In particolare i linguaggi regolari sono tutti e soli i linguaggi riconosciuti da automi astati finiti.

Page 22: Linguaggi Formali e Automi

Teorema di Kleene● L è denotato da una espressione regolare

● L è riconosciuto da un automa a stati finiti

dicono la stessa cosa!

Per dimostrarlo prima di tutto dobbiamo sapere che essendo i linguaggi “denotati”composizionali, le dimostrazioni della generica proprietà P dei linguaggi per mezzodelle espressioni regolari avvengono in modo induttivo, ossia:

1. Essendo ∅ , , espressioni regolari che verificano la proprietà P

2. Se i linguaggi A , B verificano P allora A∪B , A∗B , A * verificano P

Quindi per dimostrare che la frase 1 implica 2 dobbiamo provare che:

1. ∅ , , sono risciuti da automi a stati finiti

2. Se A , B sono riconosciuti da automi a stati finiti, allora A∪B , A∗B , A * sonoriconosciuti da automi a stati finiti

Per il punto 1 basta vedere che gli automi:

riconoscono rispettivamente ∅ , , .

Per il punto 2 supponiamo che A , B siano riconosciuti da automi a stati finiti. Diconseguenza sono rispettivamente generati, come abbiamo visto, da una grammaticadi tipo 3 del tipo

G '=⟨S ,Q ' , P ' , S ' ⟩ e G ' '=⟨S ,Q ' ' , P ' ' , S ' ' ⟩

Supponiamo inoltre che le regole di produzione siano del tipo

● qk qj

● qk

e che Q ' ,Q ' ' siano insiemi disgiunti. Quindi:

● A∪B è verificato perchè generato dalla grammatica G1=⟨S ,Q1 , P1 , S1⟩ in cuiQ1=Q '∪Q ' ' con un nuovo metasimbolo S2 , P1=P '∪P ' ' con S1S ' eS1S ' ' come regole nuove aggiuntive.

● A∗B è verificato perchè generato dalla grammatica G2=⟨S ,Q2 , P2 , S ' ⟩ in cuiQ2=Q '∗Q ' ' con un nuovo metasimbolo S2 , P1=P '∗P ' ' esclusa la regolaq ' con la nuova regola q 'S ' in aggiunta.

● A * è verificato perchè generato dalla grammatica G3=⟨S ,Q ' , P3 , S ' ⟩ in cuiP3=P ' con l'aggiunta della regola q 'S ' .

σ

Page 23: Linguaggi Formali e Automi

Alberi di derivazioneL'albero di derivazione ha le seguenti proprietà:

● Le foglie sono simboli terminali

● I nodi sono metasimboli

● La radice è l'assioma

● Se un nodo è etichettato B e i figli, in ordine, B1 , B2 , B3 ...Bn allora B1 ...Bnè una regola di produzione

● Leggendo le foglie in ordine prefisso, la sequenza di etichette forma una parola w

Esempio:

Data la grammatica: G=⟨{ , , , x , y},{E },{EEE / x / y}, E ⟩

e una parola x y x ha la seguente derivazione:

E⇒ g EE ⇒ g EE E ⇒ g xE E ⇒ g x y E ⇒ g x y x

e il corrispondede albero di derivazione:

Osserviamo che differenti derivazioni possono generare stessi risultati e differentiderivazioni possono generare stessi alberi!

Si dicono quindi equivalenti le derivazioni che producono lo stesso albero diderivazione.

E' interessante per questo motivo ottenere un elemento rappresentativo di classiequivalenti. Una soluzione è la cosidetta derivazione più a sinistra.

● Data una grammatica G=⟨ ,Q , P , S ⟩ di tipo 2 e una parola w∈ *, se laderivazione di w da S è ottenuta applicando una regola di produzione almetasimbolo più di sinsitra, allora viene detta derivazione più a sinistra.

E' interessante osservare come questa particolare derivazione sia semplicemente lavista in profondità dell'albero di derivazione.

Page 24: Linguaggi Formali e Automi

AmbiguitàDal momento che poi ogni albero di derivazione ha associata una derivazione più asinistra e viceversa, ogni derivazione più a sinistra risulta avere una corrispondenzabunivoca con gli alberi di derivazione!

Data una grammatica G=⟨{ , , , x , y},{E },{EEE / x / y}, E ⟩

che genera un linguaggio L G possiamo interpretare una parola w∈LG comeespressione aritmetica.

Per farlo basta assegnare ai simboli terminali un valore oppure un operazione binaria.

Ad esempio data la parola x yx possiamo associare ad x , y i valori 3,5ottenendo 353=11 .

Facendo in questo modo abbiamo associato alla nostra parola un significato!

Per avere un significato valido, dobbiamo avere un unico albero di derivazione persingola parola! Ma come abbiamo visto oltre ad esserci varie possibili derivazioni,potrebbero esserci vari possibili alberi di derivazione!

In questo caso il nostro significato della parola perde senso e diventa quindi ambiguo!

Esempio, data la grammatica:

G=⟨{¿ , , x , y},{E },{EEE /E∗E / x / y}, E ⟩

Sono due alberi di derivazione che generano x∗y∗x in una grammatica appropriata.

Quindi:

● Una grammatica G di tipo 2 è detta ambigua se esiste una parola w∈L G cheammette due alberi di derivazione. Una grammatica G di tipo 2 è detto nonambigua se la parola w∈L G ammette solo un albero di derivazione.

In generale linguaggi generati da grammatiche di tipo 3 ambigue sono semprericonosciuti da grammatiche equivalenti non ambigue. Per ottenere la grammatica nonambigua è necessario ricavare il riconoscitore per il linguaggio. La grammaticaderivata dal riconoscitore sarà non ambigua.

Ci sono casi inoltre di linguaggi che richiedono solo grammatiche di tipo 2 ambigue peressere generati. Questo tipo di linguaggio è chiamato inerentemente ambiguo.

Page 25: Linguaggi Formali e Automi

Forme normaliDue importanti sottoclassi della grammatica di tipo due sono le seguenti:

● Data una grammatica G di tipo 2, è detta forma normale di Chomsky se le regoledi produzione sono del tipo ABC oppure A x , con ABC metasimboli e xsimbolo terminale.

● Data una grammatica G di tipo 2, è detta forma normale di Greibach se le sueregole di produzione sono del tipo A xW con W una parola di metasimboli(eventualmente vuota) e x un simbolo terminale.

Per ogni linguaggio L libero acontestuale privo della parola vuota esiste unagrammatica G ' in forma normale di Chomsky e una G ' ' in forma normale diGreibach generanti il linguaggio L .

Page 26: Linguaggi Formali e Automi

Pumping LemmaDato che una derivazione di una grammatica in forma normale di Chomsky genera unalbero binario, sappiamo a priori che l'albero binario in questione, avendo n foglie,ha anche un'altezza almeno log2n .

Da questa certezza otteniamo una condizione necessaria chiamata pumping lemmaper la quale possiamo definire un linguaggio acontestuale o no.

Per ogni linguaggio acontestuale L esiste una costante H tale che ogni parola z∈Lcon lunghezza ∣z∣H può essere decomposta nella forma z=uvwxy tale che:

1. ∣vx∣1 ossia almeno una parola tra v e x è differente da

2. ∣vwx∣H

3. per ogni k0 vale che u v kw xk y∈L

Supponiamo di avere una grammatica G in forma normale di Chomsky che genera unlinguaggio L .

h è il numero di metasimoli in G . Abbiamo poi una parola z∈L tale che ∣z∣Hcon H=2h1 .

Come abbiamo visto, c'è per z un albero di derivazione con H foglie e altezzalog2H .

Prendiamo adesso in considerazione il cammino C più lungo e discendente dallaradice ad una foglia. C sarà per forza di cose h1=log2H .

Dal momento che G ha h metasimboli, in C sarà per forza presente una ripetizionedi un metasimbolo qualsiasi A !

Chiamiamo w la parola composta dalle foglie del sottoalbero del secondometasimbolo A e vwx la parola composta dalle foglie del primo metasimbolo A .

Abbiamo così ottenuto z=uvwxy con u , y opportune parole.

Risulta inoltre che:

1. ∣vx∣1 altrimenti le radici sei sottoalberi etichettati A coninciderebbero.

2. ∣vwx∣H in quanto il sottoalbero con radice nel primo metasimbolo A ha altezzaal più h1 e di conseguenza possiede al più H=2h1 foglie.

3. per ogni k0 vale che u v kw xk y∈L . Dal momento che:

S⇒ g∗uAy , A⇒ g∗vAx , A⇒ g∗w

allora:

S⇒ g∗uAy⇒ g∗uvAxy⇒ g∗uv2 Ax2 y⇒ g∗u v k A xk y⇒ g∗u v kw xk y

Page 27: Linguaggi Formali e Automi

Automi a pilaI linguaggi acontestuali non possono essere riconosciuti da automi a stati finiti dalmomento che non possiedono una memoria. Un linguaggio acontestuale:

L={anbn∣n≥1}

non può essere riconosciuto da un automa a stati finiti in quanto non gli è possibilecontare il numero di a per confrontarlo al numero di b .

E' necessario quindi una memoria teoricamente infinita... la memoria a pila o stack.

Per mezzo di una memoria a pila è possibile memorizzare una qualsiasi parola su unalfabeto K e implementare le seguenti operazioni:

● Controllare se una parola è vuota: ISEMPY z =0,1 .

● Leggere il primo simbolo: TOP z .

● Cancellare il primo simbolo: POP z .

● Aggiungere un simbolo in testa: PUSH a , z .

Per capire il funzionamento dell'automa a pila prendiamo un linguaggio Lacontestuale generato da una grammatica in forma normale di Greibach e applicandouna derivazione più a sinistra.

Applicando una regola X1aW ad una parola x1x2x3X1X2X3 otteniamox1x2x3aWX2X3 . Notare che per effettuare una simile operazione basta:

1. POP X1

2. PUSH W

Per applicare una regola qualunque AaV serve però prima il riconoscimento delmetasimbolo. Questa operazione è effettuata tramite TOP . InfattiTOP X1X2X3=X1 . Adesso si controlla se X1=A e si applica o meno la regola.

Informalmente un automa a pila funziona nel seguente modo:La parola è contenuta in un nastro. Il nastro è letto simbolo per simbolo da unriconoscitore e la memoria a pila contiene una parola di metasimboli.

Esempio:

pila = X1 X2 X3

riconoscitore = xk

l'automa controlla se esiste una regola del tipo X1 xkW e se la trova cancella conPOP X1 e immette con PUSH W nella memoria a pila.

Un automa a pila è di conseguenza generalmente non deterministico perchè in uninsieme di regole di produzione non è possibile determinare con sicurezza quale vengaadoperata e in che caso.

Page 28: Linguaggi Formali e Automi

Più formalmente: Un automa a pila è un sistema

=⟨ , K , , S ⟩dove:

● è un alfabeto di simboli terminali

● K è un alfabeto disgiunto da

● S è un elemento di posizionato come simbolo iniziale dentro lo stack

● è una funzione da x K ai sottoinsiemi finiti di *

a , A={W1 ,W2 .... ,Wn} funziona in modo che letto un simbolo a e avendo incima alla pila il metasimbolo A , si cancella A e si inserisce un metasimbolo Wkdell'insieme.

Un linguaggio è acontestuale se e solo se è risconosciuto da un automa a pila!

Una parola è riconosciuta da un automa a pila se la sua memoria stack alla fine delriconoscimento risulta essere vuota!