11. LINGUAGGI CONTEXT FREE

Linguaggi di tipo 2, non contestuali, context free (CF)

I linguaggi non contestuali o context free: - sono generati da grammatiche di tipo 2 - sono riconosciuti da automi a stati finiti

non deterministici con l’ausilio di una pila (automi a pila) - contengono i linguaggi di programmazione

(anzi i linguaggi di programmazione appartengono a classi di linguaggi context free deterministici molto particolari).

Molte frasi in linguaggio naturale hanno una struttura sintattica non contestuale; Ad esempio abbiamo che una frase è costituita da un soggetto seguito da un complemento; un soggetto è un articolo seguito da un sostantivo; il complemento è un verbo o un verbo seguito da un complemento oggetto. FRASE →SOGGETTO COMPLEMENTO. SOGGETTO → ART SOST COMPLEMENTO → VERBO | VERBO COMP-OGGETTO COMP-OGGETTO → ART SOST ART → il SOST → gatto | topo VERBO → mangia il gatto mangia. il gatto mangia il topo.

La BNF (Forma di Backus-Naur), utilizzata per definire la struttura sintattica dei linguaggi di programmazione non è altro che una grammatica di tipo 2, scritta in modo più suggestivo: <frase-if> ::= if <predicato>

then <istruzione>

