Sistemi di Lindenmayer

Sistemi di Lindenmayer

Non c’è distinzione tra terminali e non terminali.Tutte le parole derivate da una parola data sono nel linguaggio.Tutte le lettere di una parola sono riscritte simultaneamente.

Motivazione- la descrizione dello sviluppo di organismi filamentosi- le parole rappresentano stadi dello sviluppo di disposizioni di cellule; ogni lettera rappresenta una cellula -le produzioni corrispondono alle istruzioni con cui gli organismi sono generati e sono applicate simultaneamente alle lettere perché lo sviluppo delle cellule è simultaneo negli organismi-non ci sono terminali perché corrisponderebbero a cellule morte; la scomparsa di una cellula è rappresentata dalla parola vuota .Le varie parti di un organismo che si sviluppa possono comunicaretra loro oppure no. Il modello di base di sistema assume che non cisia comunicazione.

Sistemi OL (1)

Un sistema OL è OLS = (V, P0, F), dove V è un alfabeto, P0 è una parola non vuota su V (assioma o parola iniziale), F è un insieme di coppie ordinate (a,P) con a V, P (V+ {} tale che per ogni a V c’è almeno una parola P in (a, P) F (scriveremo a P).

La relazione OLS è definita come segue:

P Q vale se e solo se P = a1 … an, Q = Q1… Qn e ai Qi , n i 1Il linguaggio generato è definito come

L (OLS) = {P | P0 *P} Un sistema OL è deterministico (DOL) se e solo se per ogni a Vc’è esattamente una parola P tale che (a,P) F.Un sistema OL è -free o propagante (POL) se e solo se per ogniproduzione a P in F, P non è .Due sistemi sono equivalenti se generano lo stesso linguaggio.

Sistemi OL (2)

Esempi.

1) OLS = ({a}, a, {a a2 })

L(OLS) = {a2n | n 0}

2) OLS = ({a, b}, a, {a b , b ab})

L(OLS) = {a, b, ab, bab, abbab, bababbab, …} le cui lunghezze sono i numeri di Fibonacci

3) OLS = ({a, b, c}, a, {a abcc , b bcc, c c}) L(OLS) = {a, abcc, abccbcccc, abccbccccbcccccc, …} le cui lunghezze sono i quadrati dei numeri naturali.

Nota bene.Tutti i sistemi sono DOL e generano linguaggi contestuali.

Sistemi OL (3)

Esempio (alga rossa).

1) Prendiamo il sistema DOL propagante con alfabeto e produzioni come in tabella

1 2 3 4 5 6 8 ( )

2 3 2 2 4 504 6 7 8(1) ( )

Le parole derivate dall’assioma P0= 1 sono

P0= 1 P1= 2 3 P2= 2 2 4 P3= 2 2 504 P4= 2 2 60504

P5= 2 2 7060504 P6= 2 2 *(1)07060504

Pn+6 = 2 2 8(Pn)08(Pn-1) 0 … 08 P0 07060504

Sistemi OL (4)

Rappresentazione

Le espressioni parentesizzate sono rami la cui posizione è indicata dagli 8. Gli 0 sono rappresentati come pareti oblique alternativamenteinclinate a destra e a sinistra. I rami sono attaccati alternativamente suun lato e sull’altro del ramo dove nascono. I simboli sonorappresentati come pareti verticali.

2 2 8

22

4

3

Proprietà dei linguaggi OL (1)

Chiamiamo anti-AFL una famiglia di linguaggi che non è chiusa perunione, concatenazione -free, omomorfismi -free, omomorfismoinverso, intersezione con i linguaggi regolari.

Teorema. La famiglia dei linguaggi OL è anti-AFL.

Teorema. La famiglia dei linguaggi OL è chiusa sotto immaginespeculare.

Prova. Se un linguaggio è generato dal sistema (V, P0, F), la suaimmagine speculare è generata dal sistema (V, mi(P0), mi(F)) dovemi(F) è ottenuto da F sostituendo le parti destre delle loro produzionicon le loro immagini speculari.

Proprietà dei linguaggi OL (2)

Teorema. Ogni linguaggio OL è contestuale.

Prova. Sia L generato dal sistema OL H = (V, P0, F). Prendiamo lagrammatica G = ({X0, X1, X2, X3}, V, X0, F1) dove F1 consiste delleproduzioni

X0 X1 P0 X1 X1 X1a X1 X2 a per ogni a VX2 X1 X3 X1 a X3 X3 a per ogni a VX1 X3 X1

X2a P X2 per ogni produzione a P in F

Si dimostra che L(G) = L(H).

Proprietà dei linguaggi OL (3)

Esempio. Prendiamo il sistema OLS = ({a,b}, a, {a b, b abLa grammatica contestuale che lo genera è G = ({X0, X1, X2, X3},{a,b}, X0, F1) dove F1 consiste delle produzioni

X0 X1 a X1

X1 X1a X1 X2 a X1b X1 X2 b

X2a b X2 X2b ab X2

X2 X1 X3 X1

a X3 X3 a b X3 X3 b

X1 X3 X1

Sistemi TOL (1)

Un sistema TOL è H = (V, P0, T) dove V e P0 sono come nei sistemiOL e T è una collezione di sottoinsiemi di V (V+ {}. Ogni t T soddisfa la condizione: per ogni a V c’è P (V+ {}) tale che t contiene la coppia (a, P)

P Q se e solo se esiste k 1, lettere a1 , … , ak, parole Q1 , … , Qk

e t contiene la coppia (ai, Qi) per k i 1.

Il linguaggio generato è

L (H) = {P | P0 *P}

Motivazione.A ogni passo si usano solo le produzioni appartenenti a una stessa tabella. La motivazione biologica è che a stadi differenti di sviluppodell’organismo possono servire insiemi di regole differenti.

Sistemi TOL (2)

Esempio. Prendiamo il sistema H = ({a}, a, {{a a2}, {a a3}}).Si ha L(H) = {ai | i = 2m3n, m,n 0.L(H) non è un linguaggio OL.

Teorema. I linguaggi OL sono contenuti propriamente nei linguaggiTOL.

Sistemi 1L e 2L (1)

Un sistema 2L è H = (V, P0, a0, F) dove:- V e P0 sono come nei sistemi OL- a0 V è l’input dall’ambiente- F è un sottoinsieme di V V V (V+ {}tale che per

tutte lelettere a, b, c V (non necessariamente distinte) c’è una parola P V+ {} tale che F contiene la quadrupla (a,b,c,P).

P Q se e solo se esiste n 1, lettere a1 , … , an, parole Q1 , … , Qn

tali che F contiene le quadruple (a0, a1, a2, Q1), …, (ai-1, ai, ai+1, Qi), …, (an-1, an, a0, Qn) per n-1 i 2

P = a1…an e Q = Q1…Qn.

Per n= 1 F contiene la quadrupla (a0, a1, a0, Q1).

Il linguaggio generato da H è L(H) = {P | P0 *P}.

Sistemi 1L e 2L (2)

Un sistema 2L è un sistema 1L se e solo se vale una delle condizioniseguenti:- per ogni a, b, c, P F contiene la quadrupla (a,b,c,P) se e solo se

contiene la quadrupla (a,b,d,P) oppure- per ogni a, b, c, P F contiene la quadrupla (a,b,c,P) se e solo se

contiene la quadrupla (d,b,c,P).

Sistemi 1L e 2L (3)

Teorema. C’è un linguaggio 1L che non è OL e c’è un linguaggio 2L che non è 1L.