1 SISTEMI FORMALI GENERATIVI. 2 per capire un' po' le grammatiche dei linguaggi di programmazione e...

1

SISTEMI

FORMALI

GENERATIVI

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 alcune nozioni preliminari

* sistemi formali generativi

vedremo poi

* linguaggi formali, * classificazione dei linguaggi alla Chomsky * grammatiche BNF e EBNF * riconoscimento di strutture grammaticali

3sistemi formali - definizioni: alfabeto

un linguaggio e' un sistema formale basato su :

un alfabeto (un insieme di simboli base predefiniti) e un insieme di stringhe formate/formabili con i simboli dell'alfabeto:

1. esempio: alfabeto 0,1 stringhe: 0, 1010, 11110011110101, ...

2. esempio: alfabeto & * # @ stringhe: &, &&, &&&, @, @@, @@@, &@, &&@, &@@,

3. esempio: alfabeto a,b,c,d,e, f,g,h,i,l, m,n,o,p,q, r,s,t,u,v, z stringhe: a, aa, aaa, ab, aab, aaab, abb, aba, ... z,zz,zzz,za,zaa,zv,zvv,zvz,zzzzv,zzzzvzzzz, ...


un linguaggio e' un sistema formale basato su :un alfabeto (un insieme di simboli base predefiniti) con cui si forma un insieme di stringhe - ( in generale NON tutte le stringhe sono considerate valide )

2. esempio: alfabeto a,b,c,d,e, f,g,h,i,l, m,n,o,p,q, r,s,t,u,v, z stringhe: a, di, fa, se, va, chi, dopo, sicuro, ... considero solo le stringhe formate con le lettere dell' alfabeto italiano che sono anche parole in lingua italiana

in generale non tutte le stringhe formabili con l'alfabeto appartengono al linguaggio! - quindi:oltre all'alfabeto, in genere ho delle regole per stabilire quali stringhe sono del linguaggio cioe' "ben formate", e quali no


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 cui si possono formare delle stringhe di caratteri,

un insieme di regole per stabilire se una stringa appartiene al linguaggio e/o per costruire stringhe del linguaggio.

seguono delle definizioni ...

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

7sistemi formali - definizioni: lunghezza di stringa

alfabeto = insieme A di simboli, si definisce stringa su A = sequenza finita di simboli di A,una stringa puo' essere eventualmente vuota;

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

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

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

10sistemi formali - esempi A4

seguono due esempi "limite":

4.o esempio:

A4, alfabeto vuoto: A4 = { } [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 λ ( ricorda: λ = lambda )

quindi: se l' alfabeto e' vuoto: A4 = { } [insieme vuoto] allora: A4 * = 0* = { λ } [insieme di un solo elemento]

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

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

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

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

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

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

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

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

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

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

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

22sistemi formali / come definire I: a) elenco completo

a) elenco completo delle stringhe ben formate di I

ovviamente 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 *

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

i linguaggi (*) di Joyce e/o di Manzoni sono finiti ?

i linguaggi di Fforde e/o Benni e/o Rushdie 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 frasi (di parole) ben formate (parole elencate in un dizionario)

25sistemi 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 A21

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

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

29sistemi 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 0) :alfabeto A = {a,b,c,d,e,...u,v,z} (della lingua italiana), considero il linguaggio I delle stringhe di A* tali che contengono la sequenza di lettere "ndamen" ... ad es. "fondamenti" "andamento", ma ancheuvvundamenbbbccz e zzzzzndamenfffffff ...

30sistemi 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 godono delle due proprieta': 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: ((, ( ) ), ))), )(, (( ), ...

31sistemi formali: linguaggio I definito con criterio di appartenenza

si puo' 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 e' del tipo (k )k oppure no )

32sistemi formali: linguaggio I definito con criterio di appartenenza

si provi a scrivere un programma che riconosce se una stringa di caratteri data e' del tipo (k )k oppure no:

int main(){ char c; int conta; readchar(c); conta=0; while( c=='(' ) { conta++; readchar(c); } ...

da fare ;-)

}

33sistemi formali, definire I con un criterio di appartenenza

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

34sistemi 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 stringhe ben formate (numero 1 pari): 0, 11, 011, 101, 110, 01010, ....

esempi di stringhe NON ben formate (numero 1 dispari): 1, 010, 001, 111, 01110, 101010, ....

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

36A31 = { ), ( }, 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, .... } soluzione: le stringhe appartengono ad uno dei 3 linguaggi: ( ) ( ) si, ( ( ) ( ) no, ( ( ) ) si, ( ( no, ( ) ( ( ) ) ( ) si babbab si, baba no, babbab si, 1111 si, 01101 no, 1101101 no, 101101 si a quale?

37sistemi formali, definizione costruttiva di un linguaggioabbiamo visto tre modi per definire un LINGUAGGIO cioe' l' insieme delle stringhe ben formate s.b.f.

a) elenco completo b) in forma parametricac) con un criterio di appartenenza

