![Page 1: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/1.jpg)
GRAMMATICHE LIBERE DAL CONTESTO
➜ Una grammatica è, intuitivamente, un insieme di regole che permettonodi generare un linguaggio.
➜ Un ruolo fondamentale tra le grammatiche è costituito dallegrammatiche libere dal contesto.
Definizione 1 Una grammatica libera dal contesto (CF) è unaquadrupla G = 〈V, T, P, S〉, dove:
• V è un insieme finito di variabili, o simboli non terminali;
• T è un insieme finito di simboli terminali (V ∩ T = ∅);
• P è un insieme finito di produzioni della forma A → α dove:
– A ∈ V è una variabile, e
– α ∈ (V ∪ T )∗;
• S ∈ V è una variabile speciale, detta simbolo iniziale.
GRAMMATICHE LIBERE DAL CONTESTO 1
![Page 2: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/2.jpg)
GRAMMATICHE LIBERE DAL CONTESTO (ESEMPIO)➜ Sia G la grammatica
G ={
{E}, {or, and, not, (, ), 0, 1}, P,E}
,
dove P è costituito dall’insieme di produzioni
E → 0,
E → 1,
E → (E or E),
E → (E and E),
E → ( notE).
➜ G genera delle espressioni booleane.
GRAMMATICHE LIBERE DAL CONTESTO (ESEMPIO) 2
![Page 3: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/3.jpg)
GRAMMATICHE LIBERE DAL CONTESTO (NOTAZIONE)
In generale:
➜ A,B,C,D,E, S denotano variabili;
➜ S denota il simbolo iniziale;
➜ a, b, c, d, e, 0, 1 denotano simboli terminali;
➜ X,Y, Z denotano simboli che possono essere sia terminali che variabili;
➜ u, v, w, x, y, z denotano stringhe di terminali;
➜ α, β, γ, δ stringhe generiche di simboli (sia terminali che non);
➜ se A → α1, . . . , A → αn ∈ P , esprimeremo questo fatto sinteticamente
con A → α1| · · · |αn;
➜ chiameremo A-produzione una generica produzione con la variabile A
a sinistra.
➜ Esempio: E → 0|1|(E or E)|(E and E)|( notE).
GRAMMATICHE LIBERE DAL CONTESTO (NOTAZIONE) 3
![Page 4: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/4.jpg)
GRAMMATICHE LIBERE DAL CONTESTO : DERIVAZIONE
Sia G = 〈V, T, P, S〉 una grammatica:
➜ Se A → β ∈ P e α, γ ∈ (V ∪ T )∗, allora αAγG⇒ αβγ (αAγ deriva
immediatamente αβγ).
➜ Se α1, . . . , αi ∈ (V ∪ T )∗, i ≥ 2, e
i−1∧
j=1
αjG⇒ αj+1,
allora α1G⇒i−1 αi (α1 deriva αi in i− 1 passi).
➜ Per ogni α ∈ (V ∪ T )∗, α G⇒0 α.
➜ Se esiste i tale per cui α G⇒i β, allora α
G⇒∗ β (da α deriva β).
Nota:➜
G⇒∗ è la chiusura transitiva e riflessiva della relazione G
⇒;
➜ → denota l’appartenenza di una produzione all’insieme P ;
➜ ⇒ denota una relazione tra stringhe.
GRAMMATICHE LIBERE DAL CONTESTO: DERIVAZIONE 4
![Page 5: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/5.jpg)
GRAMMATICHE LIBERE DAL CONTESTO : LINGUAGGIO GENERATO
➜ Sia G = 〈V, T, P, S〉 una grammatica. Il linguaggio generato da G è:
L(G) = {w ∈ T ∗ | SG⇒∗ w }.
➜ L è un linguaggio libero dal contesto (CF) se esiste una grammatica CFG tale che L = L(G).
➜ Due grammatiche G1 e G2 sono equivalenti se L(G1) = L(G2).
GRAMMATICHE LIBERE DAL CONTESTO: LINGUAGGIO GENERATO 5
![Page 6: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/6.jpg)
GRAMMATICHE LIBERE DAL CONTESTO : ESEMPI
Esempio 2 Σ∗ è un linguaggio CF. Infatti, se Σ = {s1, . . . , sn}, alloraΣ∗ è generato da S → ε|s1S| · · · |snS.
Esempio 3 La grammatica schematicamente definita da S → 0S1 | ε
genera il linguaggio { 0n1n | n ≥ 0 } (dimostrare per esercizio).
Attenzione!
➜ Abbiamo dimostrato che quest’ultimo linguaggio non è un linguaggio
regolare. . .
➜ . . . pertanto l’insieme dei linguaggi regolari e quello dei linguaggi CFnon sono lo stesso insieme.
GRAMMATICHE LIBERE DAL CONTESTO: ESEMPI 6
![Page 7: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/7.jpg)
ALBERI DI DERIVAZIONE
Sia G = 〈V, T, P, S〉 una grammatica CF. Un albero è un albero diderivazione (parse tree) per G se:
1. ogni vertice ha una etichetta presa tra V ∪ T ∪ {ε};
2. l’etichetta della radice appartiene a V ;
3. ogni vertice interno (ovvero, non una foglia) ha etichettaappartenente a V ;
4. se un vertice n è etichettato con A e n1, . . . , nk sono(ordinatamente, da sinistra a destra) i vertici figli di A etichettaticon X1, . . . , Xk, allora A → X1 · · ·Xk ∈ P ;
5. se un vertice n ha etichetta ε, allora n è una foglia ed è l’unicofiglio di suo padre.
ALBERI DI DERIVAZIONE 7
![Page 8: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/8.jpg)
ALBERI DI DERIVAZIONE (CONT.)➜ Gli alberi di derivazione sono rappresentazioni grafica delle derivazioni.
➜ Un albero che ha foglie etichettate con simboli non terminali,
rappresenta una derivazione parziale.
➜ Un albero descrive una stringa α ∈ (V ∪ T )∗ se α è la stringa che si può
leggere dalle etichette delle foglie da sinistra a destra.
➜ Esempio: un albero che descrive ((0 or 1) and (not 0))
E
( E and E )jjjjjjjjjjjjjjjjj
ttttttttt
JJJJJJJJJ
TTTTTTTTTTTTTTTTT
( E or E )����
���
�����
////
/
????
???
( not E )����
���
�����
////
/
0 1 0
ALBERI DI DERIVAZIONE (CONT.) 8
![Page 9: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/9.jpg)
DERIVAZIONE E ALBERI
Teorema 4 Sia G = 〈V, T, P, S〉 una grammatica CF. Allora SG⇒∗ α
se e solo se esiste un albero di derivazione con radice etichettata S
per G che descrive α.
Dimostrazione: Si dimostrerà un enunciato più forte:
per ogni A ∈ V si ha che AG⇒∗ α se e solo se esiste un
albero di derivazione per G che descrive α la cui radice èetichettata A.
DERIVAZIONE E ALBERI 9
![Page 10: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/10.jpg)
DERIVAZIONE E ALBERI (=⇒)
Per induzione sul numero i di passi di derivazione per A G⇒i α.
Base: i = 0: A G⇒0 α implica, per definizione, che α = A. Ma l’albero
con unico nodo (radice) etichettato con A è un albero di derivazione(parziale) che descrive A stesso.
Passo: Supponiamo AG⇒i β1Bβ3
G⇒1 β1β2β3
︸ ︷︷ ︸
α
. Per ipotesi induttiva
esiste un albero di derivazione T con radice etichettata A chedescrive β1Bβ3. Ma, per definizione, β1Bβ3
G⇒1 β1β2β3 se e solo se
esiste la produzione B → β2 in P . Ma allora, applicando la regola (4)di definizione di albero, dall’albero T si ottiene l’albero che soddisfa irequisiti.
DERIVAZIONE E ALBERI (=⇒) 10
![Page 11: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/11.jpg)
DERIVAZIONE E ALBERI (⇐=)
Per induzione sul numero di nodi interni dell’albero di derivazioneetichettato in A che descrive α.
Completare per esercizio.
DERIVAZIONE E ALBERI (⇐=) 11
![Page 12: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/12.jpg)
AMBIGUITÀ DELLE DERIVAZIONI
➜ Una derivazione è detta sinistra (leftmost) se ad ogni passo di unaderivazione la produzione è applicata al simbolo non terminale più asinistra.
➜ Una derivazione è detta destra (rightmost) se ad ogni passo di unaderivazione la produzione è applicata al simbolo non terminale più adestra.
➜ Se w ∈ L(G), dal teorema appena visto sappiamo che per essa esistealmeno un albero di derivazione con radice etichettata S.
➜ Fissato un albero di derivazione per w con radice etichettata S, sidimostra (farlo per esercizio) che esistono esattamente una derivazionesinistra ed esattamente una derivazione destra che gli corrispondono.
➜ In generale, un albero di derivazione rappresenta più derivazioni distintedi una stessa stringa.
➜ Il che non è un problema. . . il punto è che ci possono essere più alberidi derivazione per la stessa parola:
AMBIGUITÀ DELLE DERIVAZIONI 12
![Page 13: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/13.jpg)
AMBIGUITÀ DELLE DERIVAZIONI (CONT.)➜ Si consideri la grammatica
E → E + E|E ∗ E|0|1|2 .
➜ Una derivazione sinistra è:
EG⇒ E + E
G⇒ E ∗ E + E
G⇒3 2 ∗ 0 + 1 .
➜ Un’altra derivazione sinistra per la stessa stringa è:
EG⇒ E ∗ E
G⇒ 2 ∗ E
G⇒ 2 ∗ E + E
G⇒2 2 ∗ 0 + 1 .
➜ Gli alberi associati alle due derivazioni sono quindi diversi!
AMBIGUITÀ DELLE DERIVAZIONI (CONT.) 13
![Page 14: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/14.jpg)
AMBIGUITÀ DELLE DERIVAZIONI (CONT.)
E
E + E��
����
�
????
???
E ∗ E�����
////
/
2 0
1
E
E ∗ E��
����
�
????
???
E + E�����
////
/
2
10➜ L’albero a sinistra è intuitivamente associato a (2 ∗ 0) + 1 = 1;
➜ quello a destra a 2 ∗ (0 + 1) = 2.
AMBIGUITÀ DELLE DERIVAZIONI (CONT.) 14
![Page 15: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/15.jpg)
AMBIGUITÀ DEL LINGUAGGIO
➜ Una grammatica CF tale per cui esiste una parola con più di un albero
di derivazione con radice etichettata S è detta ambigua.
➜ Un linguaggio CF per cui ogni grammatica che lo genera è ambigua è
detto essere inerentemente ambiguo.
➜ Un esempio di linguaggio inerentemente ambiguo è:
L ={ anbncmdm : n ≥ 1,m ≥ 1}
∪{ anbmcmdn : n ≥ 1,m ≥ 1}.
AMBIGUITÀ DEL LINGUAGGIO 15
![Page 16: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/16.jpg)
AMBIGUITÀ DEL LINGUAGGIO
➜ Un altro esempio di linguaggio inerentemente ambiguo è L = L1 ∪ L2
con
L1 = { ambmcn | m,n ≥ 0 },
L2 = { ambncn | m,n ≥ 0 }.
➜ È libero dal contesto, in quanto generato, tra le altre, dalla grammatica
S → S1|S2
S1 → A1C S2 → AB1
A1 → ε|aA1b B1 → ε|bB1c
A → ε|aA C → ε|cC
➜ Informalmente: L1 ∩ L2 = { ambmcm | m ≥ 0 } non è libero dalcontesto, perciò nessuna grammatica libera da contesto può deciderecome vanno interpretate le stringhe in L1 ∩ L2.
AMBIGUITÀ DEL LINGUAGGIO 16
![Page 17: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/17.jpg)
SEMPLIFICAZIONE DI GRAMMATICHE CF➜ È possibile vincolare la forma delle produzioni delle grammatiche CF
senza alterare la classe dei linguaggi generabili.
➜ Mostreremo che ogni linguaggio CF può essere generato da una
grammatica G dalle seguenti due proprietà:
1. ogni variabile e ogni simbolo terminale di G compaiono in almenouna derivazione di una qualche parola di L;
2. non ci sono produzioni della forma A → B con A e B variabili.
➜ Inoltre, se ε /∈ L, si possono sempre evitare produzioni della forma
A → ε.
➜ Se ε /∈ L, si può richiedere che ogni produzione sia della forma
A → BC o A → a (forma normale di Chomsky).
➜ Se ε /∈ L, si può richiedere che ogni produzione sia della forma A → aα
con α ∈ V ∗ (forma normale di Greibach).
SEMPLIFICAZIONE DI GRAMMATICHE CF 17
![Page 18: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/18.jpg)
ELIMINAZIONE DI SIMBOLI INUTILI
Sia G = 〈V, T, P, S〉 una grammatica CF.
➜ Un simbolo X ∈ V ∪ T è utile se esiste una derivazione
SG⇒∗ αXβ
G⇒∗ w
con w ∈ T ∗.
➜ Altrimenti X è detto inutile.
➜ Mostreremo come i simboli inutili si possano eliminare in due passi:➜ prima si eliminano le variabili che non conducono in nessun modo
ad una stringa di terminali;➜ poi si eliminano i simboli che non sono mai raggiunti da S.
ELIMINAZIONE DI SIMBOLI INUTILI 18
![Page 19: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/19.jpg)
ELIMINAZIONE DELLE VARIABILI IMPRODUTTIVE
Lemma 5 Data una grammatica CF G = 〈V, T, P, S〉 tale cheL(G) 6= ∅, si può calcolare in modo effettivo una grammaticaequivalente G′ = 〈V ′, T, P ′, S〉 (ovvero per cui L(G′) = L(G)) tale
che, per ogni A ∈ V ′, esiste w ∈ T ∗ tale che AG′
⇒∗ w.
Dimostrazione:➜ Per calcolare V ′ usiamo il seguente operatore Γ: ℘(V ) → ℘(V ):
Γ(W ) ={
A ∈ V∣
∣ ∃α ∈ (T ∪W )∗ . (A → α) ∈ P}
➜ Per induzione su i ≥ 1, si mostra simultaneamente su tutti gli A ∈ V cheA ∈ Γi(∅) se e solo se esiste un albero di derivazione che descrivew ∈ T ∗ con radice etichettata con A e di altezza ≤ i (completare peresercizio).
➜ Dunque, per il teorema sulla corrispondenza tra alberi e derivazioni, si
ha che A ∈ Γi(∅) per qualche i sse AG⇒∗ w.
ELIMINAZIONE DELLE VARIABILI IMPRODUTTIVE 19
![Page 20: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/20.jpg)
ELIMINAZIONE DELLE VARIABILI IMPRODUTTIVE (CONT.)➜ Poiché V è finito e Γ monotono, si ha che esiste i ≤ |V | tale per cui
Γi(∅) = Γ(Γi(∅)) = Γi+1(∅)(= Γi+2(∅) = · · · )
➜ Pertanto si riesce a calcolare finitamente l’insieme V ′ = Γ|V |(∅), eP ′ =
{
A → α ∈ P∣
∣ A ∈ V ′ ∧ α ∈ (V ′ ∪ T )∗}
.
➜ L’ipotesi che il linguaggio sia non vuoto è indispensabile. Se infatti fosse
L = ∅, il procedimento eliminerebbe il simbolo iniziale dellagrammatica, il che non è ammissibile.
➜ D’altra parte l’applicazione della procedura del lemma ad unagrammatica permette di determinare se il linguaggio generato è vuoto o
meno (lo è se e solo se la procedura eliminerebbe il simbolo iniziale).
ELIMINAZIONE DELLE VARIABILI IMPRODUTTIVE (CONT.) 20
![Page 21: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/21.jpg)
ELIMINAZIONE DEI SIMBOLI IRRAGGIUNGIBILI DA S
Lemma 6 Data una grammatica CF G = 〈V, T, P, S〉, si puòcalcolare in modo effettivo una grammatica equivalenteG′ = 〈V ′, T ′, P ′, S〉 tale che per ogni X ∈ (V ′ ∪ T ′) esistono α e β in
(V ′ ∪ T ′)∗ per cui S G′
⇒∗ αXβ.
Dimostrazione:➜ Definiamo l’operatore Γ: ℘(V ∪ T ) → ℘(V ∪ T ) come
Γ(W ) ={
X ∈ V ∪ T∣
∣ ∃A ∈ W . (A → αXβ) ∈ P}
∪ {S}.
➜ Per induzione su i ≥ 0, si mostra (farlo per esercizio) che X ∈ Γi({S})
se e solo se esiste un albero di derivazione (parziale) con radiceetichettata S e di altezza ≤ i in cui X compare come foglia.
➜ Per il teorema di corrispondenza tra alberi e derivazioni si ha cheX ∈ Γi({S}) per qualche i ∈ N se e solo se esistono α e β in (V ∪ T )∗
per cui S G⇒∗ αXβ.
ELIMINAZIONE DEI SIMBOLI IRRAGGIUNGIBILI DA S 21
![Page 22: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/22.jpg)
ELIMINAZIONE DI SIMBOLI IRRAGGIUNGIBILI DA S (CONT.)➜ Γ è monotono, V e T sono finiti, dunque esiste i ≤ |V |+ |T | tale che
Γi({S}) = Γi+1({S})(
= Γi+2({S})
= · · ·)
➜ Siano dunque:➜ V ′ = Γ|V |+|T |
(
{S})
∩ V ;➜ T ′ = Γ|V |+|T |
(
{S})
∩ T ;➜ P ′ =
{
(A → α) ∈ P∣
∣ A ∈ V ′ ∧ α ∈ (V ′ ∪ T ′)∗}
.
Teorema 7 Ogni linguaggio CF non vuoto è generato da unagrammatica CF priva di simboli inutili.
Dimostrazione: Immediato, applicando nell’ordine i due lemmi oravisti. (Perché?)
ELIMINAZIONE DI SIMBOLI IRRAGGIUNGIBILI DA S (CONT.) 22
![Page 23: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/23.jpg)
ELIMINAZIONE DI ε-PRODUZIONI
➜ Data una grammatica CF che genera un linguaggio L, si desideraeliminare le produzioni della forma A → ε.
➜ Qualora ε ∈ L, ammetteremo la presenza della produzione S → ε.
➜ Il metodo è quello di determinare quali variabili A ∈ V sono tali che
AG⇒∗ ε. Tali variabili sono dette annullabili.
➜ Il metodo consiste nell’eliminare, tra le Xi di ogni produzioneA → X1 · · ·Xn zero, una, . . . , o tutte le variabili annullabili.
➜ Se togliendo tutte le variabili annullabili da X1 · · ·Xn la stringa
diventasse vuota, allora anche A sarà annullabile (ma nonaggiungeremo la produzione A → ε, a meno che A non sia S).
ELIMINAZIONE DI ε-PRODUZIONI 23
![Page 24: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/24.jpg)
ELIMINAZIONE DI ε-PRODUZIONI (CONT.)
Teorema 8 Se L = L(G) per qualche grammatica CFG = 〈V, T, P, S〉, allora L \ {ε} è un linguaggio CF generato da unagrammatica G′ = 〈V ′, T ′, P ′, S〉 senza simboli inutili e senzaε-produzioni.
Dimostrazione: Definiamo l’operatore Γ: ℘(V ) → ℘(V ) come
Γ(W ) ={A ∈ V
∣∣ ∃A → α ∈ P . α \W = ε
}
dove, per ogni W ∈ ℘(V ),
ε \W = ε,
Xα \W =
α \W, se X ∈ W ;
X(α \W ), se X /∈ W .
ELIMINAZIONE DI ε-PRODUZIONI (CONT.) 24
![Page 25: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/25.jpg)
ELIMINAZIONE DI ε-PRODUZIONI (CONT.)➜ Γ è monotono, V è finito, dunque esiste i ≤ |V | tale che
Γi(∅) = Γi+1(∅).
➜ Siano dunque N = Γ|V |(∅) e
P ′′ =
A → α1 · · ·αn
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
A → X1 · · ·Xn ∈ P,
Xi /∈ N =⇒ αi = Xi,
Xi ∈ N =⇒ αi = Xi ∨ αi = ε,
α1 · · ·αn 6= ε
➜ E’ facile mostrare (farlo per esercizio) cheL(G) \ {ε} = L
(
〈V, T, P ′′, S〉)
.
➜ Applichiamo dunque il teorema sull’eliminazione dei simboli inutili allagrammatica 〈V, T, P ′′, S〉 per ottenere la grammatica desiderata
〈V ′, T ′, P ′, S〉.
ELIMINAZIONE DI ε-PRODUZIONI (CONT.) 25
![Page 26: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/26.jpg)
ELIMINAZIONE DI ε-PRODUZIONI (CONT.)➜ Ovviamente, se ε ∈ L, aggiungeremo la produzione S → ε.
➜ Si osservi come la procedura individuata dalla dimostrazione permettadi capire se ε ∈ L.
➜ E’ infatti sufficiente vedere se esiste in P una produzione S → A1 · · ·Ak
con le Ai ∈ N per i = 1, . . . , k, oppure direttamente la produzioneS → ε.
ELIMINAZIONE DI ε-PRODUZIONI (CONT.) 26
![Page 27: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/27.jpg)
ELIMINAZIONE DI PRODUZIONI UNITARIE
➜ Una produzione della forma A → B, con A e B variabili, si dice unitaria.
Teorema 9 Ogni linguaggio CF L tale che ε /∈ L è generabile da unagrammatica senza simboli inutili, senza ε-produzioni e senzaproduzioni unitarie.
Dimostrazione:➜ Grazie ai risultati già visti, possiamo partire da una grammatica senza
simboli inutili e senza ε-produzioni.
➜ Innanzitutto si calcola, per ogni A ∈ V ,
seguenti(A) = {B ∈ V | AG⇒∗ B }
➜ Poi si tolgono da P tutte le produzioni unitarie e, per ogni A ∈ V e perogni produzione non unitaria B → β ∈ P con B ∈ seguenti(A) e B 6= A,si aggiunge la produzione A → β.
ELIMINAZIONE DI PRODUZIONI UNITARIE 27
![Page 28: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/28.jpg)
ELIMINAZIONE DI PRODUZIONI UNITARIE (CONT.)➜ L’equivalenza dei linguaggi si dimostra (farlo per esercizio) per
induzione sul numero di produzioni unitarie presenti in una derivazione.
➜ Questa procedura potrebbe aver generato simboli inutili. Esempio:
P = {S → A,A → a}.➜ Ma questi possono essere rimossi, come visto, e questo senza
introdurre nuove produzioni unitarie.
ELIMINAZIONE DI PRODUZIONI UNITARIE (CONT.) 28
![Page 29: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/29.jpg)
FORMA NORMALE DI CHOMSKY
Teorema 10 (Chomsky, 1959) Ogni linguaggio context-free L taleche ε /∈ L è generato da una grammatica in cui tutte le produzionisono della forma A → BC e A → a.
Dimostrazione:
➜ Grazie ai risultati già visti, possiamo partire da una grammaticaG = 〈V, T, P, S〉 senza simboli inutili, senza ε-produzioni e senza
produzioni unitarie.
➜ Sia A → X1 · · ·Xm ∈ P con m ≥ 1 (non vi sono ε-produzioni):
➜ se m = 1, allora, poiché non vi sono produzioni unitarie, X1 ∈ T : OK;
➜ se m = 2 e X1, X2 ∈ V : OK;
FORMA NORMALE DI CHOMSKY 29
![Page 30: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/30.jpg)
FORMA NORMALE DI CHOMSKY (CONT.)➜ se m ≥ 2 e qualcuno degli Xi ∈ T , allora per ogni Xi ∈ T introduco in
V una nuova variabile, diciamo Bi, aggiungo la produzione Bi → Xi e
rimpiazzo la produzione A → X1 · · ·Xm con A → Y1 · · ·Ym, oveYi = Xi se Xi ∈ V e Yi = Bi altrimenti;
➜ se m > 2 e tutti gli Xi sono variabili, allora rimpiazzo la produzione
A → X1 · · ·Xm con le produzioni A → BX3 · · ·Xm e B → X1X2, doveB è una nuova variabile da aggiungere a V .
➜ È immediato verificare che il procedimento termina e che l’insiemefinale di produzioni, P ′, è nella forma normale di Chomsky.
FORMA NORMALE DI CHOMSKY (CONT.) 30
![Page 31: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/31.jpg)
FORMA NORMALE DI CHOMSKY (CONT.)➜ Resta da provare che G′ = 〈V ′, T, P ′, S〉 (dove V ′ si ottiene da V con
l’aggiunta delle nuove variabili) è equivalente a G. Ovvero che, per ogniA ∈ V ,
AG⇒∗ w ⇐⇒ A
G′
⇒∗ w.
➜ Si dimostra (farlo per esercizio) per induzione su i ≥ 1 che AG⇒i w
implica che esiste j ≥ i tale che AG′
⇒j w.➜ Viceversa, si dimostra (farlo per esercizio) per induzione su i ≥ 1
che AG′
⇒i w implica che AG⇒j w per qualche j ≤ i.
FORMA NORMALE DI CHOMSKY (CONT.) 31
![Page 32: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/32.jpg)
FORMA NORMALE DI GREIBACH
Per raggiungere questa forma normale abbiamo bisogno di duelemmi preliminari.
Lemma 11 (Unfolding) Sia G = 〈V, T, P, S〉 una grammatica CF, siaA → αBγ una produzione di P e B → β1| · · · |βn l’insieme delleB-produzioni. Sia G′ = 〈V, T, P ′, S〉 ottenuta da G eliminando laproduzione A → αBγ da P e aggiungendo le produzioniA → αβ1γ| · · · |αβnγ. Allora L(G) = L(G′).
Dimostrazione: Per esercizio.
FORMA NORMALE DI GREIBACH 32
![Page 33: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/33.jpg)
FORMA NORMALE DI GREIBACH (CONT.)
Lemma 12 (Eliminazione ricorsione sinistra) Sia G = 〈V, T, P, S〉
una grammatica CF e sia A → Aα1| · · · |Aαm l’insieme delleA-produzioni di G per cui A è anche il simbolo più a sinistra dellastringa di destra delle produzioni. Siano A → β1| · · · |βn le rimanentiA-produzioni. G è equivalente a G′ = 〈V ∪ {B}, T, P ′, S〉 dove si èaggiunta una nuova variabile B a V e si sono rimpiazzate tutte leA-produzioni con
1. A → βi|βiB per i ∈ {1, . . . , n};
2. B → αi|αiB per i ∈ {1, . . . ,m}.
Dimostrazione:➜ Mostriamo prima che se x ∈ L(G) allora x ∈ L(G′).
➜ Sia TS un albero di derivazione per x in G.
FORMA NORMALE DI GREIBACH (CONT.) 33
![Page 34: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/34.jpg)
FORMA NORMALE DI GREIBACH (CONT.)➜ Sia TA un sottoalbero di TS radicato in un nodo v etichettato con A tale
che v non è il figlio sinistro di un nodo etichettato con A.
➜ Il sottoalbero di TA che comprende tutte e sole le applicazioni diA-produzioni a nodi in posizione leftmost ha una frontiera della forma
βjαi1 · · ·αik , con k ≥ 0, 1 ≤ j ≤ n e {i1, . . . , ik} ⊆ {1, . . . ,m}.
➜ L’albero T ′A, radicato in v′ etichettato con A e ottenuto dalla produzione
A → βj (se k = 0) oppure da A → βjB e poi espandendo il B-nodorightmost con B → αi1 , . . . , B → αik è un albero di derivazione per G′
con la stessa frontiera di TA.
➜ Siccome la sostituzione di TA con T ′A si può effettuare per ogni scelta di
TA in TS , iterando il procedimento si ottiene un albero T ′S che è di
derivazione per G′ e la cui frontiera è x.
➜ Completare e dimostrare l’implicazione inversa
(x ∈ L(G′) =⇒ x ∈ L(G)) per esercizio.
FORMA NORMALE DI GREIBACH (CONT.) 34
![Page 35: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/35.jpg)
FORMA NORMALE DI GREIBACH (CONT.)
Teorema 13 (Greibach, 1965) Ogni linguaggio context-free L taleche ε /∈ L è generato da una grammatica in cui tutte le produzionisono della forma A → aα, ove α è una stringa (eventualmente vuota)di simboli non terminali.
Dimostrazione: Sia G una grammatica in forma normale diChomsky. Sia V = {A1, . . . , Am}. Si costruirà in tre passi unagrammatica G′ in forma normale di Greibach equivalente a G.
FORMA NORMALE DI GREIBACH (CONT.) 35
![Page 36: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/36.jpg)
FORMA NORMALE DI GREIBACH (PASSO 1)➜ Si applica il seguente algoritmo:
for k := 1 to m do
begin
for j := 1 to k − 1 do
elimina le produzioni Ak → Ajα mediante unfolding;
elimina le produzioni Ak → Akα mediante elim. ricors. sinistra
end;
➜ A causa dell’eliminazione della ricorsione sinistra sono state introdotte
delle nuove variabili: B1, . . . , Bh.
➜ L’equivalenza tra G e la grammatica ottenuta deriva dai lemmi appenadimostrati.
FORMA NORMALE DI GREIBACH (PASSO 1) 36
![Page 37: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/37.jpg)
FORMA NORMALE DI GREIBACH (PASSO 1, CONT.)➜ A questo punto tutte le produzioni sono della forma:
Ai → Ajα j > i
Ai → aβ a ∈ T
Bi → γ
➜ Poiché siamo partiti da una grammatica in forma normale di Chomsky,si osserva che α è una stringa di variabili.
➜ Per lo stesso motivo, β è una stringa di variabili.
➜ Per quanto riguarda le stringhe γ, esse non iniziano mai con un Bj .
FORMA NORMALE DI GREIBACH (PASSO 1, CONT.) 37
![Page 38: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/38.jpg)
FORMA NORMALE DI GREIBACH (PASSO 2)➜ Ogni produzione Am → α ha la parte destra iniziante con un simbolo
terminale.
➜ Posso dunque effettuare l’unfolding delle Ai-produzioni rimpiazzandoAm con ciascuna delle sue possibili parti destre.
➜ Posso iterare questo procedimento all’indietro, ottenendo produzionidella forma:
Ai → aβ a ∈ T
per ogni i = 1, . . . ,m, con β stringa di variabili.
FORMA NORMALE DI GREIBACH (PASSO 2) 38
![Page 39: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/39.jpg)
FORMA NORMALE DI GREIBACH (PASSO 3)➜ Si tratta ora di semplificare le produzioni Bi → γ. Applicando la
sostituzione sul primo (eventuale) simbolo Ai della stringa, si giunge alrisultato.
FORMA NORMALE DI GREIBACH (PASSO 3) 39
![Page 40: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/40.jpg)
FORMA NORMALE DI GREIBACH (ESEMPIO)➜ Sia G =
(
{A1, A2, A2}, {0, 1}, P, A1
)
, conP = {A1 → A2A3, A2 → A3A1 | 1, A3 → A1A2 | 0.
➜ Solo A3 viola la condizione sull’ordinamento, dunque solo le produzioniper A3 devono essere modificate, e diventano
A3 → A3A1A3A2 | 1A3A2 | 0.
➜ L’eliminazione della ricorsione sinistra ci porta a
A3 → 1A3A2B1 | 0B1 | 1A3A2 | 0,
B1 → A1A3A2 | A1A3A2B1.
Tutte le A3-produzioni iniziano con un simbolo terminale.
➜ Facciamo l’unfolding di A3 sull’unica A2-produzione che abbiamo, edora anche questa inizia con un terminale.
➜ Facciamo l’unfolding di A2 sull’unica A1-produzione che abbiamo, edora anche questa inizia con un terminale.
FORMA NORMALE DI GREIBACH (ESEMPIO) 40
![Page 41: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/41.jpg)
FORMA NORMALE DI GREIBACH (CONT.)➜ Un importante caso particolare di grammatiche in forma normale di
Greibach sono le grammatiche CF in cui le produzioni hanno tutte la
forma A → a oppure A → aB.
➜ Tali grammatiche sono dette lineari destre ed hanno l’importantecaratteristica di generare esattamente i linguaggi regolari.
FORMA NORMALE DI GREIBACH (CONT.) 41
![Page 42: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/42.jpg)
AUTOMI A PILA
➜ La pila (in inglese stack) è una struttura dati LIFO (Last In First Out).
➜ Un automa a pila è una macchina costituita da:
1. un controllo che è un automa a stati finiti;
2. un nastro di input che, come negli NFA e DFA, è di sola lettura;
3. una pila sulla quale sono possibili le seguenti operazioni:
• push(α): spinge una stringa α in testa alla pila;• X = pop(): preleva il simbolo in testa alla pila;
• empty(): vero se e solo se se la pila è vuota.
AUTOMI A PILA 42
![Page 43: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/43.jpg)
AUTOMI A PILA (CONT.)
s1 s2 s3 · · · nastro · · ·
⇑
q
m
Z1 Z2 Z3 · · · pila · · ·
AUTOMI A PILA (CONT.) 43
![Page 44: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/44.jpg)
AUTOMI A PILA (CONT.)
Le azioni possibili di un automa a pila sono:
➜ Leggere dal nastro e dalla pila (con l’operazione pop)contemporaneamente:
• avanzare la testina a destra sul nastro;
• cambiare stato nel controllo;
• inserire una stringa (anche vuota) sulla pila (con l’operazione push).
➜ Leggere solo dalla pila:
• cambiare stato nel controllo,
• inserire una stringa (anche vuota) sulla pila.
AUTOMI A PILA (CONT.) 44
![Page 45: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/45.jpg)
AUTOMI A PILA : DEFINIZIONE FORMALE
Definizione 14 Un automa a pila non-deterministico (APND) è una7-upla: M = 〈Q,Σ, R, δ, q0, Z0, F 〉 dove:
• Q è un insieme finito di stati;
• Σ è l’alfabeto (finito) di input;
• R è l’alfabeto (finito) della pila;
• q0 ∈ Q è lo stato iniziale;
• Z0 ∈ R è il simbolo iniziale sulla pila;
• F ⊆ Q è l’insieme degli stati finali;
• δ : Q× (Σ ∪ {ε})×R → ℘f (Q× R∗) è la funzione di transizione.
AUTOMI A PILA: DEFINIZIONE FORMALE 45
![Page 46: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/46.jpg)
AUTOMI A PILA : DESCRIZIONE ISTANTANEA
Definizione 15 Una descrizione istantanea per un APND è unatripla
(q, x, γ)
dove
• q ∈ Q è lo stato corrente;
• x ∈ Σ∗ è la stringa ancora da leggere sul nastro;
• γ ∈ R∗ è la sequenza di simboli contenuti sulla pila.
Se (p, γ) ∈ δ(q, a, Z), un passo di derivazione dell’APND è definito da
(q, aw, Zα) 7→M (p, w, γα).
AUTOMI A PILA: DESCRIZIONE ISTANTANEA 46
![Page 47: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/47.jpg)
AUTOMI A PILA : LINGUAGGIO ACCETTATO
Il linguaggio L(M) riconosciuto da un APND M si può definire in duemodi diversi:
1. per pila vuota:
Lp(M) ={x ∈ Σ∗
∣∣ ∃q ∈ Q . (q0, x, Z0) 7→
∗
M (q, ε, ε)};
2. o per stato finale:
LF (M) ={x ∈ Σ∗
∣∣ ∃q ∈ F . ∃γ ∈ R∗ . (q0, x, Z0) 7→
∗
M (q, ε, γ)}
Proposizione 16 Per ogni APND M , esiste un APND M ′ tale cheLF (M) = Lp(M
′).
Quando l’APND è previsto per riconoscere le stringhe per pila vuotanon è restrittivo assumere F = ∅.
AUTOMI A PILA: LINGUAGGIO ACCETTATO 47
![Page 48: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/48.jpg)
AUTOMI A PILA : ESEMPIO
L’APNDM = 〈{q0, q1}, {a, b, c}, {Z,A,B}, δ, q0, Z,∅〉
dove
q0 ε a b c
Z q0, ZA q0, ZB q1, ε
A
B
q1 ε a b c
Z q1, Z q1, Z
A q1, ε q1, Z q1, Z
B q1, Z q1, ε q1, Z
riconosce per pila vuota il linguaggio xcxr, dove x ∈ {a, b}∗, c /∈ {a, b}
e xr è la stringa x rovesciata (ovvero letta da destra verso sinistra):
εr = ε;
(aw)r = (wr)a.
AUTOMI A PILA: ESEMPIO 48
![Page 49: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/49.jpg)
AUTOMI A PILA : ESEMPIO (RICONOSCIMENTO DI abcba)
a bcba
↑ nastro
q0
l pila
Z
⇒
a b cba
↑ nastro
q0
l pila
Z A
⇒
ab c ba
↑ nastro
q0
l pila
Z BA
⇒
abc b a
↑ nastro
q1
l pila
B A
⇒
abcb a
↑ nastro
q1
l pila
A
⇒
abcba
↑ nastro
q1
l pila
AUTOMI A PILA: ESEMPIO (RICONOSCIMENTO DI abcba) 49
![Page 50: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/50.jpg)
AUTOMI A PILA : ESEMPIO (RICONOSCIMENTO DI abcba)➜ Al contrario di quanto accade per gli automi a stati finiti gli automi a pila
non-deterministici sono strettamente più potenti di quelli deterministici.
➜ Nel caso del linguaggio dell’esempio precedente, un automa a pila
deterministico è sufficiente per via del separatore c.
➜ Grazie ed esso le fasi di caricamento della pila (la lettura della stringa x)
ed il suo scaricamento (la lettura della stringa xr) sono univocamentedelimitate.
➜ Gli automi a pila deterministici sono solitamente utilizzati per il
riconoscimento sintattico dei linguaggi di programmazione.
➜ Si osservi come, anche per questo motivo, la sintassi degli usuali
linguaggi di programmazione sia strutturata in modo tale da intercalareparole chiave come if, while, then, . . .
AUTOMI A PILA: ESEMPIO (RICONOSCIMENTO DI abcba) 50
![Page 51: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/51.jpg)
AUTOMI A PILA : ALTRO ESEMPIO
L’APND
M = 〈{q0, q1}, {a, b}, {Z,A,B}, δ, q0, Z,∅〉
dove
q0 ε a b
Z q0, AZ q0, BZ
A q0, AA q0, BA
q1, ε
B q0, AB q0, BB
q1, ε
q1 ε a b
Z q1, ε
A q1, ε
B q1, ε
riconosce il linguaggio delle stringhe palindrome sull’alfabeto {a, b}:L =
{wwr
∣∣ w ∈ {a, b}∗
}.
AUTOMI A PILA: ALTRO ESEMPIO 51
![Page 52: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/52.jpg)
AUTOMI A PILA : RIDUZIONE DEL NUMERO DEGLI STATI
Teorema 17 Se L = Lp(M) con M APND, allora L = Lp(M′) con
M ′ APND con 1 solo stato.
Dim.: Siano M =⟨Q,Σ, R, δ, q0, Z0,∅
⟩, R′ = {Z0} ∪ (Q×R ×Q), e
M ′ =⟨{�},Σ, R′, δ′,�, Z0,∅
⟩.
Per c ∈ Σ ∪ {ε} e per ogni transizione di M
(p0, B1 . . . Bm) ∈ δ(p, c, A)
introduciamo |Q|m transizioni in M ′: per ogni p1, . . . , pm ∈ Q,(�, (p0, B1, p1)(p1, B2, p2) . . . (pm−1, Bm, pm)
)∈ δ′
(�, c, (p,A, pm)
);
se p = q0 e A = Z0 introduciamo inoltre le |Q|m transizioni(�, (p0, B1, p1)(p1, B2, p2) . . . (pm−1, Bm, pm)
)∈ δ′(�, c, Z0).
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI 52
![Page 53: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/53.jpg)
AUTOMI A PILA : RIDUZIONE DEL NUMERO DEGLI STATI (CONT.)
M ′ simula M “indovinando nondeterministicamente” gli stati futuri diM e “filtrando” poi solo le scelte corrette.
Dimostreremo che, per ogni w, x ∈ Σ∗,
(qo, w, Z0) 7→+
M (p0, x, B1 . . . Bm)
se e solo se esistono p1, . . . , pm ∈ Q tali che
(�, w, Z0) 7→+
M ′
(�, x, (p0, B1, p1) . . . (pm−1, Bm, pm)
).
Questo implica, in particolare, che, per ogni w ∈ Σ∗,
(qo, w, Z0) 7→+
M (p0, ε, ε) ⇐⇒ (�, w, Z0) 7→+
M ′ (�, ε, ε)
ovvero L(M) = L(M ′).
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI (CONT.) 53
![Page 54: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/54.jpg)
AUTOMI A PILA : RIDUZIONE DEL NUMERO DEGLI STATI (CONT.)
Dimostriamo, per induzione sulla lunghezza n delle derivazioni, che,per ogni w, x ∈ Σ∗,
(qo, w, Z0) 7→nM (p0, x, B1 . . . Bm)
implica che esistono p1, . . . , pm ∈ Q tali che
(�, w, Z0) 7→nM ′
(�, x, (p0, B1, p1) . . . (pm−1, Bm, pm)
).
L’implicazione inversa è lasciata per esercizio.
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI (CONT.) 54
![Page 55: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/55.jpg)
AUTOMI A PILA : RIDUZIONE DEL NUMERO DEGLI STATI (CONT.)
Caso base, n = 1: per c ∈ Σ ∪ {ε},
(qo, cx, Z0) 7→M (p0, x, B1 . . . Bm)
implica
(p0, B1 . . . Bm) ∈ δ(qo, c, Z0),
il che implica che esistono p1, . . . , pm ∈ Q tali che
(�, (p0, B1, p1) . . . (pm−1, Bm, pm)
)∈ δ′(�, c, Z0)
e dunque
(�, cx, Z0) 7→M ′
(�, x, (p0, B1, p1) . . . (pm−1, Bm, pm)
).
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI (CONT.) 55
![Page 56: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/56.jpg)
AUTOMI A PILA : RIDUZIONE DEL NUMERO DEGLI STATI (CONT.)
Passo induttivo, n = t+ 1: per c ∈ Σ ∪ {ε},
(qo, w, Z0) 7→tM (p′0, cx, A1 . . . Ar) 7→M (p′′0 , x, B1 . . . BmA2 . . . Ar)
implica:
➀ esistono p′1, . . . , p′r ∈ Q tali che
(�, w, Z0) 7→tM′
(
�, cx, (p′0, A1, p′1) . . . (p
′r−1, Ar, p
′r))
.
➁ (p′′0 , B1 . . . Bm) ∈ δ(p′0, c, A1), ovvero esistono p′′1 , . . . , p′′m ∈ Q, con
p′′m = p′1, tali che
(
�, (p′′0 , B1, p′′1 ) . . . (p
′′m−1, Bm, p′′m)
)
∈ δ′(
�, c, (p′0, A1, p′1))
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI (CONT.) 56
![Page 57: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/57.jpg)
e dunque
(
�, cx, (p′0, A1, p′1) . . . (p
′r−1, Ar, p
′r))
7→M′
(
�, x, (p′′0 , B1, p′′1 ) . . . (p
′′m−1, Bm, p′′m)(p′1, A2, p
′2) . . . (p
′r−1, Ar, p
′r))
.
AUTOMI A PILA: RIDUZIONE DEL NUMERO DEGLI STATI (CONT.) 57
![Page 58: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/58.jpg)
AUTOMI A PILA E LINGUAGGI CF
Teorema 18 Se L = Lp(M) con M APND con 1 stato, allora L è CF.
Dimostrazione:➜ Sia M = 〈{q},Σ, R, δ, q, Z0,∅〉 un APND con 1 solo stato che riconosce
il linguaggio Lp(M).
➜ Definiamo la grammatica libera da contesto G = 〈R,Σ, Z0, P 〉, dove R
sono i simboli non terminali, Z0 ∈ R è il simbolo iniziale e
P ={
Z → aZ1Z2 · · ·Zn
∣
∣ (q, Z1Z2 · · ·Zn) ∈ δ(q, a, Z)}
.
➜ È ovvio che se α ∈ R∗, allora:
(q, a, Zα) 7→M (q, ε, Z1Z2 · · ·Znα) ⇐⇒ ZαG⇒ aZ1Z2 · · ·Znα
➜ Per induzione si dimostra che per ogni x ∈ Σ∗, x 6= ε:
(q, x, Z0) 7→∗M (q, ε, ε) ⇐⇒ Z0
G⇒∗ x.
AUTOMI A PILA E LINGUAGGI CF 58
![Page 59: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/59.jpg)
AUTOMI A PILA E LINGUAGGI CF
Esercizio: Generalizzare la dimostrazione precedente per trattareanche il caso in cui ε ∈ L.
AUTOMI A PILA E LINGUAGGI CF 59
![Page 60: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/60.jpg)
AUTOMI A PILA E LINGUAGGI CF➜ C’è una forte analogia tra la derivazione da una grammatica CF ed i
passi di caricamento/svuotamento della pila durante le varie fasi di
riconoscimento delle sottostringhe di una data stringa da parte di unAPND.
➜ Si consideri la seguente grammatica G in forma normale di Greibach:
S → aB A → a
S → bA B → bS
A → aS B → aBB
A → bAA B → b
AUTOMI A PILA E LINGUAGGI CF 60
![Page 61: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/61.jpg)
AUTOMI A PILA E LINGUAGGI CF (CONT.)➜ Sia M l’APND con 1 solo stato q definito dalla seguente relazione di
transizione:
q ε a b
S q,B q,A
A q, ε q,AA
q, S
B q,BB q, ε
q, S
AUTOMI A PILA E LINGUAGGI CF (CONT.) 61
![Page 62: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/62.jpg)
S
aB
aaBB
aabB aabSB
aabaBB aabaBB
aababB
aababbS aababb
aababSB
aababbAB
��
��
������
��
��??
????
�� ��
������
��
wwoooooooooo
��
��??
????
��
(q, aababb, S)
(q, ababb,B)
(q, babb, BB)
(q, abb, B) (q, abb, SB)
(q, bb, BB) (q, bb, BB)
(q, b, B)
(q, ε, S) (q, ε, ε)
(q, b, SB)
(q, ε, AB)
��
��
������
��
��??
????
�� ��
������
��
wwooooooooo
��
��??
????
��
AUTOMI A PILA E LINGUAGGI CF (CONT.) 62
![Page 63: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/63.jpg)
AUTOMI A PILA E LINGUAGGI CF (CONT.)
Teorema 19 Sia L CF. Allora esiste un APND M tale cheL = Lp(M).
Dimostrazione:➜ Sia L = L(G) con G = 〈V, T, P, S〉 grammatica CF in forma normale di
Greibach.
➜ Definiamo: Q = {q}, Σ = T , R = V , Z0 = S, F = ∅, e
(q, α) ∈ δ(q, a, A) ⇐⇒ A → aα ∈ P.
➜ Si ha una derivazione in G del tipo
xAβG⇒ xaαβ, con α, β ∈ V ∗ e x ∈ T ∗,
se e solo se una mossa di M tale che
(q, a, Aβ) 7→M (q, ε, αβ)
AUTOMI A PILA E LINGUAGGI CF (CONT.) 63
![Page 64: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/64.jpg)
➜ Per induzione sul sul numero di passi della derivazione (completare peresercizio) si ha che
xAβG⇒∗ xyαβ, con A ∈ V , α, β ∈ V ∗ e x, y ∈ T ∗,
se e solo se
(q, y,Aβ) 7→∗M (q, ε, αβ).
➜ Ne consegue che: S G⇒∗ y se e solo se (q, y, S) 7→∗
M (q, ε, ε).
AUTOMI A PILA E LINGUAGGI CF (CONT.) 64
![Page 65: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/65.jpg)
AUTOMI A PILA E LINGUAGGI CF (CONT.)
Esercizio: Generalizzare la dimostrazione precedente per trattareanche il caso in cui ε ∈ L.
AUTOMI A PILA E LINGUAGGI CF (CONT.) 65
![Page 66: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/66.jpg)
IL PUMPING LEMMA PER I LINGUAGGI CF
Lemma 20 (Bar-Hillel, Perles, Shamir, 1961) Sia L un linguaggioCF. Allora esiste una costante n ∈ N (dipendente da L) tale che perogni z ∈ L con |z| ≥ n, esistono stringhe u, v, w, x e y tali che
1. z = uvwxy,
2. |vx| ≥ 1,
3. |vwx| ≤ n, e
4. per ogni i ≥ 0 vale che uviwxiy ∈ L.
Dimostrazione:➜ Dimostriamo che il teorema vale se ε /∈ L (la dimostrazione è appena
più complicata se ε ∈ L).
➜ Sia G = 〈V, T, P, S〉 una grammatica in forma normale di Chomsky chegenera L.
IL PUMPING LEMMA PER I LINGUAGGI CF 66
![Page 67: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/67.jpg)
IL PUMPING LEMMA PER I LINGUAGGI CF (CONT.)➜ Per induzione su i ≥ 1, si dimostra (farlo per esercizio) che se un albero
di derivazione di G per una stringa z ∈ T ∗ ha tutti i cammini di
lunghezza minore o uguale a i, allora |z| ≤ 2i−1.
➜ Sia |V | = k e sia n = 2k (si noti che k ≥ 1 e n ≥ 2).
➜ Se z ∈ L e |z| ≥ n, allora ogni albero di derivazione per z deve avere un
cammino di lunghezza almeno k + 1.
➜ Ma tale cammino ha almeno k + 2 nodi, tutti, eccetto l’ultimo, etichettatida variabili. Pertanto vi deve essere almeno una variabile ripetuta nel
cammino.
➜ In particolare, dunque, vi devono essere due nodi v1 e v2 tali che:
1. entrambi sono etichettati dalla stessa variabile, diciamo A;
2. v1 è più vicino alla radice di v2;
3. poiché n ≥ 2, a v1 è associata una produzione del tipo: A → BC;
4. il cammino da v1 a qualsiasi foglia è lungo al più k + 1.
IL PUMPING LEMMA PER I LINGUAGGI CF (CONT.) 67
![Page 68: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/68.jpg)
IL PUMPING LEMMA PER I LINGUAGGI CF (CONT.)➜ Si prenda ora il sottoalbero T1 con radice in v1: esso rappresenta una
derivazione di una parola z1 di lunghezza al più 2k.
➜ Sia z2 invece la parola relativa al sottoalbero T2 di T1 con radice in v2.
➜ Possiamo scrivere z1 = vz2x.
➜ Inoltre almeno una tra v e x deve essere non vuota, in quanto a v1 èassociata una produzione del tipo: A → BC ed il sottoalbero T2 è unsottoalbero di esattamente uno dei due sottoalberi individuati da B e C.
➜ Dunque
AG⇒∗ vAx e A
G⇒∗ z2
dove |vz2x| ≤ 2k = n.
➜ Ma allora abbiamo anche che AG⇒∗ viz2x
i per ogni i ≥ 0.
➜ Si ponga w = z2 e u e y il prefisso e il suffisso di z necessari affinchèz = uvwxy.
IL PUMPING LEMMA PER I LINGUAGGI CF (CONT.) 68
![Page 69: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/69.jpg)
IL PUMPING LEMMA PER I LINGUAGGI CF (ESEMPIO)➜ Il linguaggio { aibici | i ≥ 1 } non è CF.
➜ Per ogni n ≥ 1 scegliamo z = anbncn, e dunque z ∈ L e |z| ≥ n,
➜ Dobbiamo mostrare che, per ogni quintupla di stringhe u, v,w, x, y ∈ T ∗
tali che anbncn = uvwxy, |vx| ≥ 1 e |vwx| ≤ n, esiste un i ≥ 0 tale percui uviwxiy /∈ L.
➜ Vi sono molti modi di partizionare z in uvwxy che soddisfano i requisiti.Tuttavia questi si possono raggruppare nelle seguenti casistiche:
1. uvwx = ah con h ≤ n
2. u = ah, vwx = akbm con k > 0, k +m ≤ n
3. u = anbh, vwx = bm con m ≤ n
4. u = anbh, vwx = bkcm con k +m ≤ n
5. u = anbnch, vwx = cm con m ≤ n
➜ In ciascuna delle casistiche, tuttavia, si ha che uv0wx0y = uwy /∈ L, inquanto vengono alterati al massimo due tra i numeri di ripetizioni dei tretipi di carattere a, b e c.
IL PUMPING LEMMA PER I LINGUAGGI CF (ESEMPIO) 69
![Page 70: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/70.jpg)
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO
Teorema 21 I linguaggi CF sono chiusi rispetto all’unione, allaconcatenazione, ed alla chiusura di Kleene.
Dimostrazione:
➜ Siano G1 = 〈V1, T1, P1, S1〉 e G2 = 〈V2, T2, P2, S2〉 le grammatichegeneranti i linguaggi L1 e L2.
➜ Per semplicità si assuma che V1 e V2 siano disgiunti (altrimenti siproceda a ridenominare le variabili).
➜ Sia S una nuova variabile.
➜ G∪ = 〈V1 ∪ V2 ∪ {S}, T1 ∪ T2, P1 ∪ P2 ∪ P, S〉, ove P consta delleproduzioni:
S → S1|S2
è la grammatica che genera L1 ∪ L2.
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO 70
![Page 71: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/71.jpg)
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.)➜ G◦ = 〈V1 ∪ V2 ∪ {S}, T1 ∪ T2, P1 ∪ P2 ∪ P, S〉, ove P consta della
produzione:
S → S1S2
è la grammatica che genera L1L2.
➜ G∗ = 〈V1 ∪ {S}, T1, P1 ∪ P, S〉, ove P consta delle produzioni:
S → ε|S1S
è la grammatica che genera L∗1.
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.) 71
![Page 72: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/72.jpg)
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.)
Teorema 22 I linguaggi CF non sono chiusi rispetto all’intersezione.
Dimostrazione:
➜ Consideriamo L1 = { aibicj | i ≥ 1, j ≥ 1 } generato da:
S → RC, R → ab | aRb, C → c | cC
e L2 = { aibjcj | i ≥ 1, j ≥ 1 } generato da:
S → AR, R → bc | bRc, A → a | aA
➜ La loro intersezione è { aibici | i ≥ 1 }, che sappiamo non essere CF.
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.) 72
![Page 73: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/73.jpg)
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.)
Corollario 23 I linguaggi CF non sono chiusi rispetto allacomplementazione.
Dimostrazione: Se lo fossero, allora lo sarebbero anche rispetto
all’intersezione, in quanto A ∩B = A ∪B, ma sappiamo che non losono.
PROPRIETÀ DEI LINGUAGGI LIBERI DAL CONTESTO (CONT.) 73
![Page 74: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/74.jpg)
ALGORITMI DI DECISIONE PER LINGUAGGI CF
Teorema 24 (Vuoto, Finito, Infinito) Data una grammatica CFG = 〈V, T, P, S〉, i problemi
1. L(G) = ∅,
2. L(G) è finito, e
3. L(G) è infinito
sono decidibili.
Dimostrazione di 1: L(G) = ∅ se e solo se l’algoritmo del lemmache mostra come eliminare i simboli improduttivi termina con V ′ taleche S /∈ V ′.
ALGORITMI DI DECISIONE PER LINGUAGGI CF 74
![Page 75: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/75.jpg)
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.)
Dimostrazione di 2 e 3:➜ Se L(G) = ∅ oppure L(G) = {ε} il linguaggio è finito.
➜ Altrimenti, sia G′ = 〈V ′, T, P ′, S〉 una grammatica in forma normale diChomsky, priva di simboli inutili e tale che L(G′) = L(G) \ ε.
➜ Creiamo un grafo G avente:
• un nodo per ogni variabile A ∈ V ′;
• gli archi 〈A,B〉 e 〈A,C〉 per ogni produzione A → BC ∈ P ′.
Allora L(G) (e anche L(G′)) è finito se e solo se G non ha cicli.
➜ Se G non ha cicli, la finitezza è immediata: solo un numero finito di alberidi derivazione con radice etichettata da S possono essere costruiti.
➜ Viceversa, supponiamo G abbia (almeno) un ciclo passante per un nodoassociato ad una variabile A. In tal caso, ripetendo la costruzione vistanella dimostrazione del pumping lemma, si riescono a generare infinitialberi di derivazione diversi.
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.) 75
![Page 76: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/76.jpg)
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.)
Teorema 25 (Appartenenza) Data una grammatica CFG = 〈V, T, P, S〉, e una stringa z, il problema z ∈ L(G) è decidibile.
Dimostrazione:
➜ Per il caso z = ε, dal Teorema di eliminabilità delle ε-produzioni si hache ε ∈ L se e solo se esiste S → A1 · · ·An in P (con n ≥ 0) tale che
Ai ∈ N per i = 1, . . . , n.
➜ Sia z 6= ε e G′ = 〈V ′, T, P ′, S〉 la grammatica equivalente a G in formanormale di Greibach.
➜ Allora, se z ha una derivazione, ne ha una di esattamente |z| passi.Generiamo esaustivamente tutte le derivazioni di |z| passi e
verifichiamo se esiste una di queste che deriva z.
➜ Nota bene: esistono algoritmi più efficienti.
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.) 76
![Page 77: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/77.jpg)
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.)
Il problema dell’equivalenza di due linguaggi liberi dal contesto èindecidibile (vedi Teorema 8.12 in Hopcroft & Ullmann, 1979).
ALGORITMI DI DECISIONE PER LINGUAGGI CF (CONT.) 77
![Page 78: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/78.jpg)
GRAMMATICHE REGOLARI
Una grammatica CF si dice lineare destra se ogni produzione è dellaforma:
A → wB, con w ∈ T+, oppure
A → w, con w ∈ T+
più eventualmente S → ε. Se invece tutte le produzioni sono dellaforma:
A → Bw, con w ∈ T+, oppure
A → w, con w ∈ T+
più eventualmente S → ε, si dice lineare sinistra.
GRAMMATICHE REGOLARI 78
![Page 79: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/79.jpg)
GRAMMATICHE REGOLARI (CONT.)
Lemma 26 Data una grammatica lineare destra G esiste unagrammatica G′ equivalente (in forma normale di Greibach) tale chetutte le produzioni sono della forma:
A → aB, con a ∈ T , oppure
A → a, con a ∈ T
più eventualmente S → ε.
Dimostrazione:➜ Ogni produzione della forma A → a1a2 · · · anB viene sostituita dalle
produzioni: A → a1C1, C1 → a2C2, . . . , Cn−1 → anB, doveC1, . . . , Cn−1 sono nuovi simboli non terminali.
➜ Similmente, A → a1a2 · · · an viene sostituita dalle produzioni:A → a1C1, C1 → a2C2, . . . , Cn−1 → an.
GRAMMATICHE REGOLARI (CONT.) 79
![Page 80: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/80.jpg)
GRAMMATICHE REGOLARI (CONT.)
Teorema 27 Se L è generato da una grammatica lineare destra,allora L è un linguaggio regolare.
Dimostrazione:➜ Sia G = 〈V, T, P, S〉 tale che L(G) = L e nella forma semplificata
descritta nel precedente lemma.
➜ Costruiamo un NFA M = 〈Q,Σ, δ, q0, F 〉 che riconosce L:
• Q = V ∪ {⊥};
• Σ = T ;
• B ∈ δ(A, a) sse A → aB ∈ P , ⊥ ∈ δ(A, a) sse A → a ∈ P ; δ(⊥, a) èindefinito per ogni simbolo a ∈ Σ.
• q0 = S;
• F =
{⊥, S}, se S → ε ∈ P ;
{⊥}, altrimenti.
GRAMMATICHE REGOLARI (CONT.) 80
![Page 81: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/81.jpg)
GRAMMATICHE REGOLARI (CONT.)
➜ Si deve mostrare che δ̂(S,w) ∩ F 6= ∅ se e solo se SG⇒∗ w, per ogni
stringa w.
➜ Mostriamo, per induzione su |w| ≥ 0, che per ogni A ∈ V
A ∈ δ̂(S,w) ⇐⇒ SG⇒∗ wA
Base: Sia w = ε. Per definizione, δ̂(S, ε) = {S}. Per la forma della
grammatica SG⇒∗ εA se e solo se S = A.
Passo: Sia w = va.
A ∈ δ̂(S, va) ⇐⇒ A ∈⋃
B∈δ̂(S,v) δ(B, a) [def. di δ̂ nei NFA]
⇐⇒ A ∈⋃
B :SG⇒∗vB
δ(B, a) [ip. induttiva]
⇐⇒ SG⇒∗ vaA [def. di δ (B → aA ∈ P )]
GRAMMATICHE REGOLARI (CONT.) 81
![Page 82: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/82.jpg)
GRAMMATICHE REGOLARI (CONT.)➜ Abbiamo mostrato che, per ogni w ∈ T ∗ e per ogni A ∈ V
A ∈ δ̂(S,w) ⇐⇒ SG⇒∗ wA
➜ Da questo risultato, per definizione di F ,
F =
{⊥, S}, se S → ε ∈ P ,
{⊥}, altrimenti,
si ha che:
1. SG⇒∗ ε se e solo se δ̂(S, ε) ∩ F 6= ∅;
2. SG⇒∗ va se e solo se esiste A tale che S
G⇒∗ vA e A → a ∈ P . Ciò
accade se e solo se A ∈ δ̂(S, v) e ⊥ ∈ δ(A, a), ovvero ⊥ ∈ δ̂(S, va).
GRAMMATICHE REGOLARI (CONT.) 82
![Page 83: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/83.jpg)
GRAMMATICHE REGOLARI (CONT.)
Teorema 28 Se L è un linguaggio regolare, allora L è generato dauna grammatica lineare destra.
Dimostrazione:
➜ Sia M = 〈Q,Σ, δ, q0, F 〉 il DFA che riconosce L.
➜ Costruiamo una grammatica lineare destra G = 〈V, T, P, S〉 tale che
L(G) = L nel modo seguente:
• V = Q;
• T = Σ;
•
P ∋ A → aB ⇐⇒ δ(A, a) = B
P ∋ A → ε ⇐⇒ A ∈ F
• S = q0.
GRAMMATICHE REGOLARI (CONT.) 83
![Page 84: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/84.jpg)
GRAMMATICHE REGOLARI (CONT.)
➜ Si mostra per induzione su |w| che δ̂(q0, w) = p se e solo se q0G⇒|w| wp
(farlo per esercizio).
➜ A questo punto si ha immediatamente che δ̂(q0, w) ∈ F se e solo se
q0G⇒|w| w.
➜ Per costruzione, la grammatica ottenuta può avere ε-produzioni edunque non è della forma desiderata. Si applichi dunque l’eliminazione
di tali ε-produzioni per ottenere la grammatica nella forma voluta.
GRAMMATICHE REGOLARI (CONT.) 84
![Page 85: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/85.jpg)
GRAMMATICHE REGOLARI (CONT.)➜ Il teorema appena visto implica che ogni linguaggio regolare è anche
CF.
➜ Si possono mostrare risultati analoghi a quelli visti per le grammatiche
lineari destre anche per le grammatiche lineari sinistre (che quindi sonodel tutto equivalenti).
GRAMMATICHE REGOLARI (CONT.) 85
![Page 86: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/86.jpg)
GRAMMATICHE DI TIPO 0
Le grammatiche di tipo 0, o a struttura di frase, sono le grammatichedella forma G = 〈V, T, P, S〉 in cui P contiene produzioni
α → β
dove α ∈ (V ∪ T )+, β ∈ (V ∪ T )∗.
Teorema 29 Si ha L = L(G) con G grammatica a struttura di frasese e solo se L è un insieme ricorsivamente enumerabile.
GRAMMATICHE DI TIPO 0 86
![Page 87: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/87.jpg)
GRAMMATICHE DI TIPO 1
Le grammatiche di tipo 1, o dipendenti dal contesto o monotone,sono le grammatiche della forma G = 〈V, T, P, S〉 in cui P contieneproduzioni
α → β
ove α ∈ (V ∪ T )+, β ∈ (V ∪ T )+, e |α| ≤ |β|, con l’eccezionedell’eventuale produzione S → ε (in tal caso richiediamo che S nonoccorra mai in β).
Per queste grammatiche esiste una forma normale per le produzioni,che devono essere del tipo:
α1Aα2 → α1βα2
con β 6= ε.
GRAMMATICHE DI TIPO 1 87
![Page 88: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/88.jpg)
GRAMMATICHE DI TIPO 1 (CONT.)
Teorema 30 Ogni linguaggio L generato da una grammaticadipendente dal contesto è ricorsivo.
Teorema 31 Ci sono insiemi ricorsivi che non sono generati danessuna grammatica dipendente dal contesto.
GRAMMATICHE DI TIPO 1 (CONT.) 88
![Page 89: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/89.jpg)
GRAMMATICHE DI TIPO 1 (CONT.)➜ Il linguaggio { aibici | i ≥ 1 } è generato dalla grammatica di tipo 1:
S → aSBC | aBC
CB → BC
bB → bb
bC → bc
cC → cc
aB → ab
➜ Tutte le derivazioni iniziano con SG⇒∗ aaa · · · aBCBCBC · · ·BC. Le B
e le C tengono traccia del numero di b e c da inserire.
➜ Le tre regole che possono essere usate sono aB → ab che sistema la b
più a sinistra oppure CB → BC, che potremmo definire regola discambio, e la regola bC → bc, che non va applicata prima del tempo
(bCBG⇒ bcB).
➜ Invece, con un numero opportuno di applicazioni della regola di
scambio, si giunge a a SG⇒∗ aaa · · · abCBC · · ·BC · · ·C da cui
applicando bB → bb, bC → bc, e cC → cc, si ottiene la stringa attesa.
GRAMMATICHE DI TIPO 1 (CONT.) 89
![Page 90: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/90.jpg)
LA GERARCHIA DI CHOMSKY
➜ Sappiamo che il linguaggio { aibi | i ≥ 0 } è un linguaggio CF ma non
regolare.
➜ Sappiamo inoltre che le grammatiche (CF) lineari destre e sinistre
generano esattamente i linguaggi regolari.
➜ Sappiamo che il linguaggio { aibici | i ≥ 1 } è un linguaggio dipendentedal contesto ma non CF.
➜ Dai risultati visti sappiamo anche che la classe di linguaggi generati dagrammatiche dipendenti dal contesto è inclusa strettamente nella classe
di linguaggi generati da grammatiche a struttura di frase.
➜ Viene così indotta una gerarchia di grammatiche, nota come gerarchia
di Chomsky in cui tutte le inclusioni sono proprie.
LA GERARCHIA DI CHOMSKY 90
![Page 91: RAMMATICHE LIBERE DAL CONTESTO Gstudenti.cs.unipr.it/pipermail/fondamenti-informatica/attachments/... · ALBERI DI DERIVAZIONE (CONT.) Gli alberi di derivazione sono rappresentazioni](https://reader034.vdocumenti.com/reader034/viewer/2022051806/5ffd4a0988e0e4584160ece5/html5/thumbnails/91.jpg)
LA GERARCHIA DI CHOMSKY (CONT.)
Struttura di frase
'
&
$
%
Dipendenti dal contesto
'
&
$
%
Libere dal contesto
'
&
$
%Lineari sinistre
Lineari destre
'
&
$
%
'
&
$
%
LA GERARCHIA DI CHOMSKY (CONT.) 91