Anche la descrizione della struttura di un documento espressa in XML è sostanzialmente una grammatica di tipo 2: <!DOCTYPE nota [ <!ELEMENT nota ( messaggio+ )> <!ELEMENT messaggio (#PCDATA)> <!ATTLIST messaggio numero CDATA da CDATA> ]> <nota> <messaggio numero="a1" da=“Pippo"> Ricordati di comprare il latte tornando a casa</messaggio> <messaggio numero="a2" da=“Pluto">Ho bisogno di aiuto per i compiti a casa </messaggio> </nota>

Per i linguaggi di Tipo 2 abbiamo una immediata corrispondenza tra derivazioni e alberi (alberi sintattici). Esempio. Data la grammatica A → BC | Def C → c | cC B → b | BC D → d la derivazione della stringa può essere rappresentata con un albero B

A

B C

B C c C

c b c

Analisi sintattica ("parsing"): dato un programma ricostruirne l'albero sintattico per poter effettuare la traduzione (o, nel caso di un interprete, eseguire direttamente le istruzioni) Problemi: • non ambiguità del "parsing", cioè possibilità di ricostruire in modo univoco il "significato" di una stringa • efficienza del "parsing", cioè possibilità di ricostruire il

"significato" di una stringa con una sola scansione del testo

11.1 PROPRIETA’ DI CHIUSURA E PUMPING LEMMA Lemma. Data una grammatica non contestuale possiamo decidere se essa genera il linguaggio vuoto Dim. Supponiamo |VN|=k Per verificare la producibilità di una stringa di soli terminali è sufficiente considerare l'insieme di tutti gli alberi di derivazione con tutti i terminali a profondità ≤k (NB: la radice di un albero ha profondità 0 e se un nodo ha profondità p i suoi figli hanno profondità p+1) Infatti, se una stringa di soli terminali è generata con almeno un terminale y a profondità >k, allora sul cammino da y alla radice c'è un nonterminale ripetuto 2 volte L'albero può quindi essere "potato"

Dopo la potatura produce ancora una stringa di soli terminali.

Sia la stringa uvwxy, sia la stringa uwy appartengono al linguaggio (NB Anche tutte le stringhe uviwxiy)

Teorema. Data una grammatica non contestuale G, è decidibile stabilire se L(G) è infinito Dim. Supponiamo |VN| = k Basta considerare l'insieme di tutte le derivazioni che generano stringhe terminali in cui il ramo più lungo ha lunghezza tra k e 2k • se tale insieme è vuoto, allora il linguaggio è finito • se no, tali derivazioni hanno almeno un non terminale ripetuto 2 volte Allora l'albero di derivazione può essere ampliato indefinitamente continuando a produrre stringhe terminali e quindi il linguaggio è infinito

"Pumping lemma" per i linguaggi non contestuali Usando lo stesso ragionamento che abbiamo usato per decidere se un linguaggio CF è vuoto, finito o infinito, possiamo dimostrare il seguente risultato. Teorema. Se L è un linguaggio non contestuale allora esiste una costante n tale che se z∈L e |z|≥n allora esistono u,v,w,x,y tali che 1. uvwxy=z 2. |vx|≥1 3. |vwx|≤n 4. ∀ i≥0 uviwxiy∈L

Corollario 1. {anbncn|n≥1} non è di tipo 2. Dim. Sia anbncn = uvwxy = z se v (oppure x) contiene almeno due simboli diversi (es. v=ab)

allora la stringa uv2wx2y contiene un'alternanza di simboli incompatibile con anbncn (es. uababwx2y)

se v è composta da simboli tutti uguali fra loro (es. v=aa) e x è composta da simboli tutti uguali fra loro (es. x=cc)

allora uv2wx2y contiene un numero diverso di a, b e c

Corollario 2. I linguaggi non contestuali non sono chiusi rispetto all'intersezione (e quindi neanche rispetto alla complementazione). Dim. il linguaggio L1={anbncm|m,n≥1} è di tipo 2 il linguaggio L2={ambncn|m,n≥1} è di tipo 2 il linguaggio intersezione di L1 ed L2 è {anbncn|n≥1} che invece non è di tipo 2

NOTA BENE. Avevamo dimostrato la decidibilità dell'equivalenza tra linguaggi regolari usando la chiusura rispetto all'intersezione; la tecnica non è estendibile ai linguaggi non contestuali. In realtà il problema della equivalenza di grammatiche non contestuali è indecidibile.

Proprietà di chiusura Teorema. I linguaggi non contestuali sono chiusi rispetto all'unione, alla concatenazione ed alla iterazione. Dim. Siano <Σ,VN1,P1,S1> e <Σ,VN2,P2,S2> due linguaggi non contestuali unione

aggiungiamo S'→S1|S2 e usiamo S' come nuovo assioma, otteniamo un linguaggio non contestuale che genera l'unione dei due linguaggi

concatenazione

aggiungiamo S'→S1S2 e usiamo S' come nuovo assioma

iterazione

aggiungiamo S'→S1S'|ε e usiamo S' come nuovo assioma

11.2 FORME NORMALI PER I LINGUAGGI CONTEXT FREE Grammatica in forma ridotta.

1. non contiene ε-produzioni, oppure l’assioma può dar luogo ad una ε-produzione ma in tal caso l’assioma non compare mai a destra in una produzione 2. non contiene produzioni unitarie (es. A →B) 3. non contiene simboli inutili, cioè inutilizzabili per produrre terminali o perchè non sono raggiungibili dall’assioma o perchè non sono fertili, non generano stringhe di soli terminali

Teorema. Data una grammatica non contestuale esiste una grammatica equivalente in forma ridotta Dim. 1. Rimozione delle ε-produzioni che non sono sull'assioma.

Se ad esempio abbiamo A → BC | baB | B B → ε | aD possiamo trasformare le due produzioni così: A → BC | B | baB | C | ba | ε B → aD Tale procedimento può essere iterato finchè le ε-produzioni vengono portate sull’assioma.

2. Eliminazione delle produzioni unitarie: Se esiste G con una produzione U →V

allora possiamo costruire G' in cui per ogni produzione del tipo V→α aggiungiamo la produzione U→α e quindi

eliminiamo la produzione U →V. Si può dimostrare per induzione sulla lunghezza di una derivazione che la grammatica G genera x se e solo se anche G' genera x.

3. Eliminazione dei simboli inutili:

Perchè un simbolo A sia utile è necessario che (a) sia fecondo, cioè da A siano generabili stringhe di terminali (b) che A sia raggiungibile da S

La condizione (a) è verificabile controllando che non sia vuoto il linguaggio generato dalla grammatica in cui A si assume come assioma.

In alternativa si può procedere creando una lista dei non terminali fecondi secondo la seguente regola ricorsiva:

- A è fecondo se esiste una produzione A→α in cui α contiene solo terminali

- A è fecondo se esiste una produzione A→α in cui α contiene solo terminali o simboli fecondi

La condizione (b) (raggiungibilità dall’assioma) è verificabile ricorsivamente a partire dall'assioma S; si può procedere creando una lista dei non terminali che soddisfano la condizione (b) secondo la seguente regola:

- S soddisfa la condizione (b) - A soddisfa la condizione (b) se B soddisfa la condizione (b) ed esiste una produzione del tipo B→αAα'.

NOTA BENE. Consideriamo la seguente grammatica: S → AB | a A → a Dopo il primo passo abbiamo S → a A → a Dopo il secondo passo abbiamo S → a

Se avessimo applicato i due passi in ordine inverso avremmo avuto: S → AB | a e poi S → a A → a A → a che contiene ancora un simbolo non raggiungibile. Quindi dobbiamo prima eliminare i simboli non fecondi e poi quelli non raggiungibili.

Esempio. Riduciamo la grammatica 1 S → aUVb|TZ 5 V → aY 2 Z → aZ 6 Y → bY|b 3 U → bU|b 7 W → cWd|cd 4 V → W 8 T → tT|tz • Eliminazione delle produzioni unitarie: via la 4 ed aggiungiamo le produzioni V → cWd|cd • Eliminazione dei simboli non fecondi: via la 2 e la 1bis • Eliminazione dei simboli non raggiungibili: via la 8 1 S → aUVb 2 U → bU|b 3 V → cWd|cd|aY 4 Y → bY|b 5 W → cWd|cd

Forma Normale di Chomsky Def. Una grammatica di tipo 2 è in forma normale di Chomsky (CNF) se tutte le produzioni sono del tipo

A→BC oppure A→a Teorema. Data una grammatica G di tipo 2 tale che ε∉L(G) esiste una grammatica G' equivalente in CNF. Dim. Supponiamo che G sia in forma ridotta. Per ogni produzione p: A→β1β2....βn ( βi∈VN), se p non è in CNF sono possibili due casi: (caso 1) per ogni i∈{1,....,n} (n≥3), βi∈VN (caso 2) per qualche i∈{1,....,n} (n≥2) βi∈VT.

(caso 1) per ogni i ∈ {1,....,n} (n≥3) βi∈VN Aggiungiamo n-2 nuovi non terminali Z1..Zn-2 e sostituiamo p con una catena di produzioni A→β1Z1 Z1→β2Z2 Z2→β3Z3 ........ Zn-2→βn-1βn (caso 2) per qualche i∈{1,....,n} (n≥2) βi∈VT Per ogni βi∈VT aggiungiamo un non terminale Zi, sostituiamo Zi a βi in p ed aggiungiamo la produzione Zi→βi Se n=2, allora non è necessario lavorare ulteriormente sulla produzione, altrimenti ci riconduciamo al (caso 1)

Esempio. Trasformazione in CNF della grammatica S→aSb S→ab sostituiamo S→ab con S→AB, A→a e B→b sostituiamo S→aSb con S→ASB sostituiamo S→ASB con S→AZ e Z→SB

Forma Normale di Greibach

Def. Una grammatica di tipo 2 è in forma normale di Greibach (GNF) se tutte le produzioni sono del tipo A→aβ con β∈VN* NOTA BENE. La forma normale di Greibach ha varie applicazioni: • ci permette di costruire l'automa che riconosce il linguaggio, • ci permette di caratterizzare le classi di Grammatiche di Tipo 2 per le quali l'analisi sintattica è più efficiente.

Def. Chiamiamo A-produzioni tutte le produzioni del tipo: A → β1|β2|....|βn Lemma (Sostituzione). Data una grammatica G le cui produzioni includono A→α1Bα2 (α1, α2∈V*) B→β1|β2|....|βn e non esistono altre B-produzioni, essa è equivalente alla grammatica G' in cui la produzione A→α1Bα2 è sostituita con A→α1β1α2|α1β2α2|....|α1βnα2

Dim. Banale; ogni stringa generata usando la derivazione A ⇒ α1Bα2 ⇒ α1βiα2 può essere generata con la derivazione A ⇒ α1βiα2 Esempio. Data la grammatica A → abBc | ceB B → aD | bb D → dD | d essa è equivalente alla grammatica A → abaDc | ceaD | abbbc | cebb D → dD | d

Lemma (eliminazione della ricursione sinistra). Data una grammatica G le cui A-produzioni sono: A→Aα1|....|Aαm|β1|....|βn ed in cui nessuna delle βi inizia con A ad essa è equivalente la grammatica G' in cui la produzione A→Aα1|....|Aαm|β1|....|βn è sostituita con A→β1B|....|βnB|β1|....|βn e B→α1B|....|αmB|α1|....|αm

Dim. Ogni derivazione della G del tipo A ⇒ Aα1 ⇒ Aα2α1 ⇒ .... ⇒ Aαm....α2α1 ⇒ βjαm....α2α1 è rimpiazzata da una derivazione della G' A ⇒ βjB ⇒ βjαmB ⇒ βjαmαm-1B ⇒ .... ⇒ βjαm....α2B ⇒ βjαm....α2α1 e, viceversa, ogni derivazione della G' può essere rimpiazzata da una derivazione della G.

Teorema. Data una grammatica G di tipo 2 tale che ε∉L(G) esiste una grammatica G' in GNF con L(G)=L(G') Dim. Supponiamo che G sia in CNF. Procediamo nel seguente modo: • stabiliamo arbitrariamente un ordinamento A1,....,Am sui non terminali di G, • eseguiamo, varie volte, le operazioni di sostituzione e di eliminazione della ricursione sinistra.

Algoritmo 0. Mettere la grammatica in CNF 1. Numerare i nonterminali A1, ..., Am 2. begin for k:=1 to m do begin for j:=1 to k-1 do per ogni produzione del tipo Ak→Ajα applica il Lemma di sostituzione end end date le Ak-produzioni del tipo Ak→Akα1 | ... | Akαr | β1 | ... | βs applica il Lemma di eliminazione della ricursione introducendo la corrispondente Bk end

3. for k:=m-1 downto 1 do for j:=m downto k do per ogni produzione del tipo Ak→Ajα applica il Lemma di sostituzione end end 4. for k:=1 to m for j:=1 to m do per ogni produzione del tipo Bk→Ajα applica il Lemma di sostituzione end end

NOTA BENE. Al termine del Passo 2 avremo tutte produzioni dei seguenti tipi: a) Ak→Ajγ con j>k b) Ak→aγ c) Bk→γ in cui a∈Σ, γ∈(VN ∪ {B1, ... ,Bk})* e γ non può iniziare per B. Inoltre, - se k = m le Ak-produzioni sono tutte del tipo b, - se k = m-1 le Ak-produzioni sono tutte del tipo b oppure del tipo Am-1→Amγ - se k = m-2 le Ak-produzioni sono del tipo b oppure del tipo Am-2→Amγ o Am-2→Am-1γ e così via.

