1

PARTE I

RICHIAMI E COMPLEMENTI SULINGUAGGI FORMALI E AUTOMI

Linguaggi regolari

Linguaggi non contestuali

A u t o m i

2

1.1 I LINGUAGGI IN INFORMATICA

@ Presenti a vari livelli di applicazione

linguaggi di programmazionelinguaggi di scriptlinguaggi di marcaturaprotocolli di comunicazionesequenze di operazioniinterazione uomo macchina

3

@ Fondamentali nel software di sistema

compilatoriinterpretitools per la generazione di analizzatori lessicali e sintattici

(Lex, YACC, GNU Bison, Luthorj, Saxj ecc.;più in generale: compiler compiler)

@ Paradigmatici nella teoria

molti importanti problemi teorici sono riconducibili a quellodell'appartenenza di una stringa a un linguaggio

un ruolo importante in informatica teorica hanno i metodi didescrizione di linguaggi

4

Metodi di descrizione di linguaggi

Approccio generativo: i linguaggi possono essere definiti medianteformalismi (metalinguaggi) che specificano la struttura sintattica delleloro stringhe.

Esempi di metalinguaggiGrammatiche di ChomskyForma di Backus Naur (BNF)Linguaggi di marcatura (HTML, XML)

5

Approccio riconoscitivo: un linguaggio può essere definito mediantemacchine astratte (automi) o algoritmi che accettano le stringhe che nefanno parte e rifiutano quelle che non ne fanno parte.

EsempiAutomi a stati finiti – Analizzatori lessicali (scanner)Automi a pila – Analizzatori sintattici (parser)

Approccio algebrico: un linguaggio può essere definito mediante unaespressione algebrica che specifica come esso è costruito a partire dalinguaggi elementari.

EsempioEspressioni regolari (vedi anche Lex o Luthorj)

6

ESPRESSIONI REGOLARI

Def. Dato un alfabeto Σ, chiamiamo espressione regolare una stringa rche utilizza i simboli dell’alfabeto stesso e i simboli Ø, +, ., *, (, ) e cherispetta le seguenti strutture:

1. r = Ø oppure2. r ∈ Σ oppure3. r= (s+t) oppure r= (s.t) oppure r=s*,

con s e t espressioni regolari

7

espressione linguaggioØ Λ a {a} a ∈ Σ(s+t) L(s) ∪ L(t) dove s, t sono e.r.(s.t) L(s) ° L(t)s* L(s)*

Esempio: (a* + ((a.a) . b*))

8

Per semplificare la scrittura delle espressioni regolari possiamosfruttare:• eliminazione del simbolo della concatenazione, cioé (st) anziché (s.t)• precedenze tra operatori: * > . > +

Esempi.

(a+b)* rappresenta il linguaggio L=({a}∪{b})*

cioe’ il linguaggio costituito da stringhe di a e di b di lunghezzaqualunque (inclusa la stringa vuota, cioè la stringa di lunghezza zero).

9

(a+b)*a rappresenta il linguaggioL={x| x ∈ ({a}∪{b})* ∧ "x termina con a"}

cioè stringhe arbitrarie di a e di b che terminano con il carattere a.

(a* + ((a.a) . b*)) = a* + aab*cioè il linguaggio il linguaggio costituito da sequenze di un numeroarbitrario (anche nullo) di a oppure sequenze costituite da due a inizialiseguite da un numero arbitrario (anche nullo) di b.

10

1.2 GRAMMATICHE FORMALI

Metodo di costruzione delle stringhe del linguaggio basato sul concettodi riscrittura (nato nel contesto di studi di algebra e di logica formale).

1914 Axel Thue studia i primi problemi di riscrittura.

1943 Emil Post definisce sistemi di produzione (lavori del 1920).

1947 A.A. Markov definisce algoritmi basati su regole di riscrittura.

1956 N. Chomsky introduce le grammatiche formali nell'ambito degli studi sul linguaggio naturale.

1960 J. W. Backus e P. Naur introducono la BNF per descrivere la sintassi del linguaggio Algol.

11

Le Grammatiche di Chomsky

Def. Una grammatica formale G = <VT,VN,P,S>è caratterizzata da:

• VT (Σ) alfabeto finito di simboli detti terminali,

• VN alfabeto di simboli non terminali(variabili, categorie sintattiche),

• P, detto insieme di produzioni, è una relazione binaria:α e β sono stringhe di terminali o non terminaliα contiene almeno un non terminale<α,β> ∈ P si indica con α → β

• S ∈ VN e' detto assioma.

