Grammatiche, Linguaggio e Automi

Grammatiche, Linguaggio e AutomiGrammatiche, Linguaggio e Automi

R. BasiliR. BasiliTAL - a.a. 2009-2010TAL - a.a. 2009-2010

SommarioSommario

Grammatiche: definizione di baseGrammatiche: definizione di base La gerarchia di ChomskyLa gerarchia di Chomsky Grammatiche e Lingue NaturaliGrammatiche e Lingue Naturali Cenni alla Teoria degli AutomiCenni alla Teoria degli Automi

MotivazioniMotivazioni

Un sistema di riconoscimento della sintassi di una Un sistema di riconoscimento della sintassi di una lingua deve esibire proprietà:lingua deve esibire proprietà:– Descrittive. Deve cioè spiegare la motivazioni alla base Descrittive. Deve cioè spiegare la motivazioni alla base

della accettabilità grammaticale degli enunciati di una della accettabilità grammaticale degli enunciati di una lingua in termini di lingua in termini di Proprietà lessicali delle classi di oggetti elementari della linguaProprietà lessicali delle classi di oggetti elementari della lingua Proprietà strutturali degli enunciati Proprietà strutturali degli enunciati

– Procedurali: Deve fornire meccanismi computazionali in Procedurali: Deve fornire meccanismi computazionali in grado di grado di Riconoscere la accettabilità grammaticale Riconoscere la accettabilità grammaticale Costruire le strutture grammaticali che soggiacciono ai singoli Costruire le strutture grammaticali che soggiacciono ai singoli

enunciati accettabilienunciati accettabili

Grammatiche FormaliGrammatiche Formali

Un linguaggio L e’ caratterizzato da un insieme di Un linguaggio L e’ caratterizzato da un insieme di stringhe, cioe’ sequenze finite di elementi di un stringhe, cioe’ sequenze finite di elementi di un vocabolario di partenza Avocabolario di partenza A

“…“…I will consider a language to be a set (finite or I will consider a language to be a set (finite or infinite) of sentences, each finite in length and infinite) of sentences, each finite in length and constructed out of a finite set of elements… All constructed out of a finite set of elements… All natural languages are languages in this sense… natural languages are languages in this sense… Similarly, the set of “sentences” of some Similarly, the set of “sentences” of some formalized system of mathematics can be formalized system of mathematics can be considered a language” Chomsky 1957 considered a language” Chomsky 1957

Grammatiche Formali (2)Grammatiche Formali (2)

Dato un vocabolario A, l’insieme di tutte le stringhe Dato un vocabolario A, l’insieme di tutte le stringhe costruite su A (A*) più l’operazione di costruite su A (A*) più l’operazione di concatenazione (formazione di stringhe complesse a concatenazione (formazione di stringhe complesse a partire da stringhe semplici) costituisce una struttura partire da stringhe semplici) costituisce una struttura algebrica definita come monoide libero su A. algebrica definita come monoide libero su A.

Normalmente, non tutte le stringhe del monoide Normalmente, non tutte le stringhe del monoide costituiscono frasi ben formate di L: per es, dato un costituiscono frasi ben formate di L: per es, dato un frammento del lessico italiano, non tutte le sequenze frammento del lessico italiano, non tutte le sequenze arbitrarie sono frasi dell’italiano: arbitrarie sono frasi dell’italiano: – Il bambino corre Il bambino corre Corre il bambino Corre il bambino – *il corre bambino *il corre bambino * bambino corre il ….. * bambino corre il …..

Dato un vocabolario A, l’insieme di tutte le stringhe Dato un vocabolario A, l’insieme di tutte le stringhe costruite su A (A*) più l’operazione di costruite su A (A*) più l’operazione di concatenazione (formazione di stringhe complesse a concatenazione (formazione di stringhe complesse a partire da stringhe semplici) costituisce una struttura partire da stringhe semplici) costituisce una struttura algebrica definita come monoide libero su A. algebrica definita come monoide libero su A.

Normalmente, non tutte le stringhe del monoide Normalmente, non tutte le stringhe del monoide costituiscono frasi ben formate di L: per es, dato un costituiscono frasi ben formate di L: per es, dato un frammento del lessico italiano, non tutte le sequenze frammento del lessico italiano, non tutte le sequenze arbitrarie sono frasi dell’italiano: arbitrarie sono frasi dell’italiano: – Il bambino corre Il bambino corre Corre il bambino Corre il bambino – *il corre bambino *il corre bambino * bambino corre il ….. * bambino corre il …..