A questo punto interviene il passo 3 nel quale sostituiamo Am nelle Am-1-produzioni, Am ed Am-1 nelle Am-2-produzioni e così via, ripetendo a ritroso le sostituzioni fino al nonterminale A1.

Infine, per quanto riguarda il passo 4, esaminiamo le produzioni dei nuovi non terminali Bi. Il fatto che G sia in CNF ci garantisce che ogni produzione abbia a destra o un terminale o due non terminali. Quindi, quando effettuiamo il passo di eliminazione della ricursione, in cui per ogni produzione del tipo Ak→Akα aggiungiamo Bk→α e Bk→αBk α non è mai vuoto e non può iniziare con un nonterminale di tipo B. Infine, nel passo 4, per far comparire un terminale all'inizio della parte destra, possiamo riapplicare il passo di sostituzione alle Bi-produzioni per ogni i.

Esempio. Data una grammatica in CNF determinare la grammatica equivalente in GNF S→AB | b A→BS | b B→BA | AS | a Ordinamento: S,A,B Sostituiamo B→AS con B→bS e B→BSS e l'insieme delle produzioni e' il seguente: S→AB | b A→BS | b B→a|bS|BA|BSS

A questo punto le sostituzioni previste dal passo 2 non sono più applicabili. Ci troviamo però dinanzi alla necessità di eliminare la ricursione a sinistra nelle B-produzioni. Introduciamo il nuovo nonterminale B'. L'insieme delle produzioni diventa: S→AB | b A→BS | b B→a|bS|aB'|bSB' B'→A|SS|AB'|SSB' in cui le produzioni sono del tipo a) Ak→Ajγ con j>k S→AB A→BS b) Ak→aγ S→ b A→ b B→a|bS|aB'|bSB' c) Bk→γ B'→A|SS|AB'|SSB'