vediamo ora il quarto e per noi il piu' interessante,i sistemi formali generativi, dove si dice come si "fabbricano" o come si producono stringhe ben formate:

d) con delle regole di produzione

le regole di produzione permettono di produrre (derivare, generare) stringhe ben form. nuove a partire da s.b.f. date; alcune stringhe sono date in partenza = base del sistema), da esse si derivano le altre con le regole di produzione.

38ripeto: si DEFINISCE UN INSIEME I (sottoins. di A* ) con delle regole di derivazione (produzione) con cui si costruiscono (producono) stringhe ben formate nuove da stringhe ben form. date; rivediamo ad esempio il 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.

39sistemi formali, definizione della terna (A,B,P)

ripetiamo: UN LINGUAGGIO I su un alfabeto A (sotto-insieme di A* ) si definisce 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

40

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 (defin.) : q deriva direttamente da p se esiste una regola di produzione che da p produce q,

scrivo p q

e (defin.) : 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

*

41

dati: A = alfabeto di simboli, una base B con B = insieme di stringhe ben formate date ("assiomi"), 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 con terna (A,B,C)

*

*

42sistemi 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, e ccS sta per stringa data da concatenazione di due c e una S 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 !)

43sistemi 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 abba 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

44

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

45

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

proprieta' che devono avere le stringhe per la definizionedata di A,B,P:

tutte le stringhe iniziano con ab,tutte le stringhe hanno un numero pari di ab oppure ba,tutte le stringhe piu' lunghe di 2 finiscono con ba,

46sistemi formali, esercizio per I43

soluzione esercizio per il linguaggio I43 (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):

per la soluzione uso alcune proprieta' derivabili dal sistema: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: parte iniziale con 3 ab, ab devono esser pari!baab non derivab.(non inizia con ab, non finisce con ba)

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

48sistemi 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 che sono ben formate

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

(*) che a TS sta per "senza soldi"

50sistemi formali - ripetizione definizione di linguaggio

abbiamo visto che un

"LINGUAGGIO FORMALE", inteso come un insieme

specificato come sottoinsieme di un A*

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 la terna: alfabeto, base, delle regole di produzione

51sistemi formali e grammatiche // ripetizioneLa terna (Alfab.,Base,Prod.) ci permette di costruire stringhe ben formate nuove a partire da stringhe b. f. date (base):

ricordiamo l'esempio I41 dell' insieme PBF = parentesi ben formate: A) alfabeto: { (, ) } B) base: ( ) sta in PBF P) 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; con b C B; e s,b C A * }

cioe' I (insieme delle s.b.f.) e' dato dalle stringhe derivabili con una catena di produzioni dirette da una stringa della base

*

52sistemi formali: esempio I47 stringhe palindrome:

I47) un sistema formale che genera stringhe palindrome (o) :

A = { a,b } [alfabeto di 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 ...

--------------------(*) ricorda: ->1 sta per "applico la produzione numero 1" cioe'p1 = S -> a S a e ho da a ->1 aaa --------------------(o) stringhe palindrome sono a, aa, aba, bab, bbabb, aabaa, babaabab,.. mentre ab, abb, ba, bba, bbab, abaa, babaaba, .. non sono palindrome


I47) "linguaggio" delle stringhe palindrome:

A = { a,b } [alfabeto di 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;

esercizio: derivare la stringa : abababa

la stringa aba b aba ha una b in mezzo, quindi la derivazione partira' dalla stringa di base b;b puo' produrre b ->1 aba oppure b ->2 bbb, sceglieremo la p1, e abbiamo parte di abababa da aba devo ottenere a babab a quindi uso p2...


continua 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;

la derivazione della stringa: abababa si ottiene con la seguente catena di derivazione: b ->1 aba aba ->2 babab babab ->1 abababa

quindi : b ->1 aba ->2 babab ->1 abababa

55sistemi formali / piu'catene di derivabilita' per una stringaATTENZIONE ! lo stesso linguaggio puo’ essere generato con due o piu' sistemi formali diversi

es. le parentesi ben formate I41 possono essere prodotte con:

I41a) A={ (,) } [due simboli] B={ ( ) } [stringa base]P = {p1, p2} [due produzioni:] p1= s ->( s ); p2= s,q -> s q;nota: nella p2 s,q da sole devono essere s.b.f. !

oppure con (produzioni cambiate !!) :

I41b) A={ (,) } [due simboli] B={ ( ) } [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.

56sistemi formali - piu'catene di derivazione per una stringaI41a) A={ (,) } [due simboli] B={ ( ) } [stringa base]P = {p1, p2} [due produzioni:] p1= s ->( s ); p2= s,q -> s q;

I41b) A={ (,) } [due simboli] B={ ( ) } [stringa base]P = {p1, p2, p3} [tre produzioni, che sono:] p1 = s -> ( s ); p2 = s -> s s; p3 = s ( ) t -> s t;

NOTA:nel sistema I41b posso ottenere ( ) ( ) in piu' modi:

cosi' ( ) ->1 (( )) ->2 (( )) (( )) ->3 ( ) (( )) ->3 ( ) ( )

oppure: ( ) ->2 ( ) ( ) (o in altri modi..)

quindi: in generale una stringa di un linguaggio I puo’ avere piu’ derivazioni possibili!

57sistemi formali - piu'catene di derivazione per una stringa

continua I41b) parentesi ben formate: A = { (,) } B = { ( ) } P = { p1: s -> ( s ); p2: s -> s s; p3: q ( ) t -> q t }

una stringa di un linguaggio I puo’ avere piu’ derivazioni possibili !

ancora un esempio 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? ovvero: ( ) ->3 λ e’ ok?

58sistemi formali: derivabilita'

continua I41b) parentesi ben formate A = { (,) } B = { ( ) } P = { p1: s -> ( s ); p2: s -> s s; p3: q ( ) t -> q t }

Esercizio: posso derivare la stringa vuota? ( ) ->3 λ e’ok?

si noti che in generale nelle produzioni del tipo p3: q ( ) t -> q t [con q, t stringhe su A] NON e' necessario che s e q siano ben formate, (questo e' richiesto per la stringa completa q()t, come anche per la s che sta in s-> ...); in particolare queste q e t possono essere stringhe vuote, per cui la risposta e' si, e possiamo derivare ad esempio:

( ) -> 2 ( ) ( ) -> 1 ( ( ) ( ) ) -> 3 ( ( ) ) -> 3 ( ) ->3 λ

59sistemi formali sistema I48 per generare i n*n

prima di presentare il linguaggio I48 che produce i quadrati dei numeri naturali, ricordiamo l'algoritmo seguente per unmodo di calcolare il quadrato di un numero n senza usare il prodotto:

int main () { ( int a,b, conta, n; cout<<"inserisci il valore di n "; cin>>n; a=1; b=1; conta=1; do { conta=conta+1; // valori saranno 1, 2, 3, 4, 5, 6, ... a=a+2; // valori di a saranno 1, 3, 5, 7, 9, 11, ... b=a+b; // valori di b saranno 1, 4, 9, 16, 25, 36, ... } (while conta<n); // ora conta == n e b == n*n; cout<< n <<" al quadrato = " << b <<endl;} // main

60sistemi 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; [corrisponde ad a=a+2;] p2: a x b -> b } [corrisponde ad b=a+b;]

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

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

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” di tipo 1b -produce quindi i quadrati dei numeri naturali,

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

62sistemi 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. Mx inizia con una M, posso raddoppiare la parte x che segue la M (suffisso) e ho Mxx s.b.f.;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.;----------------------------------(*) da "Goedel, Esher, Bach"


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), poiMIIII ->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

si noti che le produzioni p1 e p2 allungano le stringhe, e che le produzioni p3,p4 accorciano le stringhe!

secondo es. di catena di derivazione:

MI ->2 MII ->2 MIIII ->1 MIIIIU ->2 MIIIIUIIIIU ->3 MUIUIIIIU ->3 MUIUUIU ->4 MUIIU ->2 MUIIUUIIU ->4 MUIIIIU ->3 MUUIU ->4 MIU stringa che si ottiene anche con MI ->1 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?

*


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 della regola stessa, [ cioe’ se x -> y allora |x| <= |y| ],

allora si puo' sempre decidere se una stringa e' ben formata con un semplice procedimento ...

-


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 ?

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’ per ogni produzione x -> y allora |x| <= |y| ],

allora il procedimento e': 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)

68sistemi 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’ (perche' non so quante stringhe produrre prima di poter rispondere si o no);

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; nel caso di sistemi formali non monotoni, con regole di produzione che allungano e altre che accorciano le stringhe, in generale NON posso decidere, data una stringa s, se essa e' ben formata oppure no: sistemi formali non decidibili.

osserviamo pero' :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' delle regole di produzione osservabili "dall'esterno" ... ma non appartenenti al sistema MIU !! ... vediamo ...

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

73sistemi formali generativi .. esercizio

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)

74Esercizio: 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)

alcuni esempi:aaaa->1 aaaba ->2 baaababa ->4 beaababa ->4 beeababa ..aaaa->2 aaabaa ->4 aaebaa ->3 abaebaa ->4 abeebaa ->..aaaa->3 aabaa->3 ababaa->3 abababa->4 abebaba->4 abebebaaaaa->4 aaae ->4 aaee ->4 aeee ->4 eeee aaaa->5 beaabe ->4 beeabe -> beeebe (nessuna prod.applicabile)

75

FINE DELLA PRIMA PARTE -

SISTEMI FORMALI GENERATIVI E LINGUAGGI

1 SISTEMI FORMALI GENERATIVI. 2 per capire un' po' le grammatiche dei linguaggi di programmazione e...

Documents

Transcript of 1 SISTEMI FORMALI GENERATIVI. 2 per capire un' po' le grammatiche dei linguaggi di programmazione e...