12

Le grammatiche di Chomsky costituiscono un metalinguaggio poichéogni grammatica descrive un linguaggio (il linguaggio che può esseregenerato in base alle sue regole)

Def. Il linguaggio generato da una grammatica è l'insieme delle stringhedi terminali ottenibili con una sequenza finita di passi di riscritturaconsistenti nell'applicazione delle regole di produzione

13

Più formalmente:

Def. Derivazione diretta: relazione su(V*°VN°V*) × V*

<φ,ψ> appartiene alla relazione se α ∈ V*°VN°V* e β,γ,δ ∈ V*tali cheφ = γαδ ψ = γβδ e α→β ∈ PIn tal caso si scrive φ ⇒ ψ.

Def. Derivazione: chiusura riflessiva e transitiva della derivazionediretta, si rappresenta con ⇒*.

Def. Data una grammaticaG = <{a,b},{S,B,C},P,S>, unaforma di frase è una qualunque stringa x tale che x∈V*e S⇒*x.

14

Il linguaggio generato da G e' l'insieme di particolari forme di frase:

Def. Il linguaggio generato da G èL(G) = {x | x∈VT*∧ S⇒*x}

Def. Due grammatiche G1 e G2 si dicono equivalenti se L(G1) = L(G2).

15

Esempio. La grammatica

G=<{a,b,c},{S,A,B,C},P,S>

con le produzioni:

1 S → aSBC2 S → aBC3 CB → BC4 aB → ab5 bB → bb6 bC → bc7 cC → cc

genera il linguaggio {anbncn | n≥1}

16

Per generare 'aaabbbccc' si effettua la seguente derivazione (la stringa cheviene riscritta è sottolineata, il numero rappresenta la produzione applicata):

S (1) ⇒ aSBC(1) ⇒ aaSBCBC(2) ⇒ aaaBCBCBC(3) ⇒ aaaBCBBCC(3) ⇒ aaaBBCBCC(3) ⇒ aaaBBBCCC(4) ⇒ aaabBBCCC(5) ⇒ aaabbBCCC(5) ⇒ aaabbbCCC(6) ⇒ aaabbbcCC(7) ⇒ aaabbbccC(7) ⇒ aaabbbccc

17

1.3 CLASSI DI GRAMMATICHE DI CHOMSKY E CLASSI DILINGUAGGI

• di tipo 0, non limitate

• di tipo 1, contestuali (context sensitive: CS)

• di tipo 2, non contestuali (context free: CF),

• di tipo 3, regolari

18

Def. Le grammatiche di Chomsky di tipo 0, sono basate sulle produzioni piu'generali, del tipo:

α→β , α∈V*°VN°V*, β∈V*

NOTA BENE. Le grammatiche di tipo 0 ammettono anche derivazioni cheaccorciano stringhe.

Def. I linguaggi di tipo 0 sono i linguaggi generati da grammatiche di tipo 0.

Def. Le grammatiche di Chomsky di tipo 1, (dette context sensitive ocontestuali) sono basate su produzioni del tipo:

α→β , α∈V*°VN°V*, β∈V+

con |α|≤|β|

19

Def. I linguaggi di tipo 1 (context sensitive o contestuali) sono i linguaggigenerati da grammatiche di tipo 1.

Def. Le grammatiche di Chomsky di tipo 2, (dette context free o noncontestuali) sono basate su produzioni del tipo:

A→β , A∈VN, β∈V+

Def. I linguaggi di tipo 2 (context free o non contestuali) sono i linguaggigenerati da grammatiche di tipo 2.

20

Esempio. Generazione di espressioni aritmetiche con la variabile i, assioma E

E → E+T | TT → T*F | FF → i | (E)

Esempio. Grammatica delle parentesi ben bilanciate:

S → ()S → SSS → (S)

21

Perche' le grammatiche di tipo 1 sono chiamate contestuali e quelle di tipo 2non contestuali?

Nell'originaria formulazione data da Chomsky le grammatiche di tipo 1 sonodefinite come quelle grammatiche le cui produzioni hanno la forma:

α → γ con α=φ1Αφ2 e γ=φ1βφ2, e con Α∈VN , φ1,φ2∈V*, β∈V+

Quindi, se |φ1| ≥ 1 o |φ2| ≥ 1, la produzione esprime il fatto che il non terminaleA viene rimpiazzato dalla stringa β solo se appare nel contesto delle stringheφ1 e φ2. Per tale motivo quelle produzioni (e le relative grammatiche) sonochiamate "contestuali".

22