Ora applichiamo il passo 3 e sostituiamo B nella produzione A→BS ottenendo A→aS|bSS|aB'S|bSB'S e quindi sostituiamo A nella produzione S→AB ottenendo S→aSB|bSSB|aB'SB|bSB'SB|bB

infine (passo 4) possiamo sostituire A ed S nella produzione B'→A|SS|AB'|SSB' ottenendo B'→aS|bSS|aB'S|bSB'S|b| aSBS|bSSBS|aB'SBS|bSB'SBS|bBS|bS| aSB'|bSSB'|aB'SB'|bSB'SB'|bB'| aSBSB'|bSSBSB'|aB'SBSB'|bSB'SBSB'| bBSB'|bSB' La grammatica in GNF sara' dunque: S→aSB|bSSB|aB'SB|bSB'SB|bB A→aS|bSS|aB'S|bSB'S B→a|bS|aB'|bSB' B'→aS|bSS|aB'S|bSB'S|b| aSBS|bSSBS|aB'SBS|bSB'SBS|bBS|bS| aSB'|bSSB'|aB'SB'|bSB'SB'|bB'| aSBSB'|bSSBSB'|aB'SBSB'|bSB'SBSB'| bBSB'|bSB'

11.3 Automi a pila Che dispositivo occorre per riconoscere un linguaggio non contestuale? Introduciamo a tal fine un nuovo modello di calcolo non deterministico: l'automa a pila (o automa "push-down", PDA) Def. Automa a pila non deterministico (PDA)