Quindi L con vocabolario A è in genere un Quindi L con vocabolario A è in genere un sottoinsieme proprio di A*, i.e. L sottoinsieme proprio di A*, i.e. L A* A*

IL compito della grammatica di L è di catturare il IL compito della grammatica di L è di catturare il sottoinsieme in questione generando tutte e sole sottoinsieme in questione generando tutte e sole le stringhe che lo compongono (capacità le stringhe che lo compongono (capacità generativa debole) e di esprimere la struttura delle generativa debole) e di esprimere la struttura delle frasi di L (capacità generativa forte). frasi di L (capacità generativa forte). – [il bambino] [legge [il libro ]] e non [il bambino] [legge [il libro ]] e non – * [[[[il] bambino] legge] il] libro] * [[[[il] bambino] legge] il] libro]

Quindi L con vocabolario A è in genere un Quindi L con vocabolario A è in genere un sottoinsieme proprio di A*, i.e. L sottoinsieme proprio di A*, i.e. L A* A*

IL compito della grammatica di L è di catturare il IL compito della grammatica di L è di catturare il sottoinsieme in questione generando tutte e sole sottoinsieme in questione generando tutte e sole le stringhe che lo compongono (capacità le stringhe che lo compongono (capacità generativa debole) e di esprimere la struttura delle generativa debole) e di esprimere la struttura delle frasi di L (capacità generativa forte). frasi di L (capacità generativa forte). – [il bambino] [legge [il libro ]] e non [il bambino] [legge [il libro ]] e non – * [[[[il] bambino] legge] il] libro] * [[[[il] bambino] legge] il] libro]


Per lo studio delle proprietà formali, è utile Per lo studio delle proprietà formali, è utile considerare linguaggi semplificati, con lessici considerare linguaggi semplificati, con lessici molto ridotti e sintassi semplice, per es, linguaggi molto ridotti e sintassi semplice, per es, linguaggi come i seguenti: come i seguenti: – ab, abab, ababab, abababab,… ab, abab, ababab, abababab,… – ab, aab, aabbbb, aaaaabb,... ab, aab, aabbbb, aaaaabb,... – ab, aabb, aaabbb, aaaabbbb... ab, aabb, aaabbb, aaaabbbb... – aa, bb, abba, baab, abaaba, aaabbaaa, ... aa, bb, abba, baab, abaaba, aaabbaaa, ... – a, abab, abbabb, abbababbab,... a, abab, abbabb, abbababbab,... – abc, aabbcc, aaabbbccc, aaaabbbbccccabc, aabbcc, aaabbbccc, aaaabbbbcccc

Grammatiche FormaliGrammatiche Formali (5) (5)

Una grammatica formale è un sistema Una grammatica formale è un sistema deduttivo di assiomi e regole di inferenza, deduttivo di assiomi e regole di inferenza, che genera le frasi della lingua come suoi che genera le frasi della lingua come suoi teoremi (capacità generativa debole). teoremi (capacità generativa debole). Inoltre, assegna rappresentazioni strutturali Inoltre, assegna rappresentazioni strutturali alle frasi (capacità generativa forte). alle frasi (capacità generativa forte).

Grammatiche Formali (6)Grammatiche Formali (6) Una grammatica formale è definita da una quadrupla : Una grammatica formale è definita da una quadrupla :

– (i) Un vocabolario terminale V(i) Un vocabolario terminale VTT – (ii) Un vocabolario non terminale V(ii) Un vocabolario non terminale VNN – (iii) Un assioma, o simbolo iniziale S(iii) Un assioma, o simbolo iniziale SVVNN – (iv) Un insieme di regole di riscrittura (iv) Un insieme di regole di riscrittura

Nella sua forma più generale, la parte sinistra e la Nella sua forma più generale, la parte sinistra e la parte destra della regola di riscrittura sono stringhe parte destra della regola di riscrittura sono stringhe qualsiasi costruite sui due vocabolari, con la sola qualsiasi costruite sui due vocabolari, con la sola restrizione che la parte sinistra deve contenere almeno restrizione che la parte sinistra deve contenere almeno un simbolo di Vun simbolo di VN N . .

Derivazione da una GFDerivazione da una GF

