Grammatiche, Linguaggio e Automi
R. Basili
TAL - a.a. 2009-2010
Sommario




Grammatiche: definizione di base
La gerarchia di Chomsky
Grammatiche e Lingue Naturali
Cenni alla Teoria degli Automi
Motivazioni
 Un sistema di riconoscimento della sintassi di una
lingua deve esibire proprietà:
– Descrittive. Deve cioè spiegare la motivazioni alla base
della accettabilità grammaticale degli enunciati di una
lingua in termini di
 Proprietà lessicali delle classi di oggetti elementari della lingua
 Proprietà strutturali degli enunciati
– Procedurali: Deve fornire meccanismi computazionali in
grado di
 Riconoscere la accettabilità grammaticale
 Costruire le strutture grammaticali che soggiacciono ai singoli
enunciati accettabili
Grammatiche Formali
 Un linguaggio L e’ caratterizzato da un insieme di
stringhe, cioe’ sequenze finite di elementi di un
vocabolario di partenza A
 “…I will consider a language to be a set (finite or
infinite) of sentences, each finite in length and
constructed out of a finite set of elements… All
natural languages are languages in this sense…
Similarly, the set of “sentences” of some
formalized system of mathematics can be
considered a language” Chomsky 1957
Grammatiche Formali (2)
 Dato un vocabolario A, l’insieme di tutte le stringhe
costruite su A (A*) più l’operazione di
concatenazione (formazione di stringhe
complesse a partire da stringhe semplici)
costituisce una struttura algebrica definita come
monoide libero su A.
 Normalmente, non tutte le stringhe del monoide
costituiscono frasi ben formate di L: per es, dato
un frammento del lessico italiano, non tutte le
sequenze arbitrarie sono frasi dell’italiano:
– Il bambino corre
– *il corre bambino
Corre il bambino
* bambino corre il …..
Grammatiche Formali (3)
 Quindi L con vocabolario A è in genere un
sottoinsieme proprio di A*, i.e. L  A*
 IL compito della grammatica di L è di catturare il
sottoinsieme in questione generando tutte e sole
le stringhe che lo compongono (capacità
generativa debole) e di esprimere la struttura delle
frasi di L (capacità generativa forte).
– [il bambino] [legge [il libro ]] e non
– * [[[[il] bambino] legge] il] libro]
Grammatiche Formali (4)
 Per lo studio delle proprietà formali, è utile
considerare linguaggi semplificati, con lessici
molto ridotti e sintassi semplice, per es, linguaggi
come i seguenti:
–
–
–
–
–
–
ab, abab, ababab, abababab,…
ab, aab, aabbbb, aaaaabb,...
ab, aabb, aaabbb, aaaabbbb...
aa, bb, abba, baab, abaaba, aaabbaaa, ...
a, abab, abbabb, abbababbab,...
abc, aabbcc, aaabbbccc, aaaabbbbcccc
Grammatiche Formali (5)
 Una grammatica formale è un sistema
deduttivo di assiomi e regole di inferenza,
che genera le frasi della lingua come suoi
teoremi (capacità generativa debole).
Inoltre, assegna rappresentazioni strutturali
alle frasi (capacità generativa forte).
Grammatiche Formali (6)
 Una grammatica formale è definita da una
quadrupla :
–
–
–
–
(i) Un vocabolario terminale VT
(ii) Un vocabolario non terminale VN
(iii) Un assioma, o simbolo iniziale SVN
(iv) Un insieme di regole di riscrittura   
 Nella sua forma più generale, la parte sinistra e la
parte destra della regola di riscrittura sono
stringhe qualsiasi costruite sui due vocabolari, con
la sola restrizione che la parte sinistra deve
contenere almeno un simbolo di VN .
Derivazione da una GF
 Una derivazione è una sequenza di stringhe che
parte dall’assioma S e arriva fino a generare una
stringa w1, …, wN del linguaggio tramite le regole,
eliminando via via i simboli non terminali.
 Modalità top-down: parte da S e cerca tutte le
sostituzioni sufficienti a generare w1, …, wN
 Modalità bottom-up: parte da w1, …, wN e ne
riscrive i frammenti usando le regole sino a
riscrivere l’assioma S
Esempio:




G=< VT , VN , S, R>
VT : {a, b}, VN : {S, A, B}
Assioma: S
Regole:
S → A B S S → ε AB → BA
BA → AB
A→a B→b
 Esempio di derivazione:
S >ABS >BAS >BAABS >BAAB >bAAB >baAB >baaB>baab
 “ε” è la stringa vuota, l’elementi neutro rispetto alla
concatenazione:
ε=ε=
Alberi
 La rappresentazione del risultato del parsing
e’ una struttura che deve esprimere
– L’ordine degli elementi costituenti una
espressione
– Il tipo grammaticale dei costituenti
– L’organizzazione gerarchica dei costituenti
 Le strutture dati che garantiscono tali
proprietà sono detti alberi
Alberi (2)
 Gli alberi sono strutture dati definite da una
5-pla <N,Q,D,P,L> dove
– N e’ un insieme finito di nodi
– Q e’ un insieme finito di etichette (label)
– D e’ una relazione d’ordine parziale debole in
NN detta relazione di dominanza
– P e’ una relazione d’ordine parziale stretta in N
 N, detta precedenza
– L e’ la funzione di etichettatura da N a Q
Alberi (3) esempio
“Il gatto beve il latte”
 N={1,2,3,4,5,6,7,8,9,10,11,12,13,14}
 Q={S,NP,VP,Det,N,V}
 D={<1,3>,<1,2>,<2,4>, <2,5>, <3,7>, <3,6>,
<7,8>, <7,9>, …}
 L={<1,S>, <3,VP>, …, <6,NP>, <8,Det>, …}
1 S
NP 2
Det 4
N 5
3 VP
7 NP
V 6
Det 8
Il10 gatto11
9 N
beve12 il13 latte14
Grammatiche ed Alberi
“Il gatto beve il latte”
 Vn={S,NP,VP,Det,N}, Assioma: S
 Produzioni: {S→NP VP, VP→V NP, NP→Det N}
 Derivazioni
 S > NP VP > Det N VP > Il N VP > Il gatto VP > Il
gatto V NP > Il gatto beve NP > Il gatto beve Det N
> Il gatto beve il N > Il gatto beve il latte
1 S
NP 2
Det 4
N 5
3 VP
7 NP
V 6
Det 8
Il10 gatto11
9 N
beve12 il13 latte14
Grammatiche ed Alberi
“Il gatto beve il latte”
 Vn={S,NP,VP,Det,N}, Assioma: S
 Produzioni: {S→NP VP, VP→V NP, NP→Det N}
 Derivazioni
 S > NP VP > Det N VP > Il N VP > Il gatto VP > Il
gatto V NP > Il gatto beve NP > Il gatto beve Det N
> Il gatto beve il N > Il gatto beve il latte
1 S
NP 2
derivazione
top-down
Det 4
N 5
3 VP
7 NP
V 6
Det 8
Il10 gatto11
9 N
beve12 il13 latte14
Grammatiche ed Alberi
“Il gatto beve il latte”
 VN={S,NP,VP,Det,N}, Assioma: S
 Produzioni: {S→NP VP, VP→V NP, NP→Det N}
 Derivazioni
 Il gatto beve il latte > Det beve il latte > Det N beve
il latte > NP beve il latte > NP V il latte > NP V Det
latte > NP V Det N > NP V NP > NP VP > S
1 S
NP 2
derivazione
bottom-up
Det 4
N 5
3 VP
7 NP
V 6
Det 8
Il10 gatto11
9 N
beve12 il13 latte14
Esercizi
 Date le seguenti frasi scrivere una
grammatica che le rappresenta e descrivere
almeno in due casi l’albero sintattico di
derivazione.
– Mario mangia
– Giovanni scrisse un poema
– Il libro fu scritto da due autori
– Le prime sezioni erano noiose
Esercizi (2)
 Estendere la grammatica precedente alle
seguenti frasi
– Mario mangia di notte
– Giovanna di notte scrisse il primo capitolo del
libro
– Le ore insonni scorrevano attraverso la notte a
Roma
 Descrivere gli alberi sintattici generati dalla
grammatica sulle tre frasi.
Esercizi (3)
 Quanti non terminali (categorie
grammaticali) sono necessarie?
 Quante frasi generano interpretazioni
grammaticali multiple?
 Quali informazioni semantiche sono
necessarie per la disambiguazione?
 Descriverne alcune in forma testuale.
Riferimenti Bibliografici
 Lyons, Introduzione alla Linguistica Teorica,
II. Grammatica,
– Capitoli 4.1, 4.2, 4.3, 6.1, 6.2, 8.1