1
SISTEMI FORMALI e
GRAMMATICHE
( parte 1 - sistemi formali )
2
per capire un'po'le grammatiche dei linguaggi di
programmazione e
per avere un'idea del procedimento di traduzione
eseguito da un compilatore C++, Java, Fortran..
presentiamo di alcune nozioni preliminari
*
*
*
*
*
*
sistemi formali
linguaggi
grammatiche generative
classificazione dei linguaggi alla Chomsky
grammatiche BNF e EBNF
riconoscimento di strutture grammaticali
sistemi formali
- definizioni: alfabeto
Da un punto di vista formale un linguaggio (ad es di
programmazione) e' un sistema formale basato su :
un alfabeto (un insieme di simboli base predefiniti)
con tale alfabeto si possono formare delle stringhe di
caratteri,. ad es.: alfabeto 0,1
stringhe: 0, 1010, 11110011110101, ...
ma: non tutte le stringhe appartengono al linguaggio!
un insieme di regole per stabilire se una stringa
appartiene al linguaggio e/o per costruire stringhe del
linguaggio.
vediamo prima delle definizioni ...
3
sistemi formali - definizioni : alfabeto, stringa
Definizioni
ALFABETO - INSIEME FINITO DI SIMBOLI DISTINTI
tre es.
A1 = { a, b, c }
A2 = { (, ) },
A3 = { 0, 1, 2, 3, 4, 5, 6, 7 }
dove { a, b, c } sta per "insieme di tre elementi a, b, c"
ecc.
si definisce:
STRINGA su A=
sequenza finita (event. vuota)
di simboli di A,
es. di stringhe su A1: a, caaaaab, babcab, aabcbaa, ...
su A2: ))), )(, ), ()()((())), (()), ...
su A3: 0, 42, 313, 1775, 65432107654,
4
sistemi formali - definizioni: lunghezza di stringa
abbiamo visto che: alfabeto = insieme A di simboli,
si definisce stringa su A = sequenza finita (event.vuota) di
simboli di A,
si definisce LUNGHEZZA di una stringa s
il numero dei simboli di s e si indica con
|s| :
| s | = lunghezza della stringa s
es.:
| abba | = 4,
| 33 | = 2,
|micheze| = 7
se \ e' una stringa vuota di zero caratteri, allora | \ | = 0
5
sistemi formali - definizioni: A stellato
abbiamo visto che: un alfabeto = insieme A di simboli,
stringa su A = sequenza finita (event.vuota) di simboli di A,
lunghezza di una stringa = |s| = nr.o simboli di s
es.: |abba| = 4, |22| = 2, | \ | = 0
si definisce l’insieme “A stellato” A*
l'insieme di TUTTE le stringhe che si possono formare con i
caratteri (simboli) dell'alfabeto A:
A* = { s | s stringa su A, |s| >= 0 }
es. se l'alfabeto e'
A1= { a,b },
allora
A1* = { a, b, aa, ab, ba, bb, aaa, aab, aba, ...}
e' un insieme infinito !
6
sistemi formali - definizioni A2 e A3
abbiamo definito:
A = insieme finito di simboli distinti, ad es. { 0, 1 }
s = stringa di simboli di A
|s| = lunghezza della stringa s (numero simboli di s)
A* = insieme A stellato = insieme di tutte le stringhe s
che si possono formare con i simboli di A
altri esempi di alfabeti e di A* :
A2 = { (,) }, ancora un alfabeto di due simboli,
A2* = { (, ), ((, (), )), )(, (((, ((), (), ...))), ((((, ....}
A3 = { 0, 1, 2, 3, 4, 5, 6, 7 } alfabeto di 8 simboli, usato
per rappresentare i numeri in base otto (in ottale):
A3* = { 0, 1, 2, .., 10, 11,12,..100,101,102,... 313, ... 7, ...}
sono tutti i numeri in ottale ... quanti sono?
7
8
sistemi formali - esempi A4
seguono due esempi "limite":
4.o esempio:
A4, alfabeto vuoto: A4 = 0
[insieme vuoto] -
anche in tale caso A4* esiste ed ha un solo elemento,
A4* e' l'insieme formato da un solo elemento,
la stringa vuota \
( veramente, \ sta per lambda! ;-)
quindi: se l' alfabeto e' vuoto: A4 = 0
allora:
A4 * = 0* = { \ }
[insieme vuoto]
sistemi formali -
esempi A5
5. es. A5, alfabeto con un solo elemento, ad es.: un 1,
ovvero
A5 = { 1 }
allora A5* ha infiniti elementi del tipo 1, 11, 111, ...
(ricordi il sistema unario?)
A5* = { \, 1, 11, 111, 1111, ...} che possiamo scrivere:
A5* = { x | x = \ , x = 1 n }
(leggi: A stellato e' un insieme di x, dove x puo' essere la
stringa vuota oppure una stringa fatta di simboli 1 ripetuti,
dove 1n sta per stringa di simboli 1 ripetuti n volte )
9
sistemi formali - alcuni esempi A6
es.6)
10
alfabeto con due elementi: (ad es.:)
A6 = { 1,X }
A6* e' un insieme di infiniti elementi del tipo:
A6* = { \, 1, X, 11, 1X, X1, XX,
111, 11X, 1X1, 1XX, X11, X1X, XX1, XXX,
1111, 111X, 11X1, 11XX, ... XXXX,
11111, 1111X, .... XXXXX,
.... }
che possiamo scrivere:
= { s | s = \ oppure s = z n , con z = 1 oppure z = X }
dove z n sta per z ripetuto n volte (stringa di n caratteri)
sistemi formali -
alcuni esempi
A7
es.7) alfabeto A7 con n elementi, ad es. sei:
A7 = {a,b,c,d,e,f}
A7 * ha infiniti elementi, numerabili
A7 * = { \, (stringa vuota)
a, b, c, d, e, f, (stringhe di 1 carattere),
aa, ab, ac, ad, ae, ba, bc, bd, be, .. ff, (stringhe di 2 caratt)
aaa, ... fff, (str.di 3 caratteri) ecc ecc }
Si osservi che (come e' per ipotesi)
se A e' finito
allora A* e' numerabile:
basta ordinare le stringhe secondo un certo ordine - ad es
prima tutte le s con |s|=1, poi tutte le s con |s|=2, poi... :
a, b, c, d, e, f, aa, ab, ac, ad, ae, af, ba, bc, bf,.. ff, aaa, aab, ..
(ricorda la numerazione in base n, oppure l'ordine lessicogr.)
11
sistemi formali - definizioni: A+
ricorda: dato un alfabeto = insieme A di simboli,
s = stringa su A = sequenza finita (ev.vuota) di simboli di A,
defin. “A stellato” insieme A*= { s | s stringa su A, |s| >= 0 }
due nuove definizioni:
si definisce A+ = A* - { \ }
ovvero:
A+ { s | s stringa su A, |s| > 0 }
es.: dato l’alfabeto A8 = { 0,1,2,3,4,5,6,7,8,9 }
allora
A8 + = { 0, 1, 2, ..9, 10, 11, .. 99, 100, 101, .. 999, 1000, ... }
e’ l’insieme dei numeri interi non negativi.
12
13
sistemi formali - definizioni: concatenazione
definiamo ancora l'operazione di concatenazione:
date alcune stringhe su un alfabeto A
ad es. A9 = { a, b, c, d }
s1 = aa,
s2 = bbb,
s3 = c,
ottengo altre stringhe con la concatenazione:
s4 = s1 s2
= aabbb,
s5 = s1 s3 s2 = aacbbb
diremo per la stringa s5 definita come s5 = s1 s3 s2 che:
- s1 = prefisso,
- s2 = suffisso,
- s1, s2, s3 = sottostringhe di s5
sistemi formali - proprieta'della concatenazione
14
proprieta’ della concatenazione di stringhe s
dell’insieme w = A stellato = A*
a) w e’ chiuso rispetto la concatenazione ovvero:
se x,y appartengono a w allora
anche z = xy appartiene a w;
b) vale la proprieta’ associativa: x(yz)= (xy)z = xyz
c) esiste un elemento identita’, che e’ la stringa vuota \
tale che per qualunque x di w vale \ x = x \ = x
d) att: non e’ commutativa: [se A ha piu’ di un elem.]
esistono x, y tali che xy <> yx
e) per la lunghezza, per qualunque x,y di w vale |xy| = |x| + |y|
sistemi formali - definizioni
dagli esempi visti finora si vede che
se A e’ finito (come lo e' per ipotesi)
allora A* e’ numerabile
ovvero
si possono mettere in corrispondenza biunivoca
le stringhe di A*
ed i numeri naturali
e ... finalmente, arriviamo alla definizione seguente ...
15
sistemi formali e linguaggi / definizioni: linguaggio
definizione:
un LINGUAGGIO I e’ un SOTTOINSIEME di A*
I
c
A*
definizione: se s appartiene ad I allora diremo che
s e' una stringa ben formata, e viceversa:
I e' l' insieme delle s.b.f.
quindi nell'insieme A* introduco un criterio per cui
alcune stringhe di A sono "buone" o "ben formate" ,
altre non lo sono ...
16
sistemi formali e linguaggi / definizioni: linguaggio
definz: LINGUAGGIO I e’un SOTTOINSIEME di A
I c A* nel senso seguente:
definz: se s (stringa) appartiene ad I diremo che
s e' una stringa ben formata,
e viceversa:
I e' l' insieme delle s.b.f. (stringhe ben form.)
diremo (ma senza pretesa moralistica ;-)
alcune stringhe di A sono "buone" o "ben formate" ,
altre non lo sono:
introduco una "discriminazione" nella popolazione di
A*
ovvero una proprieta' che alcune stringhe di A* hanno e
altre no, da cui riconosco le stringhe ben formate !
17
sistemi formali e linguaggi / esempio:
abbiamo definito un LINGUAGGIO I come un
SOTTOINSIEME di A*
cioe'
I c A*
e abbiamo definito le stringhe ben formate:
se s appartiene ad I allora diremo che s e' ben formata,
e viceversa: I e' l' insieme delle s.b.f.
es: A10 = { a,b }, e A10 * = { \, a, b, aa, ab, ba, bb, aaa, ..}
definiamo il "linguaggio" Ip come
Ip = insieme delle stringhe “palindrome” di A10 *
ovvero delle stringhe simmetriche
(<== proprieta' delle s.b.f. !! )
per A10 = { a,b } le stringhe palindrome sono:
Ip = { a, aa, bb, aaa, aba, bab, bbb, aaaa, abba, baab, ...}
18
sistemi formali / 4 modi di definire un "linguaggio"
un LINGUAGGIO
SI PUO' DEFINIRE in vari modi:
a)
elenco completo
b)
in forma parametrica
c)
con un criterio di appartenenza
d)
con delle regole di produzione
(come vale in generale per qualunque insieme) ...
vediamo meglio...
19
sistemi formali / come definire I: a) elenco completo
a) elenco completo delle stringhe ben formate di I
questo modo di definire un linguaggio ...
e' applicabile solo per insiemi I finiti
ES.1)
se l'alfabeto e' A11 = {a, d,e,g,i,m,n,o,r }
allora l'insieme A11 stellato e':
A11 * = { a,d,e,g, .., r,aa,ad,ae,..ar,da,..ee, eg, ..., rr, aaa, ... }
e ad esempio posso definire
I1 = { ieri, oggi, domani }
e’ un sottoinsieme di A11 *
20
sistemi formali / come definire I:
a) linguaggio dato con un elenco completo delle stringhe
ben formate di I
applicabile solo per insiemi finiti (*)
ES.2) A12 = { ( , ) },
A12 * = { ( , ), ((, ( ), )(, )), (((, ... }
un sottoinsieme di A2* ad esempio (solo 4 stringhe):
I2 = { ( ), ( ( ) ), ((( ))), (((( )))) }
ES.3) A13 = { x }, quindi
A3* = { \, x, xx, xxx, xxxx, .... }, e, ad es.,
un sottoinsieme di A3* (un linguaggio) e':
I3 = { x, xx, xxx } )
------------(*) le opere di uno scrittore (fa differenza se vivo o no?)
21
sistemi formali / come definire I:
a)linguaggio dato con elenco completo delle stringhe ben
formate di I - metodo applicabile solo per insiemi finiti :
e i linguaggi naturali?
il linguaggio (*) di Manzoni e' finito;
i linguaggi di Camilleri e/o Benni e/o Trabucchi sono finiti?
un linguaggio naturale (italiano, azero, wolof, ainu, ecc) e' finito?
=> se un linguaggio ha delle regole per produrre parole nuove (e in
genere ogni linguaggio naturale ha queste regole) allora il numero di
parole del linguaggio non e' limitato - non e' finito
(*) inteso come insieme di parole ben formate (elencate in un
dizionario)
22
sistemi formali / come definire I: b) in forma parametrica
b) linguaggio I su A definito in forma parametrica
es.1 : alfabeto A21 = { a,b },
allora:
A21* = { \ , a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab, .... },
A21* = tutte le stringhe fattibili con i simboli di A11
definiamo ad esempio:
I21 = { s = ak b n |
k,n>=0
}
quindi: I21= linguaggio formato da stringhe s su A, con
la proprieta’ : le stringhe di I21 sono fatte di un po’ di
simboli a seguiti da un po’ di simboli b -- nota: a3 = aaa,
in generale ak = stringa formata da a ripetuto k volte
I21 = { a,b,aa,ab,aaa,aaab,abb,...}
23
sistemi formali / definizione parametrica
es.2 : alfabeto di due simboli, zero e uno:
A22 = { 0,1 },
l’insieme A22stellato e’ :
A22* = {\ , 0, 1,00,01,10,11,100,101,110, .... },
definiamo su A22 un linguaggio come insieme di stringhe
formate come un simbolo (0 oppure 1) ripetuto n volte, con
n maggiore di zero:
I22 = { s = an | con a = 0 oppure a=1, e n>0 }
ovvero { 0,1, 00,11, 000,111, 0000,1111, ...}
24
sistemi formali / come definire I:
in forma parametrica .... ancora un esempio:
es.3 :
A23 = { (,) },
A23* = {\ , (, ), ((, )), (), )(, (((, ((), .... },
I23 = { s = (k )k |
k>0 }
linguaggio I23 dato da stringhe formate da un po’ di
parentesi aperte seguite dallo stesso numero di parentesi
chiuse:
ovvero { (), (( )), ((( ))), (((( )))) , ((((( ))))), ...}
25
sistemi formali / come definire I:
... fine degli esempi di definizione parametrica dell'insieme I;
abbiamo detto che SI PUO' DEFINIRE un LINGUAGGIO
in vari modi:
a)
elenco completo
b)
in forma parametrica
c)
con un criterio di appartenenza
d)
con delle regole di produzione
vediamo il terzo metodo:
definizione di un linguaggio
con un criterio di appartenenza
26
sistemi formali / definire I con criterio di appartenenza
definizione di un linguaggio I su un alfabeto A
con un criterio di appartenenza:
dato A appartengono ad un linguaggio I tutte le stringhe di
A*che hanno una certa proprieta’ caratteristica.
quindi dato un alfabeto A e l'insieme A*
per sapere se una stringa appartiene a I
devo controllare se essa possiede la proprieta' richiesta !
es.: tutte le stringhe sull'insieme A*
lettere "ndamen"
che contengono la sequenza di
27
sistemi formali / definire I con criterio di appartenenza
Es.1) : stringhe di parentesi ben formate , definite da:
A31 = { ), ( },
A31* = { \ , (, ), ((, )), (), )(, (((, ))), ()(), .... },
I31 = { s | s di A* , s tale che
1) ad ogni ( in s segue una ) e
2) ogni ) in s e’ preceduta da una (
}
es. stringhe di I31:
( ), ( )( ), (( )), ((( ))), ( )( )( ), (( )( )), (( ))(), () (()) ((())) (()) (), ..
es di stringhe che non appartengono a I31:
((, ( ) ), ))), )(, (( ), ...
28
sistemi formali, definire I con un criterio di appartenenza
(cont.) il modo di definire un linguaggio I su un alfabeto A
con un criterio di appartenenza:
dato A appartengono ad un linguaggio I tutte le stringhe di
A* che hanno una certa proprieta’ caratteristica.
Talvolta e’ possibile definire un “automa riconoscitore”
[una macchina, un programma] che riceve come dato in
ingresso una stringa generica s di A stellato e fornisce come
risultato la risposta “si” oppure “no”.
Ritorneremo su questo argomento ....
(si provi a scrivere un programma che riconosce se una
stringa di caratteri data se e' del tipo (k )k oppure no )
29
sistemi formali, definire I con un criterio di appartenenza
ancora due esempi :
30
A32 = { a,b },
A32* = { \ , a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab, .... },
I32 = { s
| s di A* , con s palindroma }
ricorda: stringa palindroma = simmetrica rispetto il centro
stringa,
esempi di stringhe palindrome (ben formate per il ling. I32):
a,b,aa,bb,aaa, aba,bab,bbb, abba, baab, bbbb, ...
stringhe "cattive" o non ben formate:
ab, aab, baba, abbbbb, ....
sistemi formali, definire I con un criterio di appartenenza
es.3 :
A33 = { 0, 1 }
A33* = { 0, 1, 00, 01, 10, 11, 100, 101,..., 111, 1000, ... }
I33 = { s | s di B *, s tale che il numero degli 1 in s e’ pari}
esempi di s.b.f. :
0, 11, 011, 101, 110, 01010, ....
esempi di s.NON b.f.:
1, 010, 001, 111, 01110, 101010, ....
31
32
esercizio: date le tre definizioni gia' viste di linguaggi:
A31 = { ), ( }, A31* = {\ , (, ), ((, )), (), )(, (((, ))), ()(), ... },
I31 = { s | s di A31* , s tale che 1): ad ogni ( in s segue
una ) e che 2): ogni ) in s e’preceduta da una ( }
A32 = { a,b }, A32* = {\ , a,b,aa,bb,ab, ba,aaa,aab,aba,... },
I32 = { s | s di A32* , con s palindroma }
= { a,b,aa,bb,aaa, aba,bab,bbb, abba, baab, bbbb, ...}
dove aba e' s.b.f. mentre aab non e' s.b.f.
A33 = { 0, 1 } A33* = { 0, 1, 00, 01, 10, 11, 100,..1000, ... }
I33 = { s | s di A33 *, s tale che il numero degli 1 in s e’ pari}
= { 0, 11, 011, 101, 110, 01010, .... }
le stringhe seguenti appartengono a uno dei linguaggi:
( ) ( ), 1111, babbab, ( ( ) ( ), baba, ( ( ) ) , 01101,
( (, 1101101, babbab, 101101, ( ) ( ( ) ) ( )
?
A31*
A31 = { ), ( },
= {\ , (, ), ((, )), (), )(, (((, ))), ()(), ... },
I31 = { s | s di A31*, s tale che 1): ad ogni ( in s segue una )
e s tale che 2): ogni ) in s e’preceduta da una ( }
A32 = { a,b }, A32* = {\ , a,b,aa,bb,ab, ba,aaa,aab,aba,... },
I32 = { s | s di A32* , con s palindroma }
= { a,b,aa,bb,aaa, aba,bab,bbb, abba, baab, bbbb, ...}
A33 = { 0, 1 }, A33* = { 0, 1, 00, 01, 10, 11, 100,..1000, ... }
I33 = { s | s di A33 *, s tale che il numero degli 1 in s e’ pari}
= { 0, 11, 011, 101, 110, 01010, .... }
a che linguaggio appartengono le stringhe:
( ) ( ) si,
( ( ) ( ) no, ( ( ) ) si, ( ( no, ( ) ( ( ) ) ( ) si
babbab si,
baba no,
babbab si,
1111 si,
01101 no,
1101101 no,
101101 si ?
33
sistemi formali, definizione costruttiva di un linguaggio
abbiamo cosi' visto tre modi per definire un LINGUAGGIO
a)
b)
c)
elenco completo
in forma parametrica
con un criterio di appartenenza
vediamo ora il quarto e per noi il piu' interessante
(un sistema formale generativo, dove si dice come si
"fabbricano" stringhe ben formate):
d)
con delle regole di produzione
le regole di produzione ci permettono di costruire (produrre,.
derivare, generare) stringhe ben formate nuove a partire da
stringhe ben formate date; alcune stringhe sono date in
partenza (sono la base del sistema), da esse si derivano le altre
con le regole di produzione.
34
d) si puo' DEFINIRE UN INSIEME I (sottoins. di A* ) con
delle regole di derivazione o regole di produzione con cui
possiamo costruire (produrre) stringhe ben formate nuove da
stringhe ben formate date; es.:
linguaggio I31 = I41 = insieme PBF = parentesi ben formate
alfabeto: ( )
ovvero A = { ( , ) }
base: ( ) sta in PBF
ovvero la stringa ( ) e'ben formata per definizione
1.a regola ( E indica una stringa di A* )
se E sta in PBF allora (E) sta in PBF
(es. se ( ) ( ) e’ PBF, allora ( ( ) ( ) ) e’ PBF)
2.a regola:
se E ed F stanno in PBF allora EF sta in PBF
(es. se ( ) e ( ( ) ) sono PBF, allora ( ) ( ( ) ) e’ PBF)
limitazione: null’altro sta in PBF.
35
sistemi formali, definizione della terna (A,B,P)
ripetiamo: possiamo definire UN LINGUAGGIO I su un
alfabeto A (sottoinsieme di A* ) CON UNA TERNA (A,B,P)
con: A = alfabeto di simboli
B = base = insieme di stringhe ben formate
date in partenza ("assiomi"),
P = un insieme regole di produzione (o derivazione o generazione) di nuove stringhe ben
formate (s.b.f.) a partire da s.b.f. date:
es.: “linguaggio”delle stringhe di parentesi ben formate I41:
A = { ), ( }
= insieme di due simboli
B = { () }
= una stringa base (assioma)
P = { p1, p2 } = 2 regole di produzione:
p1 = se s e’ pbf allora ( s ) e' pbf
p2 = se s,p sono pbf allora sp e' pbf
36
sistemi formali, definizione di deriva e deriva direttamente
37
due definizioni: dati (A,B,P) con A = alfabeto di simboli,
B = base = ins. di stringhe ben formate date ("assiomi"),
P = regole di produzione di nuove s.b.f. da s.b.f. date;
diremo che
q deriva direttamente da p
se esiste una regola di produzione che da p produce q,
scrivo
p
q
e (def.) : q deriva da p
se esiste una sequenza di stringhe p0,p1,p2,p3,.. pn tali che
p0=p, pn=q,
e
pi
pi+1,
con i=0..n
scrivo
p
*
q
(freccia con * sopra)
sistemi formali: definizione di linguaggio da terna (A,B,C)
38
dati: un A = alfabeto di simboli, una base B con
B = insieme di stringhe ben formate date ("assiomi"), e
P = regole di produzione di nuove s.b.f. da s.b.f. date:
( se p produce q scrivo p -> q ( q deriva direttamente da p ),
e se esiste una sequenza di stringhe p0,p1,p2,p3,.. pn tale che
p0=p, pn=q, e pi -> pi+1, con i=0..n, allora diremo che
q deriva da p, scrivo: p
*
q
(freccia con * sopra) )
la terna (A,B,P) definisce un linguaggio I = l’insieme delle
stringhe su A derivabili dalla base B con le regole di
produzione P
I={s| b
*
s; dove b appartiene a B; s,b app.ad A * }
cioe' I e' dato dalle stringhe derivabili con una catena di
produzioni dirette da una stringa della base
sistemi formali, es. I42 stringhe cccc
un linguaggio I e’ l’insieme delle stringhe su A derivabili
dalla base B con le regole di produzione P ==>>
diremo che la terna (A,B,P) genera il linguaggio I.
cinque esempi di sistemi formali generativi:
I42) linguaggio delle stringhe cccc:
A = { c } B = { cc } P = { p1, p2 }
con
p1: cc -> cccc
p2: ccS -> ccSS
dove S sta per stringa qualunque
es.di produzioni (indico anche il numero della regola di
produzione usata; es. ->2 significa: applico p2 ed ho..) :
cc ->1
cccc
->2
cccccc
->2
cc cccc cccc ->..
(nota: non posso applicare la regola p1 alla stringa cccc !)
39
sistemi formali, es. I43 stringhe ab
I43) linguaggio delle stringhe ab:
A = { a, b },
B = { ab }
P = { p1,p2,p3 }
con
p1: ab -> abba
p2: abS -> abSS
p3: Sba -> SSba
dove S sta per stringa qualunque
produce infinite stringhe, es : (indico anche la regola di
produzione usata ad es. con
ab ->1 ab ba si intende:
applico la produzione p1 alla stringa ab e ottengo abba):
es:
ab ->1 ab ba , poi: ab ba ->2 ab ba ba (qui S e’ ba)
poi: abba ba ->3 abba abba ba (qui S e’ abba) ecc;
es:
ab ->1 ab ba ->3 ababba ->3 abab abab ba
40
41
sistemi formali, esempio I43 stringhe ab, esercizio
esercizio per il linguaggio I43 o insieme delle stringhe ab:
A = { a, b }, B = { ab }
( di seguito S sta per stringa qualunque)
P = { p1,p2,p3 }
con
p1: ab -> abba
p2: abS -> abSS
p3: Sba -> SSba
esercizio: le stringhe qui a destra
appartengono al linguaggio I
definito dalla terna A,B,P ?
(trovare le catene di produzione,
se esistono):
abbaabbaba
bba
ab
abbb
a
ababababba
abababba
baab
sistemi formali, esercizio per I43
esercizio per il linguaggio I43 (insieme delle stringhe ab) :
A={ a, b }, B={ ab }, P={ p1,p2,p3 } S=stringa qualunque
p1: ab -> abba
p2: abS -> abSS
p3: Sba -> SSba
le stringhe seguenti appartengono al linguaggio I definito
dalla terna A,B,P ? (trovare le catene di produzione, se
esistono):
abbaabbaba ab->1 abba ->2 abbaba ->3 abbaabbaba
bba
non derivabile: tutte le stringhe iniziano con ab
ab
appartiene a I43 - e' la base !
abbb non derivabile: tutte le stringhe finiscono con ba
a
non derivabile: almeno i 2 caratteri ab
ababababba ab->1 abba ->3 abab ba ->3 abab abab ba
abababba non derivabile: parte iniziale con 3 ab !
baab non derivab.(non inizia con ab, non finisce con ba)
42
sistemi formali, es. I44 somma in unario
43
I44 - linguaggio per la "somma" in unario
A = { |, p, e } insieme di 3 simboli
B = { | p | e || } leggi 1 piu' 1 = 2 [e'l'unica s.b.f. di partenza]
P = { p1, p2 } vi sono due produzioni:
p1 = x p y e z -> x | p y e z |
(leggi: se x+y=z allora (x+1)+y=(z+1)
p2 = a p b e c -> a p b | e c |,
(leggi: se a+b=c allora a+(b+1)=(c+1); si noti che
x,y,z,a,b,c sono tutte strin. formate da uno o piu' | )
|p|e|| ->2 |p||e||| ->1 ||p||e|||| ->1
1+1 = 2, 1+2 = 3,
2+2 = 4,
|||p||e||| || ->1 |||| p || e ||| ||| ...
3+2 = 5,
4+2 = 6,
(nb: la riga sotto riporta l'interpretazione "esterna"al sistema formale)
|p|e|| ->2 |p||e|||->2 |p|||e||||->2 |p||||e|||||->2 |p|||||e||||||, ...
1+1=2, 1+2=3, 1+3=4,
1+4 = 5
1+5=6, ...
sistemi formali esempio: I45 sistema formale modesto
44
un sist. form. generat. (A,B,P) non necessariamente produce
insiemi di stringhe ben formate grandi o infiniti; esempio:
I45 un sistema formale "modesto":
A = { a, b, x, y } alfabeto di 4 simboli a,..y
B = { a, b }
base: 2 stringhe, la stringa a e la stringa b
P = { p1,p2,p3,p4 } quattro produzioni: con S stringa non
p1= a -> xx
p2= b -> yy
vuota qualunquep3= Sa -> SS
p4= Sb -> SyyS
S e' un contesto (*)
produce un linguaggio finito di sole 4 stringhe (le due della base a e b
e due nuove xx e yy:
a ->1 xx ; b ->2 yy ; ... e non posso applicare altro
le produzioni p3 e p4 non si possono applicare mai!
il linguaggio completo e' I = { a, b, xx, yy } = B + { xx,yy }
(*) le stringhe contesto sono generiche, non e'detto ben formate
sistemi formali, definizioni, es.: I46, linguaggio==base
talvolta un sist.form.gener. non riesce a produrre nulla:
vediamo I46, linguaggio generato da un sistema formale
modesto, anzi, modestissimo (un sistema formale "cisto") :
A = { a,b,c,x}
alfabeto di 4 simboli
B = { aa,bb,cc } base di 3 stringhe
P = { p1,p2,p3 } tre produzioni:
p1= Sx ->bbSxbb
p2 = xS ->aaxSaa
p3= xSx ->xxSSxx
ma nessuna delle tre regole di produzione e'
applicabile alle tre stringhe date nella base!
quindi I = B ovvero
il linguaggio I46 generato da (A,B,P) coincide con la base !
45
sistemi formali -
ripetizione definizione di linguaggio
abbiamo cosi' visto che un
"LINGUAGGIO"
formale, inteso come qualunque
insieme specificato come sottoinsieme
SI PUO' DEFINIRE in vari modi:
a) elenco completo - es. I3 = { x, xx, xxx }
b) in forma parametrica – es: I23 = { s = (k )k | k>0 }
c) con un criterio di appartenenza - es.
I32 = { s | s di A* , con s palindroma }
d) con delle regole di produzione
46
sistemi formali e grammatiche // ripetizione
d): le regole di produzione ci permettono di costruire stringhe
ben formate nuove a partire da stringhe b. f. date (base):
I41 ricordiamo l'esempio I41:
insieme PBF = parentesi ben formate:
base: ( ) sta in PBF
produzioni:
1.a regola: se E sta in PBF allora (E) sta in PBF
(es. se ( ) ( ) e’ PBF, allora ( ( ) ( ) ) e’ PBF)
2.a regola: se E ed F stanno in PBF allora EF sta in PBF
(es. se ( ) e ( ( ) ) sono PBF, allora ( ) ( ( ) ) e’ PBF)
limitazione: null’altro sta in PBF.
dato (A,B,P) un linguaggio I e’ l’insieme delle stringhe
su A derivabili dalla base B con le regole di produz. P
I={ s| b
*
s; b
C
B; s,b
C
A*
}
cioe' I e' dato dalle s.b.f. derivabili con una catena di
produzioni dirette da una stringa della base
47
sistemi formali: esempio I47 stringhe palindrome:
I47) un sistema formale che genera semplici stringhe
palindrome:
A = { a,b }
[due simboli]
B = { a, b, aa, bb } [quattro stringhe base]
P = { p1, p2 }
[due produzioni, che sono:]
p1 = S -> a S a ;
p2 = S -> b S b;
due esempi di catene di derivazione:
a ->1 aaa ->2 baaab ->2 bbaaabb ->1 abbaaabba ...
oppure
bb->2 bbbb ->1 abbbba ->2 babbbbab ->1 ababbbbaba ...
esercizio: derivare la stringa
abababa
48
sistemi formali: esempio I47 stringhe palindrome:
soluz. esercizio: derivare la stringa
abababa
dal sistema formale che genera stringhe palindrome I47
A = { a,b }
[due simboli]
B = { a, b, aa, bb } [quattro stringhe base]
P = { p1, p2 }
[due produzioni, che sono:]
p1 = S -> a S a ;
p2 = S -> b S b;
abbiamo visto due esempi di derivazione
a ->1 aaa ->2 baaab ->2 bbaaabb ->1 abbaaabba ...
bb->2 bbbb ->1 abbbba ->2 babbbbab ->1 ababbbbaba ..
vediamo la derivazione della stringa:
abababa
si ottiene con la seguente catena di
derivazione:
b->1 aba ->2 babab ->1 abababa
49
sistemi formali / piu'catene di derivabilita' per una stringa
riprendiamo l'esempio I41: ATTENZIONE ! lo stesso
linguaggio puo’ essere generato con due o piu' sistemi
formali diversi: ad es.
le parentesi ben formate I41 possono essere prodotte con:
I41a) A = { (,) } [due simboli] B = { ( ) } [una stringa base]
P = {p1, p2} due produzioni: p1= s ->( s ); p2= s,q -> s q;
oppure con il sistema seguente, con le produzioni cambiate:
I41b) A = { (,) } [due simboli] B = { ( ) } [una stringa base]
P = {p1, p2, p3} [ tre produzioni, che sono:]
p1 = s -> ( s );
p2 = s -> s s;
p3 = s ( ) t -> s t;
1)nota: la produzione p3, accorcia le stringhe!
2)nota: nella p3 s,t da sole possono anche NON essere s.b.f.
da cui ho ad es:
( ) ->1 (( )) ->2 (( )) (( )) ->3 ( ) (( )) ->3 ( ) ( ) ...
50
sistemi formali - piu'catene di derivazione per una stringa
continua I41b) parentesi ben formate: A = { (,) } B = { ( ) }
P = { p1: s -> ( s ); p2: s -> s s; p3: s ( ) t -> s t }
es: nel sistema I41b posso ottenere ( ) ( ) in due modi:
cosi'
( ) ->1 (( )) ->2 (( )) (( )) ->3 ( ) (( )) ->3 ( ) ( )
oppure: ( ) ->2 ( ) ( )
quindi: in generale una stringa di un linguaggio I puo’
avere piu’ derivazioni possibili!
ancora un es. di stringa derivabile in piu’ modi:
( ) ->1 ( ( ) ) ->2 ( ( ) ) ( ( ) ) ->2 ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ->3
( ( ) ) ( ) ( ( ) ) ( ( ) ) ->3 ( ( ) ) ( ) ( ) ( ( ) ) ->3 ( ( ) ) ( ) ( ( ) )
->1 ( ( ( ) ) ( ) ( ( ) ) ) ->3 ( ( ( ) ) ( ( ) ) ) ->3 ( ( ) ( ( ) ) )
->3 ( ( ( ) ) ) ->3 ( ( ) ) ->3 ( ) ... e siamo ritornati alla base;
Esercizio: posso derivare la stringa vuota? ( ) ->3 \ e’ok?
51
52
sistemi formali: derivabilita'
continua I41b) parentesi ben formate A = { (,) } B = { ( ) }
P = { p1: s -> ( s ); p2: s -> s s; p3: s ( ) t -> s t }
Esercizio: posso derivare la stringa vuota? ( ) ->3 \ e’ok?
per rispondere, si noti che in generale nelle produzioni del
tipo s X q -> ... [con s e q stringhe su A e X un simbolo di
A ] NON e' necessario che s e q siano ben formate,
(questo e' richiesto per la stringa completa sXq, come anche
per la s che sta in s-> ...); in particolare queste s e q
possono essere stringhe vuote, per cui la risposta e' si, e
possiamo derivare:
( ) -> 2
( ) ( ) -> 1
( ( ) ( ) ) -> 3
( ( ) ) -> 3 ( ) -> \
sistemi formali sistema I48 per generare i n*n
I48) quadrati dei numeri naturali (*) A = { 1,x } B = { 1x }
P = { p1: a x b -> a 11 x a b;
p2: a x b -> b }
es:
(genera i quadrati di n):
1 x ->2 \ (str.vuota)
1 x ->1 1 1 1 x 1 ->2 1, oppure, sulla stessa stringa,
1 1 1 x 1 ->1 1 1 1 1 1 x 1 1 1 1 ->2 1 1 1 1,
1 1 1 1 1 x 1 1 1 1 ->1 1 1 1 1 1 1 1 x 1 1 1 1 1 1 1 1 1 ->
->2 1 1 1 1 1 1 1 1 1, ecc
produce stringhe “con x” tipo 1a+2 x 1a+b con a = 1,3,5,7,..
e con b = 1, 4, 9, ...
e stringhe “senza x” tipo 1b
produce quindi i quadrati dei numeri naturali,
(*) rispecchia il procedimento (a,b variabili a valori interi):
a=1; b=1; ripeti: a=a+2, b=a+b fino_a_che_basta; ...
53
sistemi formali: deducibilita'
Problema:
dato un sistema formale (A,B,P) (alfabeto, base, produzioni)
e data una stringa s dell'insieme A* si puo' chiedere:
s appartiene al linguaggio definito da (A,B,P)
cioe': s e' una stringa ben formata del linguaggio generato
dal sistema (A,B,P) ?
ovvero s e' derivabile da B con le regole P ?
ovvero s e' deducibile da B con le regole P ?
si noti che un caso particolare di questo problema e' l'accettazione da
parte del compilatore del testo di un programma ...
vediamo cosa implica la risposta, ma prima un esempio ...
54
sistemi formali: deducibilita' : il sistema MIU
il sistema MIU di Hofstadter:
A = { M, I, U }
B = { MI }
P = { p1,p2,p3,p4 }
con:
p1=aI->aIU
p2=Mb->Mbb
p3=aIIIb->aUb
p4=aUUb->ab
ovvero:
p1: se una s.b.f. x finisce con I allora la stringa xIU e' b.f.
(posso appendere una U se la s.b.f. finisce con I)
p2: se una s.b.f. inizia con una M allora raddoppiando la
parte che segue la M (suffisso) e' ben formata;
p3: se una s.b.f. contiene tre I consecutive allora la str.
ottenuta sostituendo alle tre I una U e' anche b.f.;
p4: se una s.b.f.contiene due U allora togliendo
queste due U si ottiene ancora una s.b.f.;
55
sistemi formali: deducibilita' : il sistema MIU
cont. il sistema MIU di Hofstadter:
A = { M, I, U }
B = { MI }
P = { p1,p2,p3,p4 }
con:
p1=aI->aIU
p2=Mb->Mbb
p3=aIIIb->aUb
p4=aUUb->ab
un es. di catena di derivazione:
MI ->2 MII (applico la p2: se una s.b.f. inizia con una M
puoi raddoppiare quanto segue la M), poi, continuando:
MII ->2 MIIII (come sopra), poi
MIII ->1 MIIIIU (la p1 dice: se una s.b.f. finisce con una I
puoi appendere una U)
MIIIIU ->3 MIUU (sostituisce a tre I una U ) MIUU
MIUU ->4 MI ( ... riottengo la stringa di partenza ;-)
56
sistemi formali: deducibilita' : il sistema MIU
cont. il sistema MIU di Hofstadter:
A = { M, I, U }
B = { MI }
P = { p1,p2,p3,p4 }
con:
p1=aI->aIU
p2=Mb->Mbb
p3=aIIIb->aUb
p4=aUUb->ab
secondo es. di catena di derivazione:
MI ->2 MII ->2 MIIII ->1 MIIIIU ->2 MIIIIUIIIIU
->3 MUIUIIIIU ->3 MUIUUIU ->4 MUIIU ...
57
sistemi formali: deducibilita' : il sistema MIU
domanda di “derivabilita’ (o decidibilita') :
dato il sistema MIU,
MU e' una s.b.f.?
ovvero: esiste una catena di derivazione da MI a MU ?
cioe’ esiste: MI * MU ?
in generale, possiamo porre il problema:
dato 1) un sistema formale generativo (A,B,P) che definisce
un linguaggio I, e 2) data una stringa generica s,
e’ possibile decidere se s appartiene a I
ovvero
se s e’ derivabile da B?
58
sistemi formali: deducibilita'
il problema della derivabilita’ (producibilita'), ovvero:
dato un sistema formale generativo (Alfab,Base,Produz)
che definisce un linguaggio I, e data stringa s,
possiamo decidere se s appart.a I [se s e’derivabile da B] ?
ha una risposta positiva in alcuni casi:
se un sistema formale (A, B, P) ha le regole di produzione di
tipo “monotono” = tali che in ogni caso le stringhe prodotte
da una regola sono piu' lunghe delle stringhe di partenza per
la regola stessa, [ cioe’ se x -> y allora |x| <= |y| ],
-
allora si puo' sempre decidere se una stringa e' ben formata:
59
sistemi formali: deducibilita'
60
dato un sistema formale generativo (A, B, P) e data una
stringa s, possiamo decidere se s appartiene ad I ovvero se s
e’derivabile da B ?
si puo' sempre decidere se una stringa e' ben formata in un
sistema (A,B,P) SE il sistema formale ( Alfabeto, Base,
Produzioni ), ha le regole di produzione di tipo “monotono”
cioe' tali che in ogni caso le stringhe prodotte da una regola
sono piu' lunghe delle stringhe di partenza per la regola
stessa, [ cioe’ se x -> y allora |x| <= |y| ],
procedimento: per sapere se s c I basta costruire l’insieme
K di tutte le s.b.f. k a partire dalla B con |k| <= |s| e poi
controllare se s sta in K;
il procedimento richiede un num.ro finito di passi (per ipotesi)
sistemi formali: deducibilita'
es.: il sistema somma in unario permette di decidere in
modo meccanico se una str. r e' ben formata: basta
elencare tutte le s tali che la lunghezza di s: |s| <= |r|
in generale pero' un sistema formale ha regole di
produzione tali che alcune allungano e altre accorciano le
stringhe, e allora non sappiamo dare una risposta al
problema della derivabilita’:
i sistemi generativi (A,B,P) in generale consentono di
generare tutte le stringhe (per definizione), ma in generale
NON consentono di decidere, data una stringa s, se essa e'
ben formata oppure no --
diremo che tali sistemi sono generabili
ma non decidibili.
61
sistemi formali: deducibilita'
ripetiamo - con un sistema formale dove alcune regole di
produzione allungano e altre accorciano le stringhe allora
in generale non si riesce a decidere sulla derivabilita’ di s:
tali sistemi consentono di generare tutte le stringhe ben form.
(per definizione), ma in generale NON consentono di decidere, data una stringa s, se essa e' ben formata oppure no:
sia s stringa su A*, con n=|s| ad es. n=5; anche se produco
alcune stringhe lunghe k<=5, applicando le regole a partire
dalla base, non so se le ho prodotte tutte: siccome vi sono
produzioni che accorciano, non posso sapere se magari
potrei produrre s da una stringa m, con |m|=10000,
applicando opportune regole che accorciano le stringhe...
cioe’ non riesco a sapere se ad un dato punto ho prodotto
TUTTE le stringhe di lunghezza <= |s| !
62
sistemi formali: deducibilita'
quindi per quanto riguarda il problema posto prima sulla
derivabilita' della stringa MU dal sistema MIU, la risposta
e' NO;
(caso di sistemi formali con regole di produzione dove alcune
allungano e altre accorciano le stringhe in generale NON
posso decidere, data una stringa s, se essa e' ben formata
oppure no)
ma:
talvolta esistono criteri "esterni" al sistema formale
generativo, che permettono di stabilire delle proprieta’ che
discriminano le s.b.f. da altre, e quindi permettono di
decidere se s e’ b.f.
ora possiamo ritornare al sistema MIU ....
63
sistemi formali: deducibilita'
il sistema MIU non permette di decidere in modo meccanico
(algoritmico) se MU e' ben formata; ma ...
ricordiamo la definizione del sistema MIU:
A = {M,I,U}
B = { MI }
P = { p1,p2,p3,p4 }
con: p1 = aI->aIU
p2 = Mb->Mbb
p3 = aIIIb->aUb p4 = aUUb->ab
il sistema MIU e' (ovviamente) stato definito in modo da
avere le produzioni che sia allungano sia accorciano,
ma e' stato definito in modo da avere la risposta con un
ragionamento "esterno" al sistema, basato su delle
proprieta' delle stringhe MIU,
proprieta' osservabili dalle regole di produzione ma non
appartenenti al sistema MIU !!
... vediamo ...
64
sistemi formali: deducibilita' - MIU produce MU ?
il sistema MIU
65
ricordiamo la definizione del sistema MIU:
A = {M,I,U}
B = { MI }
P = { p1,p2,p3,p4 }
con: p1 = aI->aIU
p2 = Mb->Mbb
p3 = aIIIb->aUb p4 = aUUb->ab
per ottenere MU devo avere MIII ->3 MU; quindi devo
avere una Mz dove z e’ stringa con sottostringa III;
si noti pero’ che per quanto riguarda il numero delle I nelle
s.b.f. le produzioni di MIU o non cambiano tale numero (p1,
p4) o lo raddoppiano (p2) oppure lo diminuiscono di 3 (p3);
quindi se la stringa di arrivo deve avere tre I, allora la
stringa di partenza deve avere un numero di I che e’
multiplo di 3 -> MA la base MI ha una I sola ->
non posso ottenere tre I -> non posso ottenere MU !
66
Esercizio:
Cosa produce il sistema formale generativo seguente:
A = { a, b, e }
B = { aaaa }
P = { p1: aaaa -> aaaba,
p2: aaaS -> SaabaS,
p3: SaaT -> SabaT,
p4: SaT -> SeT
p5: aaaa-> beaabe }
dove S e T sono stringhe qualunque di A* (anche vuote)
67
FINE DELLA PRIMA PARTE SISTEMI
FORMALI
GENERATIVI
E
LINGUAGGI