M=<Σ,Γ,Z0,Q,q0,F,δ> Σ alfabeto di input Γ alfabeto dei simboli della pila Z0∈Γ simbolo di pila iniziale Q insieme finito di stati q0∈Q stato iniziale Q⊇F insieme di stati finali δ : Q × (Σ∪{ε}) × Γ → P(Q × Γ*) funzione di transizione.

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 è il simbolo affiorante sulla pila, si realizzano, non deterministicamente, due transizioni; la prima sostituisce il simbolo affiorante sulla pila con la stringa di caratteri BA e si porta nel nuovo stato interno qj, la seconda sostituisce il simbolo affiorante sulla pila con la stringa vuota ε, in altre parole 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 di ingresso. Convenzione: se metto BA in pila, B è il nuovo simbolo affiorante.

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 con ciò che si è memorizzato, lo stato q2 è lo stato finale. NOTA BENE. In questo caso l'automa ha un comportamento sostanzialmente deterministico

Z0 A0 A a b a b a b

q0 A0 q0

AA0 q0

A0 q2

AA q0

ε q1

q1 A0 q2

ε q1

q2

Def. Configurazione di automa a pila: tripla

<q,x,γ> con q∈Q stato interno, x∈Σ* stringa da leggere in input e γ∈Γ* stringa attualmente in pila relazione di transizione per automa a pila: relazione binaria sulle configurazioni |