Esempio. Le produzioni

aB→ab, bB→bb, bC→bc, cC→cc

della grammatica per il linguaggio {anbncn | n≥1} sono contestuali secondoChomsky.

23

Teorema. Le grammatiche di tipo 1 e le grammatiche contestuali secondoChomsky consentono di generare la stessa classe di linguaggi.

Dim. i) Le produzioni contestuali di Chomsky sono di tipo 1.ii) Le produzioni di tipo 1 possono essere facilmente trasformate in produzionicontestuali di Chomsky. (Esercizio)

Ad esempio la produzione CB →BC puo' essere trasformata nella sequenza diproduzioni (contestuali secondo Chomsky):

CB → CXCX → BXBX → BC

24

NOTA BENE. Le produzioni di tipo 2 corrispondono al caso particolare in cuisia φ1 che φ2 sono stringhe vuote. Tali produzioni consentono dunque dirimpiazzare un nonterminale con una stringa di caratteri, indipendentementedal contesto in cui esso si trova. Per tale motivo esse (e le relativegrammatiche) si chiamano "non contestuali".

25

Def. Le grammatiche di Chomsky di tipo 3, (dette regolari) sono basate suproduzioni del tipo:

A→aB oppure A→a,

con A, B∈VN, a∈VT

Def. I linguaggi di tipo 3 (regolari) sono i linguaggi generati da grammatiche ditipo 3.

Esempio. Il linguaggio {anb | n≥0} e' di tipo 3 in quanto e' generato dallagrammatica con le produzioni:

S → aSS → b

26

Le grammatiche di tipo 3 sono chiamate anche lineari destre (LD).

Le grammatiche di tipo 3 vengono chiamate lineari perche' nel lato destro diogni produzione compare al piu' un solo non terminale (variabile); inoltrevengono chiamate lineari destre perché il non terminale compare a destra delterminale.

Si possono anche definire grammatiche lineari sinistre (LS) con produzioni deltipo:

A→Ba oppure A→a,

con A, B∈VN, a∈VT

27

Esempio. Il linguaggio {anb | n≥0}puo' essere anche generato da una grammatica lineare sinistra con le seguentiproduzioni:

S → Tb | bT → Ta | a

Teorema. Le classi di linguaggi generabili con grammatiche LD e LScoincidono.

28

Def. Un linguaggio e' strettamente di Tipo n se esiste una grammatica di tipo nche lo genera e non esiste nessuna grammatica di tipo m>n che lo genera.

Esempi. Il linguaggio {anbn | n≥1} e' generato da una grammatica di tipo 2 enon e' generabile con nessuna grammatica di tipo 3.Il linguaggio {anbncn | n≥1} e' generato da una grammatica di tipo 1 e non e'generabile con nessuna grammatica di tipo 2 o di tipo 3.

NOTA BENE. La dimostrazione dei suddetti risultati e’ basata sui noti“pumping lemma” basati sulle proprietà strutturali dei linguaggi di vario tipo.Per mostrare linguaggi strettamente di tipo 0 è necessario introdurre ulterioriconcetti.

29

1.4 LINGUAGGI LINEARI

I linguaggi lineari sono quei linguaggi CF generati da grammatiche lineari, incui, cioe', la parte destra di ogni produzione contiene al piu' un non terminaleLe grammatiche di tipo 3 sono lineari; come si e' detto, in particolare, linearidestre (LD).

Esempio. La grammatica seguente, che genera {ancbn | n≥0} e' lineare:

S → aSb | c

Si noti che tale linguaggio e' strettamente CF. I linguaggi lineari sono unsottoinsieme dei linguaggi CF (ad esempio il linguaggio delle parentesi benbilanciate non è un linguaggio lineare) e un soprainsieme di quelli regolari.NOTA BENE: Fondendo produzioni lineari destre e lineari sinistre si possonogenerare linguaggi non regolari.

30

1.5 RICONOSCIMENTO DI LINGUAGGI

Dato un linguaggio L, il problema del riconoscimento di L e' il problemadecisionale seguente: data una stringa x, stabilire se essa appartiene ad L. Taleproblema e' noto anche come problema dell'appartenenza (membership).

• I linguaggi di tipo 3 sono riconosciuti in tempo lineare da dispositivi conmemoria costante (automi a stati finiti).

• I linguaggi di tipo 2 sono riconosciuti in tempo lineare da dispositivinondeterministici dotati di una memoria gestita come una pila (automi a pilanon deterministici).

31

