1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio) · DeﬁnizioniPreliminari...

Definizioni PreliminariGrammatiche Generative

Esercizi

1. Introduzione ai Linguaggi Formali(Fanizzi - Carofiglio)

17 marzo 2016

1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio)


Esercizi

1 Definizioni PreliminariAlfabeti e StringhePotenze e ChiusureLinguaggi

2 Grammatiche GenerativeDefinizioneDerivazioniLinguaggio Generato da una GrammaticaCorrettezza di una Grammatica

3 Esercizi



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 ∗



Esercizi


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



Esercizi


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 δ



Esercizi


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



Esercizi


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



Esercizi


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



Esercizi


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



Esercizi


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



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



Esercizi


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



Esercizi


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 ′)



Esercizi


Esempio

Data la grammatica G = (X ,V , S ,P),dove X = {a, b} V = {S} P = {S → aSb, S → ab}

Determiniamo L(G )

−−−−−−−−−−−−−−−−−−−



Esercizi


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}



Esercizi


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



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}.



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}



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



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



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)


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 .



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 )



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.



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 ) ⊆ ∅.



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



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 )∗



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) · DeﬁnizioniPreliminari...

Documents

Transcript of 1. Introduzione ai Linguaggi Formali (Fanizzi - Carofiglio) · DeﬁnizioniPreliminari...