<q,x,γ> | <q',x',γ'>

se vale:

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

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

Def. Linguaggio accettato dall'automa a pila: due definizioni alternative • accettazione per pila vuota: una stringa è accettata da un automa a pila M 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 pila M se e solo se al termine della scansione della stringa M si trova in uno stato finale

L(M) = {x|<q0,x,Z0>|*<q,ε,γ>,q∈F,γ∈Γ*} NOTA BENE. Si può dimostrare che le due definizioni sono equivalenti.

Z0 A a b a b

q0 A q0

AA q0

ε q1

q1 ε q1

Esempio. Automa a pila che riconosce wwR con w in (0+1)+ M=<{0,1},{R,Z,U},R,{q1,q2},q1,∅,δ> δ(q1,0,R)={<q1,ZR>} δ(q1,1,R)={<q1,UR>} δ(q1,0,Z)={<q1,ZZ>,<q2,ε>} δ(q1,0,U)={<q1,ZU>} δ(q1,1,Z)={<q1,UZ>} δ(q1,1,U)={<q1,UU>,<q2,ε>} δ(q2,0,Z)={<q2,ε>} δ(q2,1,U)={<q2,ε>} δ(q1,ε,R)={<q2,ε>} δ(q2,ε,R)={<q2,ε>}

Def. Automa a pila deterministico: M=<Σ,Γ,Z0,Q,q0,F,δ> è deterministico se ∀σ∈Σ,Z∈Γ,q∈Q

|δ(q,σ,Z)|+|δ(q,ε,Z)|≤1 La condizione impone che 1. |δ(q,σ,Z)| ≤ 1 2. se è definita una ε-transizione per un certo stato q e per un certo simbolo di pila Z, non deve essere definita un'altra transizione per q, Z NOTA BENE. • La 2. impone che se M riconosce ε, allora è non deterministico. • Si può ovviare a questa limitazione chiudendo tutte le strighe con un carattere speciale "$"

Automi a pila e linguaggi non contestuali Teorema. Se L(G) è non contestuale esiste un automa a pila M tale che L(G)=N(M) Dim. Sia G=<Σ,VN,P,S> tale che ε∉L(G) e supponiamo G in GNF. In questo caso il PDA ha un solo stato e i non terminali della grammatica possono 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)

Per completare la dimostrazione dobbiamo mostrare che <q,x,S>|*<q,ε,ε> se e solo se S ⇒*x (1) Dimostriamo per induzione su i che

se <q,xu,S>|i<q,u,α> allora S⇒ixα i=1 se <q,xu,S>|1<q,u,α> allora x∈Σ e dobbiamo avere una regola di transizione δ(q,x,S) = {<q, α>}, quindi, per costruzione, deve esistere in P una produzione S →xα

i>1 x∈Σ*, x=ya, a∈Σ se <q,xu,S>|i<q,u,α>, allora ∃β tale che <q,yau,S>|i-1<q,au,β>|1<q,u,α> Per ipotesi induttiva S⇒i-1yβ , inoltre <q,au,β>|1<q,u,α> implica che in P esista una produzione A→aη con β=Aγ e α=ηγ Quindi S ⇒* yβ = yAγ ⇒ yaηγ = yaα = xα

Vediamo ora che vale anche il viceversa (2) Dimostriamo per induzione su i che

se S⇒ixα allora <q,xu,S>|i<q,u,α> i=1 se S⇒1xα allora x∈Σ ed esiste in P una produzione S →xα e quindi, per costruzione, esiste una regola di transizione δ(q,x,S) = {<q, α>} e quindi <q,xu,S>|1<q,u,α> i>1 x∈Σ*, x=ya, a∈Σ Se S⇒ixα allora esiste A→aη in P tale che S⇒i-1yAγ ⇒ yaηγ con x=ya e α=ηγ (derivazione sinistra). Per ipotesi induttiva <q,yv,S>|i-1<q,v,Aγ>e e, in particolare, se v=au, <q,yau,S>|i-1<q,au,Aγ>;