• I linguaggi di tipo 1 sono riconosciuti da dispositivi nondeterministici conmemoria che cresce linearmente con la lunghezza della stringa da esaminare:automi non deterministici lineari (linear bounded automata).

• Per alcuni linguaggi strettamente di tipo 0 e' possibile che non esista unalgoritmo di decisione ma esiste comunque un processo semidecisionale, incui, se la stringa fa parte del linguaggio essa viene riconosciuta ma se non faparte del linguaggio non e' detto che la computazione termini. I dispositivi checonsentono di riconoscere o di attuare un procedimento di semidecisione per ilinguaggi di tipo 0 sono le macchine di Turing. In generale non e' possibilestabilire un limite alle quantita' di risorsa tempo o memoria che si rendenecessario per riconoscere un linguaggio di tipo 0.

32

1. 6 LINGUAGGI REGOLARI E AUTOMI A STATI FINITI

I linguaggi regolari:

• sono generabili con grammatiche di tipo 3

• coincidono con i linguaggi definibili con espressioni regolari

• coincidono con i linguaggi riconoscibili con automi a stati finitideterministici o non deterministici

33

AUTOMI A STATI FINITI (ASF)

a1 a2 a n

meccanismo di controllo

testina di lettura

nastro di input unidirezionale

schema di automa a stati finiti

34

Def. Automa a stati finiti (ASF):

A=<Σ,K,δ,q0,F>

Σ = {σ1,...,σn} alfabeto di input

K = {q0,...,qn} insieme finito non vuoto di stati

K ⊇ F insieme di stati finali

q0∈K stato iniziale

δ : K × Σ → K funzione di transizione, funzione totale che determina lostato successivo

35

Def. Funzione di transizione estesa alle stringhe:

δ : K × Σ* → K

δ(q,ε) = qδ(q,ax) = δ(δ(q,a),x), con x∈Σ* e a∈Σ

Def. Linguaggio riconosciuto da un automa A:

L(A) = { x ∈ Σ* | δ(q0,x) ∈ F}

36

Esempio. Dato il linguaggio {anb | n≥0} generato da S → aS | b,l'automa che lo riconosce e' l'automa<{a,b}, {q0,q1,q2}, δ, q0, {q1}>

δ a bq0 q0 q1q1 q2 q2q2 q2 q2

37

38

Nei ‘compiler compiler’ e nei generatori di analizzatori lessicali (Lex,Luthorj) si utilizzano tutti i diversi formalismi di definizione deilinguaggi regolari.

Definiamo il linguaggio per cui vogliamo costruire l’analizzatorelessicale mediante una espressione regolare.

Il generatore prende in input l’espressione regolare e:

- costruisce l’automa a stati finiti non deterministico corrispondente- lo trasforma in automa a stati finiti deterministico- fornisce come output il programma di analisi lessicale (scanner) per

il linguaggio dato.

39

1.7 LINGUAGGI NON CONTESTUALI ED AUTOMI A PILA

I linguaggi non contestuali (context free):

• sono generabili con grammatiche di tipo 2

• coincidono con i linguaggi riconoscibili con automi a pilanon deterministici

• alcune loro sottoclassi sono sufficientemente ampie da consentire didescrivere linguaggi di programmazione e al tempo stessosufficientemente ristrette da consentire la costruzione di analizzatorisintattici (parser) che operano in tempo lineare

40

Forme normali per i linguaggi non contestuali

Forma ridotta: grammatiche- prive di ε-produzioni,- prive di produzioni unitarie,- prive di produzioni che contengono simboli inutili (cioè simboli non

generabili partendo dall’assioma o simboli non fecondi, dai quali nonsi generano stringhe di soli terminali).

41

Forma normale di Chomsky: grammatichedi tipo 2 le cui produzioni sono del tipo

Α→ΒC con Α, Β, C ∈ VN

o del tipo Α → a con a ∈ Σ

Forma normale di Greibach: grammatichedi tipo 2 le cui produzioni sono del tipo

Α → a β con a ∈ Σ, β∈ V*

42

I linguaggi non contestuali sono tutti e soli i linguaggi che vengonoriconosciuti da un automa a pila non deterministico (o automa "push-down", PDA)

Def. Automa a pila non deterministico (PDA)

M=<Σ,Γ,Z0,Q,q0,F,δ>

Σ alfabeto di inputΓ alfabeto dei simboli della pilaZ0 ∈ Γ simbolo di pila inizialeQ insieme finito di statiq0 ∈ Q stato inizialeQ ⊇ F insieme di stati finaliδ : Q × (Σ∪{ε}) × Γ → P(Q × Γ*)

