1 SISTEMI FORMALI e GRAMMATICHE ( parte 1 - sistemi formali )

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 traduzioneeseguito 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

3sistemi 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 ...

4sistemi 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,

5sistemi 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

6sistemi 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 !

7sistemi 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 sche 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?

8sistemi 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 [insieme vuoto] allora: A4 * = 0* = { \ }

9sistemi 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 )

10sistemi formali - alcuni esempi A6

es.6) 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)

11sistemi 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.)

12sistemi 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.

13sistemi 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

14sistemi formali - proprieta'della concatenazione

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|

15sistemi 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 ...

16sistemi 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 ...

17sistemi formali e linguaggi / definizioni: linguaggio

definz: LINGUAGGIO I e’un SOTTOINSIEME di AI 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 !

18sistemi 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, ...}

19sistemi 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...

20sistemi 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 *

21sistemi 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?)


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)

23sistemi 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,...}

24sistemi 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, conn maggiore di zero:

I22 = { s = an | con a = 0 oppure a=1, e n>0 }

ovvero { 0,1, 00,11, 000,111, 0000,1111, ...}


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 { (), (( )), ((( ))), (((( )))) , ((((( ))))), ...}


... 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 parametricac) con un criterio di appartenenza d) con delle regole di produzione

vediamo il terzo metodo:

definizione di un linguaggio con un criterio di appartenenza

27sistemi 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* che contengono la sequenza di lettere "ndamen"

28sistemi 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: ((, ( ) ), ))), )(, (( ), ...

29sistemi 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 )


ancora due esempi :

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


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

32esercizio: 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, ( ) ( ( ) ) ( ) ?

33A31 = { ), ( }, 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 ?

34sistemi formali, definizione costruttiva di un linguaggio

abbiamo cosi' visto tre modi per definire un LINGUAGGIO

a) elenco completo b) in forma parametricac) 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):


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.

35d) 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 definizione1.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.

36sistemi 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

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 deriva e deriva direttamente

*

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: definizione di linguaggio da terna (A,B,C)

*

*

39sistemi 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 !)

40sistemi 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 -> abSSp3: 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

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

abbaabbaba bba ab abbb a ababababba abababba baab

esercizio: le stringhe qui a destra appartengono al linguaggio I definito dalla terna A,B,P ? (trovare le catene di produzione, se esistono):

42sistemi 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 -> SSbale 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 abbaabbababba non derivabile: tutte le stringhe iniziano con ab ab appartiene a I43 - e' la base !abbb non derivabile: tutte le stringhe finiscono con baa non derivabile: almeno i 2 caratteri abababababba ab->1 abba ->3 abab ba ->3 abab abab baabababba non derivabile: parte iniziale con 3 ab !baab non derivab.(non inizia con ab, non finisce con ba)

43sistemi formali, es. I44 somma in unario

I44 - linguaggio per la "somma" in unarioA = { |, 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 |||p||e||| || ->1 |||| p || e ||| ||| ... 1+1 = 2, 1+2 = 3, 2+2 = 4, 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, ...

44sistemi formali esempio: I45 sistema formale modesto

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 bP = { p1,p2,p3,p4 } quattro produzioni: con S stringa non p1= a -> xx p2= b -> yy vuota qualunque- p3= 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 altrole 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

45sistemi 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 simboliB = { aa,bb,cc } base di 3 stringheP = { 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 !

46sistemi 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 }


47sistemi formali e grammatiche // ripetizioned): 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

*

48sistemi 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 ...oppurebb->2 bbbb ->1 abbbba ->2 babbbbab ->1 ababbbbaba ...

esercizio: derivare la stringa abababa

49sistemi formali: esempio I47 stringhe palindrome:

soluz. esercizio: derivare la stringa abababadal 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: abababasi ottiene con la seguente catena di derivazione: b->1 aba ->2 babab ->1 abababa

50sistemi 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 ( ) ( ) ...

51sistemi 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?

52sistemi 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 ( ) -> \

53sistemi 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; ...

54sistemi 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 ...

55sistemi 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->abovvero: 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.;


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), poiMIII ->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 ;-)


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


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?

*


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:-


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)


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.


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| !


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


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

65sistemi formali: deducibilita' - MIU produce MU ?

il sistema MIU 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

1 SISTEMI FORMALI e GRAMMATICHE ( parte 1 - sistemi formali )

Documents

Transcript of 1 SISTEMI FORMALI e GRAMMATICHE ( parte 1 - sistemi formali )