Una derivazione è una sequenza di stringhe che Una derivazione è una sequenza di stringhe che parte dall’assioma S e arriva fino a generare una parte dall’assioma S e arriva fino a generare una stringa stringa ww11, …, w, …, wNN del linguaggio tramite le regole, del linguaggio tramite le regole,

eliminando via via i simboli non terminali. eliminando via via i simboli non terminali. Modalità Modalità top-downtop-down: parte da S e cerca tutte le : parte da S e cerca tutte le

sostituzioni sufficienti a generare sostituzioni sufficienti a generare ww11, …, w, …, wNN

Modalità Modalità bottom-upbottom-up: parte da : parte da ww11, …, w, …, wNN e ne e ne

riscrive i frammenti usando le regole sino a riscrive i frammenti usando le regole sino a riscrivere l’assioma Sriscrivere l’assioma S

Esempio:Esempio: G=< VG=< VTT , V , VNN , S, R> , S, R> VVT T : {a, b}, V: {a, b}, VN N : {S, A, B} Assioma: S : {S, A, B} Assioma: S Regole: Regole: S → A B S S → S → A B S S → εε AB → BA BA → AB A → a AB → BA BA → AB A → a

B → b B → b

Esempio di derivazione: Esempio di derivazione: S >ABS >BAS >BAABS >BAAB >bAAB >baAB >baaB>baab S >ABS >BAS >BAABS >BAAB >bAAB >baAB >baaB>baab

““ε” è la stringa vuota, l’elementi neutro rispetto alla ε” è la stringa vuota, l’elementi neutro rispetto alla concatenazione: concatenazione: ε ε = = ε = ε =

Alberi Alberi

La rappresentazione del risultato del La rappresentazione del risultato del parsingparsing e’ una struttura che deve esprimeree’ una struttura che deve esprimere– L’ordine degli elementi costituenti una L’ordine degli elementi costituenti una

espressioneespressione– Il tipo grammaticale dei costituentiIl tipo grammaticale dei costituenti– L’organizzazione gerarchica dei costituentiL’organizzazione gerarchica dei costituenti

Le strutture dati che garantiscono tali Le strutture dati che garantiscono tali proprietà sono detti alberiproprietà sono detti alberi

Alberi (2)Alberi (2)

Gli alberi sono strutture dati definite da una Gli alberi sono strutture dati definite da una 5-pla <N,Q,D,P,L> dove5-pla <N,Q,D,P,L> dove– N e’ un insieme finito di nodiN e’ un insieme finito di nodi– Q e’ un insieme finito di etichette (Q e’ un insieme finito di etichette ( labellabel))– D e’ una relazione d’ordine parziale debole in D e’ una relazione d’ordine parziale debole in

NNN detta relazione di N detta relazione di dominanzadominanza– P e’ una relazione d’ordine parziale stretta in N P e’ una relazione d’ordine parziale stretta in N

N, detta N, detta precedenzaprecedenza– L e’ la funzione di etichettatura da N a QL e’ la funzione di etichettatura da N a Q

Alberi (3) esempioAlberi (3) esempio““Il gatto beve il latteIl gatto beve il latte”” N={1,2,3,4,5,6,7,8,9,10,11,12,13,14}N={1,2,3,4,5,6,7,8,9,10,11,12,13,14} Q={S,NP,VP,Det,N,V}Q={S,NP,VP,Det,N,V} D={<1,3>,<1,2>,<2,4>, <2,5>, <3,7>, <3,6>, D={<1,3>,<1,2>,<2,4>, <2,5>, <3,7>, <3,6>,

<7,8>, <7,9>, …}<7,8>, <7,9>, …} L={<1,S>, <3,VP>, …, <6,NP>, <8,Det>, …}L={<1,S>, <3,VP>, …, <6,NP>, <8,Det>, …}

3

1

2

4 5 6 7

8 9

IlIl1010 gatto gatto1111 beve beve1212 il il1313 latte latte1414

SS

VPVPNPNP

DetDet NN VV

DetDet NN

NPNP

Grammatiche ed AlberiGrammatiche ed Alberi““Il gatto beve il latteIl gatto beve il latte”” Vn={S,NP,VP,Det,N}, Assioma: SVn={S,NP,VP,Det,N}, Assioma: S Produzioni: {SProduzioni: {S→→NP VP, VPNP VP, VP→→V NP, NPV NP, NP→→Det N}Det N} DerivazioniDerivazioni S > NP VP > Det N VP > S > NP VP > Det N VP > IlIl N VP > N VP > Il gattoIl gatto VP > VP > Il Il

