1. introduzione ai linguaggi formali (fanizzi - carofiglio) · definizionipreliminari...
TRANSCRIPT
Definizioni PreliminariGrammatiche Generative
Esercizi
1. Introduzione ai Linguaggi Formali(Fanizzi - Carofiglio)
17 marzo 2016
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
1 Definizioni PreliminariAlfabeti e StringhePotenze e ChiusureLinguaggi
2 Grammatiche GenerativeDefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
3 Esercizi
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Alfabeti e Stringhe
Un alfabeto è un insieme X finito e non vuoto di simboli
es. X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Una parola (o stringa) w su un alfabeto Xè una sequenza finita di simboli x1, x2, . . . , xn tale che
∀i = 1, . . . , n : xi ∈ X
La lunghezza di w è pari ad n e si denota con |w |.es. X = {0, 1} w = 0010110 |w | = 7.
La parola vuota, denotata con λ, è la parola priva di simboli(quindi |λ| = 0)Si denota con X ∗ l’insieme di tutte le stringhe su X .
es. X = {0, 1} ⇒ X ∗ = {λ, 0, 1, 00, 01, 10, 11, 000, 001, . . .}osservazione: ∀X : λ ∈ X ∗
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Concatenzaione o prodotto
Date α, β ∈ X ∗ tali che α = x1 · · · xm e β = x ′1 · · · x ′n laconcatenazione (o prodotto) di α e β è data dalla stringa αβ(denotata anche α · β) di lunghezza m + n con i primi msimboli uguali a quelli di α e gli ultimi n uguali a quelli di β:
γ = αβ = x1 · · · xmx ′1 · · · x ′n
La concatenzazione su X é una operazione binaria su· : X ∗ × X ∗ → X ∗
ha per elemento neutro λgode della proprietà associativa: α · (β · γ) = (α · β) · γnon è commutativo
Ogni parola w su X si puó scrivere come prodotto di parole dilunghezza unitaria
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Prefisso, suffisso e sottostringa
Data la stringaδ = αβγ
tale che α, β, γ ∈ X ∗,α è un prefisso di δ,γ è un suffisso di δ eβ è una sottostringa di δ
es. δ = 00110
prefissi di δ: λ, 0, 00, 001, 0011 e δsuffissi di δ: λ, 0, 10, 110, 0110 e δsottostringhe di δ:λ, 0, 1, 00, 01, 10, 11, 001, 011, 110, 0011, 0110 e δ
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Potenze e Chiusure
Data α ∈ X ∗, la potenza k-esima di α è definita con:
αk =
{λ k=0ααk−1 k>0
Dunque la potenza k-esima è un caso speciale diconcatenamento
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Potenze e Chiusure
La potenza di un alfabeto è definita come segue:X 1 = X ,X 2 = X · X = {x1x2|x1, x2 ∈ X},X 3 = X · X · X = {x1x2x3|x1, x2, x3 ∈ X} ...etc.
X k =
{{λ} k=0X · X k−1 k>0
L’insieme X+ =⋃
k>0 X k è chiusura transitiva di X .Si osservi che X ∗ = X+ ∪ {λ} è la chiusura riflessiva etransitiva di X
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Linguaggi
Un linguaggio L su un alfabeto X è un sottinsieme di X ∗:
L ⊆ X ∗
Es. Linguaggio delle parentesi ben formate L ⊆ {(, )}∗:(())() ∈ L e ()(()()) ∈ L
mentre(()() 6∈ L
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Linguaggi
I linguaggi possono essere riguardati sotto due punti di vista:Descrittivo-Generativo: come generare le parole w di L ?
L potrebbe essere infinito (estensione) maenumerabile mediante un numero finito di regole(intensione).
Riconoscitivo: come decidere se w ∈ L ?E’ il punto di vista dei compilatori e traduttori in fased’analisi
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Alfabeti e StringhePotenze e ChiusureLinguaggi
Esempio
Esempio. X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}L linguaggio dei numeri relativiUsando il formalismo di Backus-Naur:<S> ::= +<I> | -<I><I> ::= <D> | <I><D><D> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9w = −375 <S> ⇒ -375
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Grammatica Generativa
Una grammatica generativa è una quadrupla G = (X ,V , S ,P):X alfabeto terminale;V alfabeto non terminale (NT), tale che X ∩ V = ∅S ∈ V simbolo di partenza o distintivoP insieme delle produzioni (α, β) denotate anche α −→ β doveα ∈ (X ∪ V )+ contiene almeno un non terminale eβ ∈ (X ∪ V )∗ (puó essere anche λ)
La notazione α −→ β1 | β2 | . . . | βn riassume le produzioni:
α −→ β1α −→ β2
...α −→ βn
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Derivazioni
Data la grammatica G = (X ,V , S ,P) e due stringhe y e z suX ∪ V tali che y = γαδ ∈ (X ∪ V )+ e z = γβδ ∈ (X ∪ V )∗
con α, β, γ, δ ∈ (X ∪ V )∗, y deriva direttamente zsse a −→ β ∈ P . Ció è denotato con y =⇒ z
y deriva z , denotato con y ∗=⇒ z , sse
y = z oppure∃w1 = y ,w2, . . . ,wn−1 ∈ (X ∪ V )+ e wn = z ∈ (X ∪ V )∗ taliche: wi =⇒ wi+1 ∀i = 1, . . . , n − 1
n=⇒ denota una derivazione in n passi(n lunghezza della derivazione)Dato un ordinamento su P , =⇒i denota una derivazionediretta usando la produzione i-esima
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Linguaggio Generato da una Grammatica
Data la grammatica G = (X ,V , S ,P), il linguaggiogenerato dalla grammatica G , denotato con L(G ) èl’insieme delle stringhe di simboli terminali derivabili da S :
L(G ) = {w ∈ X ∗|S ∗=⇒ w}
w ∈ (X ∪ V )∗ è una forma di frase di G sse: S ∗=⇒ w
Alle forme di frase si applicano gli stessi operatori usati fin quiper le stringhe.Due grammatiche G e G ′ sono equivalenti sse L(G ) = L(G ′)
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Esempio
Data la grammatica G = (X ,V , S ,P),dove X = {a, b} V = {S} P = {S → aSb, S → ab}
Determiniamo L(G )
−−−−−−−−−−−−−−−−−−−
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Esempio
la stringa ab ∈ L(G ) (dato che esiste la produzione S → ab(S ⇒ ab) )la stringa a2b2 ∈ L(G ) (poichè S ⇒1 aSb ⇒2 aabb = a2b2)la stringa a3b3 ∈ L(G ) (poichèS ⇒1 aSb ⇒1 aaSbb ⇒2 aaSbb = a3b3)...
{anbn|n > 0} ⊆ L(G )Inoltre tutte le stringhe generate da S in G sono del tipo anbn,ovveroL(G ) ⊆ {anbn|n > 0}
⇓L(G ) = {anbn|n > 0}
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
DefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica
Correttezza di una grammatica
In generale, dati un linguaggio L ed una grammatica G , non esisteun algoritmo in grado di dimostrare che L = L(G ):
Teorema. Il problema generale di dimostrare la correttezza di unagrammatica è irresolubile per via algoritmica
In molti casi specifici, questo si puó dimostrare per induzioneL ⊆ L(G ), i.e. G genera solo stringhe di LL(G ) ⊆ L, i.e. L contiene solo stringhe generabili da G
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Esercizi
1 Determinare la grammatica che genera il linguaggioL = {anbn|n > 0}.
2 Determinare la grammatica che genera il linguaggioL = {anbn+1|n > 0}.
3 Data la grammatica G = (X ,V , S ,P)con X = {0, 1}, V = {S ,A,B} eP = {S → 0B | 1A, A→ 0 | 0S | 1AA, B → 1 | 1S | 0BB}determinare il linguaggio L(G ).
4 Determinare la grammatica che genera il linguaggioL = {anb2n | n > 0}.
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Esercizi
1 Determinare la grammatica che genera il linguaggioL = {akbnc2k | n, k > 0}.
2 Dimostrare induttivamente che è vuoto il linguaggio L(G )generato dalla grammaticaG = (X ,V , S ,P), con X = {a, b, c}, V = {S ,A,B}P = {S → aBS | bA, aB → Ac | a, bA→ S | Ba}
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Esercizio 1
Esercizio 1. Determinare la grammatica per L = {anbn | n > 0}
——————-
G = ({a, b}, {S}, {S 1−→ aSb, S 2−→ ab})Occorre dimostrare: L ⊆ L(G ) and L(G ) ⊆ L
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L(G ) ⊆ L
Sia w ∈ {a, b}∗ tale che: S ∗=⇒ w
Per induzione sulla lunghezza n della derivazione di w da S .
base n = 1 S ∗=⇒ ab e ab ∈ L
passo Dimostriamo che:
∀n > 1SE (w ′ ∈ L(G ) ∧ S n−1
=⇒ w ′) implica w ′ ∈ LALLORA da (w ∈ L(G ) ∧ S n
=⇒ w) consegue w ∈ L
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L(G ) ⊆ L
Sia w ∈ L(G ) e S n=⇒ w , cioè:
∃w1,w2, . . . ,wl : S =⇒ w1 =⇒ w2 =⇒ · · · =⇒ wn = w
Necessariamente: w1 = aSb n−1=⇒ wn = w
Per ipotesi di induzione:É vero che ∀n (w ′ ∈ L(G ) ∧ S n−1
=⇒ w ′) implica w ′ ∈ L.Dunque S n−1
=⇒ w ′ = akbk con k > 0.
ma S k=⇒ w ′ = akSbk con k > 0
Dunque w ′ = an−1bn−1
allora la stringa:aw ′b = aan−1bn−1b=anbn
é ancora una stringa di L ed é inoltre derivabile da S in n passiinfatti:S 1
=⇒ aSb n−1=⇒ aw ′b = anbn = w
C .V .D L(G ) ⊆ L1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L ⊆ L(G )
Sia w ∈ LPer induzione sulla lunghezza |w | della parola w ∈ Lbase |w | = 2
∃ S =⇒ ab = w e w ∈ Loss: |W | minima è 2 perché devo applicare almeno una regola di
derivazione.
passo Dimostriamo che:
∀nSE w ′ ∈ L, |w ′| = 2(n − 1) implica S ∗
=⇒ w ′
ALLORA w ∈ L, |w | = 2n implica S ∗=⇒ w .
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L ⊆ L(G )
Sia w ∈ L, |w | = 2n, n > 1:l’unica parola di L di tale lunghezza è w = anbn
Nella derivazione dovremo necessariamente applicare laproduzione (1) come primo passo: S =⇒1 aSbPer ipotesi di induzione:É vero che ∀w ′ ∈ L, |w ′| = 2(n − 1) : S ∗
=⇒ w ′
Quindi anche S ∗=⇒ an−1bn−1 = w ′
Unendo i due risultati si ottiene:S =⇒1 aSb ∗
=⇒ aw ′b = aan−1bn−1b = anbn = w
C .V .D. L ⊆ L(G )
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Esercizio 2
Determinare la grammatica per L = {anbn+1 | n > 0}
——————-
G = ({a, b}, {S ,A}, {S 1−→ Ab,A 2−→ aAb, A 3−→ ab})Occorre dimostrare: L ⊆ L(G ) and L(G ) ⊆ L... la dimostrazione del tutto uguale alla precedente è lasciata comeesercizio.
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
Esercizio 2, seconda pagina
Dimostrare induttivamente che è vuoto il linguaggio L(G ) generatodalla grammaticaG = (X ,V , S ,P), con X = {a, b, c}, V = {S ,A,B}P = {S → aBS | bA, aB → Ac | a, bA→ S | Ba}
——————-
Dovremmo provare che:L(G ) ⊆ ∅∅ ⊆ L(G )
Ovviamente è sufficiente provare che L(G ) ⊆ ∅.
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L(G ) ⊆ ∅
Sia w ∈ L(G ).se ∀n S n
=⇒ w allora w = αNβ, conα, β ∈ (X ∪ V )∗ e N ∈ V
Per induzione sulla lunghezza n della derivazionebase n = 1
le uniche derivazioni possibili sono:a. S =⇒ aBSb. S =⇒ bA
entrambe presentano almeno un non terminale
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L(G ) ⊆ ∅: cenni
passo Dimostriamo che:∀n > 1
SE S n−1=⇒ w ′ implica ∃N ∈ V : w ′ = yNz , con y , z ∈ (V ∪ X )∗
ALLORA S n=⇒ w ′ implica ∃N ∈ V : w ′ = yNz , con y , z ∈ (V ∪ X )∗
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)
Definizioni PreliminariGrammatiche Generative
Esercizi
L(G ) ⊆ ∅: cenni
Consideriamo una qualunque derivazione in G di n passi:S n
=⇒ wPer definizione: ∃w1, ..,wn = w tali che:S n−1
=⇒ wn−1 =⇒ wn = wPer ipotesi di induzione: ogni stringa derivabile da S in n − 1passi presenta un non terminale Dunque anche wn−1 presentaun non terminale.Si hanno le seguenti possibilità:
in wn−1 compare il non terminale S :allora....in wn−1 compare il non terminale A:allora.....in wn−1 compare il non terminale B:allora.....
1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)