ma poiche' A→aη allora <q,η>∈δ(q,a,A) <q,yau,S>|i-1<q,au,Aγ>|<q,u,ηγ>=<q,u,α>

(3) Rimuoviamo la limitazione che ε∉L(G).

Aggiungiamo un nuovo stato q0 iniziale definiamo la transizione δ(q0,ε,Z0)=<q0,ε> e la transizione δ(q0,a,Z0)={<q,γ>|<q,γ>∈δ(q,a,Z0)}

S A B a b a b a b q SA

q ----- A q

SB q

----- B q

ε q

ε q

Possiamo anche dimostrare il risultato simmetrico. Teorema. Se un linguaggio è accettato da un automa a pila M mediante pila vuota, esiste una grammatica non contestuale G che lo genera, tale cioè che L(G) = N(M) Sia la costruzione della grammatica G a partire dal PDA M, sia la dimostrazione che L(G) = N(M) sono molto laboriosi. In sostanza si tratta di costruire una grammatica che "simula" un automa a pila. Noi non dimostreremo il risultato suddetto ma ne vedremo uno analogo successivamente, quando mostreremo come si può costruire una grammatica di Tipo 0 che "simula" una Macchina di Turing.

11.4 AMBIGUITA’ Problema fondamentale per i linguaggi di programmazione. Def. Una grammatica non contestuale G è ambigua se esiste una stringa x in L(G) derivabile con due diversi alberi di derivazione. Esempio. Data la grammatica E →E+E|E*E|a la stringa a+a*a può essere derivata con alberi di derivazione diversi. NOTA BENE. Ci sono vari metodi per evitare l'ambiguità: • introduzione di parentesi • uso di notazione prefissa • precedenza tra gli operatori

Esempio. La grammatica precedente può essere modificata in E →(E+E)|(E*E)|a Esempio. La grammatica precedente può essere modificata in E →+ E E |* E E | a Esempio. La grammatica delle espressioni aritmetiche utilizza il concetto di precedenza e le parentesi quando le precedenze devono essere violate E →E+T|E-T|T T →T*F|T/F|F F →(E)|a

Def. Un linguaggio di tipo 2 è inerentemente ambiguo se tutte le grammatiche che lo generano sono ambigue. Esempio. Il linguaggio generato dalla grammatica: E →E+E|E*E|a non è inerentemente ambiguo poichè ha una grammatica equivalente non ambigua: E →a+E|a*E|a Esempio. Il linguaggio: {anbncm|n,m≥1}∪{ambncn|n,m≥1} è inerentemente ambiguo, infatti, qualunque grammatica per tale linguaggio genera le stringhe anbncn in due modi diversi.

NOTA BENE Il problema dell’ambiguità di una grammatica e il problema della ambiguità di un linguaggio sono indecidibili.

Confronto tra linguaggi regolari e linguaggi non contestuali.

Proprietà di chiusura. REG CF unione si si concatenazione si si stella si si intersezione si no complementazione si no

Problemi di decisione. REG CF w in L? DEC DEC L=∅? DEC DEC |L|=∞? DEC DEC L1=L2? DEC INDEC L1∩L2=∅? DEC INDEC

Linguaggi non contestuali deterministici Def. I linguaggi CF deterministici sono quelli riconosciuti da automi a pila deterministici. Perchè sono importanti i CF deterministici? I linguaggi CF possono essere analizzati in tempo lineare solo con PDA non deterministici. Se si utilizzano metodi deterministici il tempo può essere (nel caso generale) O(n3). I linguaggi di programmazione si vuole che siano analizzabili in tempo lineare (anzi, con una sola scansione) con metodi deterministici. Pertanto è necessario che i linguaggi di programmazione siano CF deterministici. NOTA BENE. Il problema della decidibilità dell'equivalenza degli automi a pila deterministici (e dei linguaggi relativi) è stato risolto positivamente dopo 40 anni.