gattogatto V NP > V NP > Il gatto beveIl gatto beve NP > NP > Il gatto beveIl gatto beve Det N Det N > > Il gatto beve ilIl gatto beve il N > N > Il gatto beve il latteIl gatto beve il latte

3

1

2

4 5 6 7

8 9


SS

VPVPNPNP

DetDet NN VV

DetDet NN

NPNP

Grammatiche ed AlberiGrammatiche ed Alberi““Il gatto beve il latteIl gatto beve il latte”” Vn={S,NP,VP,Det,N}, Assioma: SVn={S,NP,VP,Det,N}, Assioma: S Produzioni: {SProduzioni: {S→→NP VP, VPNP VP, VP→→V NP, NPV NP, NP→→Det N}Det N} DerivazioniDerivazioni S > NP VP > Det N VP > S > NP VP > Det N VP > IlIl N VP > N VP > Il gattoIl gatto VP > VP > Il Il

gattogatto V NP > V NP > Il gatto beveIl gatto beve NP > NP > Il gatto beveIl gatto beve Det N Det N > > Il gatto beve ilIl gatto beve il N > N > Il gatto beve il latteIl gatto beve il latte


1 SS

32 VPVPNPNP

6 7VV NPNP

8DetDet 9 NN

4 5DetDet NNderivazionederivazionetop-downtop-down

Grammatiche ed AlberiGrammatiche ed Alberi““Il gatto beve il latteIl gatto beve il latte”” VVNN={S,NP,VP,Det,N}, Assioma: S={S,NP,VP,Det,N}, Assioma: S

Produzioni: {SProduzioni: {S→→NP VP, VPNP VP, VP→→V NP, NPV NP, NP→→Det N}Det N} DerivazioniDerivazioni Il gatto beve il latteIl gatto beve il latte > Det > Det beve il lattebeve il latte > Det N > Det N

beve il lattebeve il latte > NP > NP beve il lattebeve il latte > NP V > NP V il latteil latte > NP > NP V Det V Det lattelatte > NP V Det N > NP V NP > NP VP > S > NP V Det N > NP V NP > NP VP > S


1 SS

3 VPVP

6VV 7 NPNP

8DetDet 9 NN

4DetDet 5NN

2NPNP

derivazionederivazionebottom-upbottom-up

EserciziEsercizi

Date le seguenti frasi scrivere una Date le seguenti frasi scrivere una grammatica che le rappresenta e descrivere grammatica che le rappresenta e descrivere almeno in due casi l’albero sintattico di almeno in due casi l’albero sintattico di derivazione.derivazione.– Mario mangiaMario mangia– Giovanni scrisse un poemaGiovanni scrisse un poema– Il libro fu scritto da due autoriIl libro fu scritto da due autori– Le prime sezioni erano noioseLe prime sezioni erano noiose

Esercizi (2)Esercizi (2)

Estendere la grammatica precedente alle Estendere la grammatica precedente alle seguenti frasiseguenti frasi– Mario mangia di notteMario mangia di notte– Giovanna di notte scrisse il primo capitolo del Giovanna di notte scrisse il primo capitolo del

librolibro– Le ore insonni scorrevano attraverso la notte a Le ore insonni scorrevano attraverso la notte a

RomaRoma Descrivere gli alberi sintattici generati dalla Descrivere gli alberi sintattici generati dalla

grammatica sulle tre frasi.grammatica sulle tre frasi.

Esercizi (3)Esercizi (3)

Quanti non terminali (categorie Quanti non terminali (categorie grammaticali) sono necessarie?grammaticali) sono necessarie?

Quante frasi generano interpretazioni Quante frasi generano interpretazioni grammaticali multiple? grammaticali multiple?

Quali informazioni semantiche sono Quali informazioni semantiche sono necessarie per la disambiguazione?necessarie per la disambiguazione?

Descriverne alcune in forma testuale.Descriverne alcune in forma testuale.

Riferimenti BibliograficiRiferimenti Bibliografici

Lyons, Introduzione alla Linguistica Teorica, Lyons, Introduzione alla Linguistica Teorica, II. Grammatica, II. Grammatica, – Capitoli 4.1, 4.2, 4.3, 6.1, 6.2, 8.1Capitoli 4.1, 4.2, 4.3, 6.1, 6.2, 8.1

Grammatiche, Linguaggio e Automi

Documents

Transcript of Grammatiche, Linguaggio e Automi