funzione di transizione

43

Se abbiamo una regola di transizione δ(qi,a,A)={(qj,BA),(qh,ε)}essa significa che se nello stato interno qi, leggiamo a sul nastro ed A e' ilsimbolo affiorante sulla pila, si realizzano, non deterministicamente, duetransizioni; la prima sostituisce il simbolo affiorante sulla pila con lastringa di caratteri BA e si porta nel nuovo stato interno qj, la secondasostituisce il simbolo affiorante sulla pila con la stringa vuota ε, in altreparole cancella A dalla pila, e si porta nel nuovo stato interno qh.

NOTA BENE. La testina sul nastro di ingresso può anche non spostarsi.Questa situazione è espressa dicendo che la testina legge ε sul nastro diingresso.

Convenzione: se metto BA in pila, B è il nuovo simbolo affiorante.

44

Esempio. Automa a pila M che riconosce anbn

M = <{a,b},{Z0,A0,A},Z0,{q0,q1,q2},q0,{q2},δ>

- il simbolo A serve a ricordare la presenza delle a

- nello stato q0 si memorizzano le a, nello stato q1 si confrontano le b concio' che si e' memorizzato, lo stato q2 e' lo stato finale.

NOTA BENE. In questo caso l'automa ha un comportamentodeterministico

45

Z0 A0 Aa b a b a b

q0 A0q0

AA0q0

A0q2

AAq0

εq1

q1 A0q2

εq1

q2

46

Def. Configurazione di automa a pila: tripla <q,x,γ>con q∈Q stato interno, x∈Σ* stringa da leggere in input e γ∈Γ* stringaattualmente in pila

relazione di transizione per automa a pila: relazione binaria sulleconfigurazioni |

<q,x,γ> | <q',x',γ'> significa che:

((x=ax' ∧ γ=Zη ∧ γ'=ζη ∧ <q',ζ>∈δ(q,a,Z)) ∨(x=x' ∧ γ=Zη ∧ γ'=ζη ∧ <q',ζ>∈δ(q,ε,Z)))

computazione: chiusura transitiva e riflessiva di |, indicata con |*

47

Def. Linguaggio accettato dall'automa a pila:

due definizioni alternative

• accettazione per pila vuota: una stringa è accettata da un automa a pilaM se e solo se al termine della scansione della stringa la pila è vuota

N(M) = {x|<q0,x,Z0>|*<q,ε,ε>}

• accettazione per stato finale: una stringa è accettata da un automa a pilaM se e solo se al termine della scansione della stringa M si trova in unostato finale

L(M) = {x|<q0,x,Z0>|*<q,ε,γ>,q∈F,γ∈Γ*}

48

NOTA BENE. Si può dimostrare che le due definizioni sono equivalenti.

Teorema. Se L(G) è non contestuale esiste un automa a pila M tale cheL(G)=N(M)

Dim. Sia G=<Σ,VN,P,S> tale che ε∉L(G) e supponiamo G in GNF. Inquesto caso il PDA ha un solo stato e i non terminali della grammaticapossono essere usati come simboli di pila.

Costruiamo M=<Σ,Γ,Z0,Q,q0,F,δ>

Γ=VN, Z0=S, Q={q}, q0=q, F=∅

Per ogni A→aγ con γ∈VN* abbiamo che <q,γ>∈δ(q,a,A)

49

Esempio: il linguaggio { wwR | w ∈ (a+b)+} è generabile con la seguentegrammatica in forma di Greibach:

S → aSA | bSB | aA | bBA → aB → b

Ed è riconoscibile (per pila vuota) con il seguente automa a pila:

S A Ba b a b a b

q SA, q-----A, q

SB, q-----B, q

ε, q ε, q

50

Per consentire un’efficiente e corretta analisi sintattica i linguaggi diprogrammazione devono essere linguaggi CF

- non ambigui (ogni stringa deve essere generabile con un solo albero diderivazione)- analizzabili in modo deterministico in tempo lineare (linguaggi LL(k),

LR(K), LALR(k) ecc.)

51

Proprietà decidibili per i linguaggi regolari e CF:

- L è vuoto, L è finito, L è infinito- due automi a stati finiti dati sono equivalenti- due grammatiche CF deterministiche date sono equivalenti

Proprietà non decidibili:

- una grammatica CF è ambigua- un linguaggio CF è ambiguo (tutte le sue grammatiche lo sono)- due grammatiche CF (non deterministiche) date sono equivalenti- l’intersezione di due linguaggi CF è vuota, ecc.