7/21/2019 PDF Document (92329)

1/125

7/21/2019 PDF Document (92329)

2/125

7/21/2019 PDF Document (92329)

3/125

7/21/2019 PDF Document (92329)

4/125

7/21/2019 PDF Document (92329)

5/125

7/21/2019 PDF Document (92329)

6/125

7/21/2019 PDF Document (92329)

7/125

7/21/2019 PDF Document (92329)

8/125

7/21/2019 PDF Document (92329)

9/125

7/21/2019 PDF Document (92329)

10/125

7/21/2019 PDF Document (92329)

11/125

7/21/2019 PDF Document (92329)

12/125

7/21/2019 PDF Document (92329)

13/125

7/21/2019 PDF Document (92329)

14/125

7/21/2019 PDF Document (92329)

15/125

7/21/2019 PDF Document (92329)

16/125

7/21/2019 PDF Document (92329)

17/125

7/21/2019 PDF Document (92329)

18/125

7/21/2019 PDF Document (92329)

19/125

7/21/2019 PDF Document (92329)

20/125

7/21/2019 PDF Document (92329)

21/125

7/21/2019 PDF Document (92329)

22/125

7/21/2019 PDF Document (92329)

23/125

7/21/2019 PDF Document (92329)

24/125

7/21/2019 PDF Document (92329)

25/125

7/21/2019 PDF Document (92329)

26/125

7/21/2019 PDF Document (92329)

27/125

7/21/2019 PDF Document (92329)

28/125

7/21/2019 PDF Document (92329)

29/125

7/21/2019 PDF Document (92329)

30/125

7/21/2019 PDF Document (92329)

31/125

7/21/2019 PDF Document (92329)

32/125

7/21/2019 PDF Document (92329)

33/125

7/21/2019 PDF Document (92329)

34/125

7/21/2019 PDF Document (92329)

35/125

7/21/2019 PDF Document (92329)

36/125

7/21/2019 PDF Document (92329)

37/125

7/21/2019 PDF Document (92329)

38/125

7/21/2019 PDF Document (92329)

39/125

7/21/2019 PDF Document (92329)

40/125

7/21/2019 PDF Document (92329)

41/125

7/21/2019 PDF Document (92329)

42/125

7/21/2019 PDF Document (92329)

43/125

7/21/2019 PDF Document (92329)

44/125

7/21/2019 PDF Document (92329)

45/125

7/21/2019 PDF Document (92329)

46/125

7/21/2019 PDF Document (92329)

47/125

7/21/2019 PDF Document (92329)

48/125

7/21/2019 PDF Document (92329)

49/125

7/21/2019 PDF Document (92329)

50/125

Decima Seconda Lezione14/11/2006

Tremi sulle Derivazioni e gli Alberi di derivazioneDerivazioni estreme (a sx. e a dx.) Grammatiche Branching

TEOREMA1.3 (rif.D.S. W . pag. 274): Se una grammaticaC.F. positiva e risultaS w

allora vi un

albero di derivazione perw in.

DIM.: Si dimostra per induzione sulla lunghezza della derivazione diw daS in.

Passo base: 1m = , ci corrisponde a dire cheS w = (per 1m = non ci sono produzioni) elalbero di derivazione richiesto rappresentato da un unico vertice etichettato conS ;

N.B.: A lezione, nel passo base della dimostrazione per induzione, stato considerato, giustamente, il

caso 2m = , si ha quindiS w , cio in ci deve essere una produzione 1 2 nS w = elalbero sar fatto cosi:

Seguendo la dimostrazione del libro il passo in cui2m = pu essere visto come passo successivo (secon-do caso base) a 1m = , dove le foglie rappresentano sottoalberi.

Passo induttivo: ipotizzando che per derivazioni diw daS di lunghezzaq noto lalbero di deri- vazione, dimostriamo che ci vale anche per derivazioni diw da S di lunghezza 1q + in , cioche esiste lalbero di derivazione diw da S in per derivazioni di lunghezza 1m q = + . Si ha

quindi:1m q m

S v w

= =

, con ( ),v w V T . Applicando lipotesi di induzione suS v

si ha che

esiste un albero di derivazione div da S in . Scrivendo orav w

(ricordando la definizionedata peru v

rif. D.S. W . pag. 269) si ha chev x X y = e 1 2 k

h

w x y = ( X V ,

( )h V T

). contiene la produzione 1 2 k X , come gi detto lalbero di derivazio-ne div noto per lipotesi di induzione, mentre lalbero di derivazione diw si costruisce a par-tire dallalbero di derivazione div aggiungendo un sottoalbero rappresentante la derivazione

v w

che sappiamo costruire sempre per lipotesi di induzione ( 1m q < + , per la precisione2m = , che come abbiamo poco fa visto nella nota riguardante il caso 2m = , a fortiori sappia-

mo costruire). Tale sottoalbero ha chiaramente radice etichettata con X . Il teorema dunquedimostrato.

S

1 2 n

7/21/2019 PDF Document (92329)

51/125

EDIT by Qd Grammatiche - XII Lez.

49

Graficamente abbiamo:

DEF.: con la scrittura l u v indichiamo che esiste una produzione in X z , conu x X y = e v x z y = , ( ) y V T e x T .

Mentre la sequenza1 2l l l nu u u dettaderivazione estrema a sinistra .

Tale tipo di derivazione si ottiene applicando produzioni solo alle variabili che si trovano allestrema si-nistra della stringa del tipou xXy = , abbiamo dunque: l x X y x z y , dove xzy v = . Poichz de-riva da X , ovvio che x non pu essere una variabile altrimenti si otterrebbe una derivazione qualsiasi, in- vece, essendo una derivazione estrema a sinistra, deve essere prodotta la prima variabile a sinistra, che nelnostro caso X V ( x T e ( ) y V T ), sez un terminale allora le successive derivazioni e-streme a sinistra si applicheranno a y che potrebbe contenere variabili. Una derivazione estrema a sinistra (rif.D.S. W . pag. 274, 1):

l l l l l l S a X bY aa X bY aaa X bY aaaab Y aaaabb Y aaaabbb

Larchetto identifica la prima variabile alla sinistra della stringa sulla quale si applica la produzione.

DEF.: Viceversa la scrittura r u v indica che esiste una produzione in X z , conu x X y = e v x z y = , ma, rispetto alla definizione precedente, risulter:( ) x V T e y T .

Analogamente la sequenza:1 2r r r nu u u dettaderivazione estrema a destra .

Dualmente rispetto a prima, in questo caso, vengono prodotte le variabili che si trovano allestrema de-stra della stringa come si pu evincere dallesempio analogo a quello visto prima:

r r r r r r S aXb Y aXbb Y a X bbb aa X bbb aaa X bbb aaaabbb

Come si pu evincere vengono prodotte soltanto le variabili allestrema destra.

Per completezza vediamo un terzo esempio di derivazione:,l r l r l r l S a X bY aaXb Y aa X bbY aaaXbb Y aaa X bbb aaaabbb

Questa derivazione non n estrema a sinistra n estrema a destra, essendo costituita sia da derivazioniestreme a sinistra che estreme a destra. Da notare che, come nei due esempi precedenti, la prima deriva-zione ( ,l r S a X bY ) estrema sia a sinistra che a destra.

TEOREMA (rif.D.S. W . pag. 275) Dato un albero di derivazione perw T si pu ottenere una de-rivazione estrema a sinistra (a destra) diw daS , quindiw = .

DIM.: Si costruisce una dimostrazione per induzione sulla lunghezza della derivazione.

S

x X y x X y

1 w

v

2 k

7/21/2019 PDF Document (92329)

52/125

EDIT by Qd Grammatiche - XII Lez.

50

Con la stringa: 0 1 1 2 r r v X v X X v (con 0 1, , , r v v v T e 1 2, , , r X X X V )(notazioni alternative indicanoq in luogo dir )

indichiamo la parola che si legge da sinistra a destra lungo lalbero di derivazione nei vertici sucimmediati della radiceS .

Come gi definito i simboliv rappresentano stringhe terminali, mentre i simboli X sono le etichette dei vertici 1 2, , , n immediati successori della radiceS di (da non confondere il simbolov con ilsimbolo ).

Passo base:( ) 0q r = = , produzione priva di variabili.Stiamo ipotizzando il caso in cui non esistano deri- vazioni con lunghezza maggiore di 2 e cio che le derivazioni di lunghezza 2 non generino stringhe che conte

variabili ma soltanto terminali.Ovviamente in questo caso si ha immediatamenteS w , conw T , 0w v = e 0r = ( facileevincere ci osservando lalbero appena mostrato, escludendo i nodi etichettati con le variabili X , in quanto assen-ti nella produzione del passo base, e chiaramente le stringhe0 1, , , r v v v devono essere viste come ununica stringache in questo caso indicata con0v ).In questo caso facile osservare chel S w , ma anche r S w , la derivazione dunque e-strema sia a sinistra che a destra. Il caso base dunque dimostrato;

Passo induttivo: ipotizzando( ) 0q r = > , cio che la produzione contenga almeno una variabile X . Consideriamo gli alberii i

= con 1, 2, ,i r = . Con questa notazione indichiamo legrammatiche i che hanno come assiomii X , rappresentano in pratica sottoalberi di le cuiradici sono etichettate coni X e le cui foglie sono etichettate con 10 , , , ni i i w w w ( 10 ni i i i w w w w = ). La parola che si ottiene dalla derivazione dellalbero principale sar

0 1 1 2 r r w v w v w w v = .

Presupponendo vero il teorema per un certo0r > , partendo da i si ha l i i X w e r i i X w ,con 1 i r , ipotizzando vera lultima affermazione fatta (ipotesi di induzione) possiamo giu

S

0 0 01 2

0

n

v v v v

1 X

n

1 1 11 2

1

mv v v v

2 X

r X 1 2r r r p

r

v v v

v

1 2 r

7/21/2019 PDF Document (92329)

53/125

EDIT by Qd Grammatiche - XII Lez.

51

gere alla tesi del teorema (su una lunghezza della derivazione maggiore dir ) e cio che l S w e

r S w , e pi esplicitamente che

1 1 2

1 1 2

1 1 2

1 1 2

l o r r

l o r r

l o r r

l o r r

S v X v X X v

v w v X X v v w v w X v

v w v w w v w =

e

1 1 2

1 1 2

1 1 2

1 1 2

r o r r

r o r r

r o r r

r o r r

S v X v X X v

v X v X w v

v X v w w v

v w v w w v w =

Da S si ottiene una derivazione estrema sia a sinistra che a destra. Tale conclusione delteorema si ottiene applicandoricorsivamente i due passi dellinduzione.

TEOREMA1.4(non dim): Sia una grammaticaC.F. positiva con simbolo inizialeS e terminaliT . Al-lora i seguenti enunciati sono equivalenti:1. ( )w L ;2. esiste un albero di derivazione perw in;3. c una derivazione estrema a sinistra diw daS in;4. c una derivazione estrema a destra diw daS in;

DEF.: Una grammaticaC.F. positiva dettabranching(ramificata o ramificante di Chomsky ) se nonha produzioni della forma X Y , con , X Y V .

Lalbero di derivazione di tale grammatica ha vertici che, se non sono foglie, non sono unici, nel sensoche ogni vertice non pu avere un solo figlio, ammenoch questo figlio non sia una foglia.TEOREMA1.5: Vi un algoritmo per ottenere, da una grammatica C.F. positiva, una gramma-

tica C.F. positiva e ramificante tale che si ha linvarianza( ) ( )L L = .

La dimostrazione segue alla lezione successiva.

7/21/2019 PDF Document (92329)

54/125

Decima Terza Lezione17/11/2006

teoremi sulla grammatica Branching e in Chomsky Normal FormPumping Lemma propriet di chiusura

Grammatiche Ambigue e Grammatiche Regolari

DIM.: Supponiamo prima il caso in cui contenga delle produzioni cicliche del tipo:1 2, X X 2 3 1, , k X X X , chiaramente con1 2, , , , 0k X X X V k > .

1. Il primo passo consiste nelleliminare le produzioni cicliche, e sostituendo, ad ogni variabili X rimanente, il nuovo simbolo X V .

Da notare che facendo queste sostituzioni il linguaggio generato non cambia, in quanto ad esempio:1Y X e 1 2 1, , k X X X X , tale sequenza d gli stessi risultati di 1Y X , possiamo dunque e-

liminare il ciclo e rimpiazzare1 X con X .

Se una variabilei X S = (cio se un assioma) allora porremo X S = .

Ora supponiamo il caso in cui non contenga produzioni cicliche, in tal caso si passa al secon-do passo.

2. Per ottenere da una grammatica branching non deve contenere produzioni del tipo X Y tali cheY Z (cioY non deve essere una variabile, ma un terminale ).L dove risultaY x e X Y con ( ) x V T , si eliminano tali produzioni e le si rim-piazza con X x , si ripete tale procedura fintantoch 1 x = e x V , proprio perch si vuoleottenere, non modificando il linguaggio generato, una grammatica branching ( X Y nonammesse, mentre sono ammesse ad esempio X YZ ).

Ripetendo il passo 2 pi volte si otterr una grammaticaC.F. positiva e ramificata.

DEF.: con la dicituraChomsky Normal Form( forma normale di Chomsky ) si indica una grammaticaC.F. con variabiliV e terminaliT e ogni sua produzione ha una delle forme seguenti:YZ oppu-re X a , con , , X Y Z V e a T .

TEOREMA3.1: Vi un algoritmo che permette di trasformare una grammaticaC.F. positiva in unagrammaticaC.N.F. (Chomsky Normal Form), tale che il linguaggio generato non cambia, quind

( ) ( )L L = .

DIM.: Per il teorema precedente possiamo supporre che sia una grammatica branching senza che ladimostrazione perda di generalit.

1.1. Per ogni simboloa T , si introduce la variabilea X ;

1.2. Si modifica rimpiazzando ogni produzione x (dove x non un singolo terminale)con la produzione X x , tale x si ottiene da x sostituendo ad ogni terminalea la va-riabile a X ;

7/21/2019 PDF Document (92329)

55/125

EDIT by Qd Grammatiche - XIII Lez.

53

Quindi se si ha X x e x aa = si ottiene , a a X x x X X = .

2. Si aggiungono tutte le produzionia X a .

Chiaramente il linguaggio generato dalla grammatica ottenuta dai passi appena descritti la stes( )L e avr produzioni del tipo (ma non ancora una grammatica inC.N.F.):

I) 1 2 k X X X X con 1k > (del resto avevamo ipotizzato branching) pi precisamente si ha X x con 1 2 k x X X X = , x non un singolo terminale per questo2k ;

II) X a .

1 2, , , , k X X X X sono variabili mentrea un terminale.

Al fine di ottenere una grammatica inC.N.F. bisogna eliminare tutte le produzioni I) con2k > , infattilaC.N.F. deve avere produzioni con (soltanto) due variabili, a tal fine si introduce un nuovo tipo diriabile: Z che utilizzeremo in questo modo:

1 1

1 2 2

3 2 2

2 1

;;

;k k k k k k

X X Z Z X Z

Z X Z Z X X

Con questo stratagemma otteniamo una grammaticaC.N.F. tale che ( ) ( )L L = .

DEF. (accenno, rif.:D.S. W . pag. 287, ex. 3): Si dice grammaticaC.F. in forma normale di Greibach unagrammatica che ha ogni produzione nella forma: 1 2 k X aY Y Y con 0k , a T e

1 2, , , , k Y Y Y V .

TEOREMA4.1 Pumping Lemma(non dim.): tale lemma visto per i linguaggi regolari pu essere e-steso alle grammaticheC.N.F. in questo modo, sia una grammaticaC.N.F. con n variabili e sia

( )L L= , allora x L tale che 2n x = si ha che 1 1 2 2 x r q r q r

= dove:

[ ] [ ]

1 2

1 2

1 1 2 2

1. 2 ;2. 0;3. 0

n

i i

q r q q q

i r q r q r L

TEOREMA4.2 (rif.D.S. W . pag. 290 non dim.): Il linguaggio [ ] [ ] [ ]{ }| 0n n nL a b c n= > non C.F.Chiaramente sen avesse un limite superiore alloraL sarebbeC.F., ma qui stiamo considerando il caso in

cuin possa assumere qualsiasi (tutti) valore positivo non nullo.

Risolvendo il seguente esercizio(rif.D.S. W . pag. 290, ex. 1) si scopre che anche le grammaticheC.F. han-no dei limiti: mostrare che [ ]{ }| un numero primoi L a i = non C.F. Tale fatto si pu dimostrare i-

7/21/2019 PDF Document (92329)

56/125

EDIT by Qd Grammatiche - XIII Lez.

54

potizzando cheL siaC.F., possiamo applicare il pumping lemma, si ha che(punto 3. del lemma): 0k [ ] [ ]

1 1 2 2k k rq rq r L, ma ci non possibile 0k in quanto non avremmo sempre ripetizioni dia pari ad

un numero primo. La contraddizione ci conduce ad affermare cheL non C.F.

PROPRIET DI CHIUSURAper i linguaggiC.F.

Mostriamo tali propriet analogamente a come si fatto per i linguaggi regolari.

TEOREMA5.1: se 1L ed 2L sono due linguaggiC.F. allora 1 2L L un linguaggioC.F.

DIM.: Supponiamo che1L sia un linguaggio generato dalla grammaticaC.F. 1 ed 2L il linguaggio ge-

nerato dalla grammaticaC.F. 2 , si ha quindi ( )1 1L L= ed ( )2 2L L= , inoltre supponiamo che1 e 2 abbiano insiemi di variabili disgiunti fra loro, si ha quindi1 2V V = (con questultima posizione non vi perdita di generalit della dimostrazione del teorema in quanto ci che interessa come risultato finale sono i termcio i linguaggi e non le parti costituenti le grammatiche).Ora supponiamo che1S ed 2S siano rispettivamente i simboli iniziali di1 e 2 . Definiamo unagrammatica C.F. che ha come insieme di variabili { }1 2V V S e simbolo inizialeS .

Questo modo di dimostrare il teorema si basa sullo stesso approccio utilizzato per i teoremi sui linguaggiregolari, in quel caso cercavamo di costruire automi (riconoscitori ) mentre adesso cerchiamo di costruiregrammatiche ( generatrici ).

Aggiungiamo due nuove produzioni a: 1S S e 2S S . In conclusione la grammatica costruita generatrice sia di1L che di 2L , infatti ( ) ( ) ( )1 2L L L = da cui ( )1 2L L L = .

Ricordiamo che dire che un dato linguaggio C.F. vuol dire che esiste una grammatica che la genera,quindi nel caso di questa dimostrazione bastato trovare unopportuna grammatica che generasse il lin-guaggio ( ) ( )1 2L L .

TEOREMA5.2:Ci sono linguaggiC.F. 1L ed 2L tali che 1 2L L non un linguaggioC.F. In al-tre parole il teorema ci assicura che la classe dei linguaggiC.F. non chiusa rispetto allintersezione.

DIM.: la dimostrazione consiste nel trovare (almeno) un esempio di linguaggio che non C.F. che sta-to ottenuto dallintersezione di due linguaggiC.F., quindi consideriamo:

1 , grammaticaC.F. con le produzioni: | , |S Sc Xc X aXb ab tale grammatica genera il linguaggioC.F.: [ ] [ ] [ ]{ ( )1 1| , 0n n mL a b c n m L= > = ;

2 , grammaticaC.F. con le produzioni: | , |S aS aX X bXc bc tale grammatica genera il linguaggio C.F.: [ ] [ ] [ ]{ ( )2 2| , 0m n nL a b c n m L= > = .

chiaro che il linguaggio [ ] [ ] [ ]{1 2 | 0n n nL L a b c n = > non C.F. (teorema 4.2, conseguenza del pumping lem-ma), tale risultato ci sufficiente per ritenere dimostrato il teorema.

7/21/2019 PDF Document (92329)

57/125

EDIT by Qd Grammatiche - XIII Lez.

55

COROLLARIO5.3: non vi chiusura, per la classe dei linguaggiC.F., neanche per loperazione dicomplemento, infatti: vi (almeno) un linguaggioC.F. L A tale che A L non C.F.

DIM.: Si adoperano le leggi di De Morgan (rif.D.S. W . pag. 2 -( ) ( )

R S R S = ) e possiamo scrivere:

( ) ( )1 2 1 2 1 2 1 2L L L L A L L A A L A L = = =

con lausilio del teorema 5.1 e del teorema 5.2 se ne deduce che il complemento di un linguaggioC.F. non C.F. infatti, se (per assurdo) neghiamo la tesi del teorema, cio assumiamo che A L siaC.F.allora, per il teorema 5.1 potremmo affermare che, posto( ) ( )1 2H A L A L = , H C.F. Prose-guendo la dimostrazione per assurdo potremmo affermare anche che A H C.F., ma A H , come visto poco fa uguale a1 2L L che, per il teorema 5.2 non C.F. (contraddizione), quindi il comple-

mento di un linguaggioC.F. non , in generale,C.F.

DEF. (rif.D.S. W . pag. 280): Una grammaticaC.F. dettaregolare se ogni sua produzione ha una delledue forme:U aV oppureU a , conU eV variabili ea terminale.

TEOREMA2.1. (non dim.): SeL un linguaggio regolare, allora vi una grammatica regolare taleche ( )L L= oppure ( ) { }0L L= .

TEOREMA2.2. (non dim.): Se una grammatica regolare allora il linguaggio( )L generato da

gamma regolare.COROLLARIO2.4 (non dim.): Ogni linguaggio regolare C.F. chiaro che il contrario non vale (non vero

che ogni linguaggioC.F. regolare).

DEF. (rif.D.S. W . pag. 300): Una grammaticaC.F. dettaambigua se esiste una parola ( )u L cheha due derivazioni estreme a sinistra.Una grammaticaC.F. che non ambigua anche dettanon ambigua .

Esempio (rif.D.S. W . pag. 303): consideriamo la grammatica con le seguenti produzioni:

| , , ,S XY YX Y ZZ X a Z a

consideriamo la parola ( )aaa L , tale parola ha due derivazioni estreme a sinistra, infatti, si ha:

1. l l l l l S XY aY aZZ aaZ aaa 2. l l l l l S YX ZZX aZX aaX aaa

Le due derivazioni hanno i seguenti alberi di derivazione:

7/21/2019 PDF Document (92329)

58/125

EDIT by Qd Grammatiche - XIII Lez.

56

Tale ambiguit viene risolta mediante lutilizzo delle parentesi, per mezzo delle quali possibillire in maniera univoca alla derivazione. In effetti i due alberi coincidono. Quindi la stringa proddalla derivazione 1. verr indicata come( )a aa , mentre la stringa della derivazione 2. verr indicata co-

me ( )aa a . In questo modo lalbero di derivazione (unico) pu essere utilizzato per risalire univocamte alla derivazione.

S

X Y

a

aa

Z Z

1

Z

a

S

Y X

a

Z a

2

7/21/2019 PDF Document (92329)

59/125

Decima Quarta Lezione21/11/2006

Grammatiche Separatrici teorema sulla Grammatica Regolare Automi a Pila

Riprendendo dallesercizio della lezione precedente, possiamo riscrivere le produzioni della gratica in questo modo: ( ) [ ] { }| , , ,S X Y Y X Y Z Z X a Z a . Le produzioni che posso-no indurre ad ambiguit devono essere provviste di parentesi distinte (differenti tra loro). La stringaaa si otterr nei due casi visti prima cos:

1. ( ) ( ) ( ){ } ( ){ } ( ){ }S X Y a Y a Z Z a a Z a a a 2. [ ] { } { } { } { }S Y X Z Z X a Z X a a X a a a

Il risultato concettualmente identico, ma non ambiguo, in questo modo ogni stringa pu esprodotta da ununica derivazione. I relativi alberi di derivazione sono i seguenti:

Luso delle parentesi essenziale per evitare ambiguit, un esempio dato nellambito algebrico dei con-nettivi logici in cui( ) ( )a b c a b c .

Partendo dal concetto di grammatica ambigua e luso delle parentesi si arriva alla seguente:DEF. (rif.D.S. W . pag. 303): Sulla base di una grammatica C.N.F. con terminaliT e produzioni:

i i i X Y Z e V a con 1,2, ,i n= e a T

Costruiamo una nuova grammaticaS tale che i suoi terminai siano i terminali di assieme ad altri2n simboli (i e )i , quindi il nuovo insieme ricavato daT { }( , ) | 1,2, ,S i i T T i n= = .

Le produzioni della nuova grammaticaS saranno identiche a quelle di se della formaV a , men-tre le produzioni di del tipo i i i X Y Z , in S assumeranno la forma: ( )i i i i i Y Z per

1,2, ,i n= .

La grammaticaS appena definita prende il nome di grammatica separatrice (si dice anche cheS ilseparatore , ogni sua produzione ha una coppia distinta di parentesi).

S

( ) X Y

( )a

a

{ } Z Z

( )1

[ ]Y

{ }[ a { }a

S( )2

X

a{ }[ Z ] Z

]a

7/21/2019 PDF Document (92329)

60/125

EDIT by Qd Grammatiche - XIV Lez.

58

ovvio comprendere che da una grammaticaS possibile ricavare la grammatica, basta, infatti, e-liminare dalle sue produzioni i simboli delle parentesi (i e )i .

Ora che conosciamo la nozione di grammatica separatrice. Aggiungendo alla grammatica.1es , mo-

strata nellaIXlezione, le produzioni:;

;;

S S connettivo S connettivo e connettivo oppure connettivo ma

Possiamo ottenere la stringa:v = un gatto corre e un topo canta oppure un gatto cantaottenibili nonda ununica derivazione e trasformando tale grammatica in una grammatica separatrice otterremmoderivazione univoca.

TEOREMA2.3 (rif.D.S. W . pag. 282 non dim.): Un linguaggioL regolare se e solo se vi una gram-matica regolare tale che ( )L L= oppure ( ) { }0L L= .

Tale teorema rappresenta una caratterizzazione dei linguaggi regolari in termini generativi (per gli auto-mi tale caratterizzazione era fatta in termini di riconoscimento).

Ora viene mostrato uno schema che illustra e localizza gli argomenti studiati sin ora e alcuniancora trattati:

Algoritmi:Linguaggi: Riconoscimento Generazione

Regolari Automi Finiti Grammatiche RegolariC.F.Context Free Automi a Pila GrammaticheC.F.

Le grammatiche regolariC.F. generatrici di linguaggi regolari hanno produzioni con una sola variabile eun solo terminale (questo fatto fa intuire come una grammatica di questo tipo riesca asimulare in qualchemodo il comportamento dellautoma finito).

dimostrato che la classe dei linguaggi regolari inclusa propriamente(propriamente perch esiste alme-

no un linguaggioC.F. che non regolare)nella classe dei linguaggiC.F.: R C.F.C C . Del resto il corollario 2.4dice proprio che ogni linguaggio regolare ancheC.F., ma il viceversa non vale come dimostrato dal te-orema 1.1(rif.D.S. W . pag. 270) in cui viene fatto un esempio di linguaggioC.F. che non regolare.

Si introduce ora il concetto diautoma a pila (o pushdown) che unentit matematica (pi potentedegli automi finiti) in grado di riconoscere i linguaggiC.F. (quindi anche i linguaggi regolari, per quantodetto poco fa), che, oltre ad avere le propriet degli automi finiti (tradizionali) possiede una mem( pila o stack ) per memorizzare i dati ( push) o eliminarli ( pop) durante la lettura dellipotetico nastro.Formalmente diamo la seguente:

DEF.: Lautoma a pila rappresentato da un insieme di stati{ }1 2, , mQ q q q = , con 1q stato inizia-le, F Q insieme degli stati finali (o di accettazione), A lalfabetousuale (il nastro costituito da parole diquesto alfabeto), un altro alfabeto dettoalfabeto pila ( pushdown) . Introduciamo un nuovo simbolo0 il

7/21/2019 PDF Document (92329)

61/125

EDIT by Qd Grammatiche - XIV Lez.

59

quale non appartiene n allinsieme A, n allinsieme , scriveremo quindi 0 A e 0 con{ }0 A A= e { }0 = .

DEF. (rif.D.S. W . pag. 310): Pertransizione di un automa a pila si intende la quintupla: :i j q a q i

con a A e , i . La transizione si interpreta in questo modo:

1. i q rappresenta lo stato in cui si trova lautoma a pila prima della lettura del simboloa ;2. a il simbolo che viene letto dallautoma se 0a , altrimenti non viene letto nulla;3. h il simbolo che viene estratto ( pop) dalla pila se 0 , altrimenti non viene estrat-

to nulla;4. i il simbolo che viene inserito ( push) nella pila se 0 , altrimenti non viene in-

serito nulla;5. j q lo stato in cui transiter lautoma dopo la transizione.

Come detto se 0a = non verr letto alcun simbolo sul nastro (ovvero lautoma non si sposter lungo il nastro per leggere il simbolo), il fatto che 0a = non vieta allautoma di eseguire eventuali opera-zioni di pop e di push e di transitare eventualmente in un altro stato.

DEF.: Un automa a pila viene specificato da un numero finito di transizioni.

Il simbolo 0 rende, in qualche modo, lautoma a pila non deterministico. Difatti se 0a = lautomapotrebbe comunque transitare in un altro stato, anche pi di una volta, imitando, in questo modo, che avviene negli automi finiti non deterministici (i quali possono leggendo un solo simbolo tran

in pi stati contemporaneamente).DEF.: Date le seguenti transizioni: :i j q a q i e :i k q b q k se distinte tra loro(ovvero se c

almeno un elemento delle due quintuple che le distingue), esse vengono detteincompatibili se si verifica una delleseguenti condizioni:

1. a b= e =j (in questo caso viene letto due volte lo stesso simbolo e viene fattoil pop dello stesso simbolo due volte);

2. a b= e 0= oppure 0= (viene letto due volte lo stesso simbolo e in una delle due transizioni non viene fatto il pop);

3. =j e 0a = oppure 0b = (viene fatto il pop due volte dello stesso simbolo e in una delle due transizioni non viene letto alcun simbolo);

4. 0a = oppure 0b = e 0= oppure 0= (in una delle due transizioni non viene lettoalcun simbolo e in una delle due transizioninon viene effettuato il pop);

DEF.: Un automa a pila si dicedeterministico se non possiede coppie di istruzioni incompatibili.

La definizione appena data giustificata dal fatto che con istruzioni incompatibili non assicurato il de-

terminismo dellautoma.

7/21/2019 PDF Document (92329)

62/125

EDIT by Qd Grammatiche - XIV Lez.

60

DEF.: Postou A ed un automa pushdown. Con il termineu-configurazione per indi-chiamo la tripla ( ), ,i k q = dovek un intero 1 1k u + , i q uno stato di ed

unastringa dellinguaggio pushdown ( una sequenza di simboli contenuti nella pila, che in caso pu an-che essere vuota, per via della stella), mentreu rappresenta la stringa letta dallautoma.

Intuitivamente una u-configurazione rappresenta una situazione nella quale: u scritto nel nastro di ; osserva ilk -mo simbolo della stringau; Se 1k u= + la computazione di terminata durante la u-configurazione ; i q lo stato in cui si trova durante la u-configurazione ; la stringa di simboli nella pila dellautoma durante la u-configurazione ; Se 0 = allora la pila vuota nella u-configurazione .

DEF.: Nel caso dellautoma a pila non deterministico, per una coppia di u-configurazioni scriv

mo: ( ) ( )|: , , , ,i j u k q l q se contiene una transizione :i j q a q i , dove =h e =i , con e:

1. l k = e 0a = ;oppure

2. 1l k = + e ilk -mo simbolo diu a .

Da notare che il push (pop) viene fatto inserendo (estraendo) nella stringa della pila un simbolo alla vol-ta da sinistra, ad esempio, inserendoB nella pila in cui c A, si ha:B A.

Chiaramente se 0= oppure 0= si avr rispettivamente = oppure = .

In effetti il simbolo| serve a descrivere il passaggio da una configurazione allaltra di un atoma pushdown nella lettura di un simbolo (0 compreso).

DEFF.: una successione1 2, , , m dettau-computazione di se valgono le seguenti condi-zioni:

1. ( )1 1, ,0q = (per unq Q , lo stack vuoto e viene letto il primo simbolo diu, lo stato non necessariamente quello iniziale);

2. ( )1, ,m u p = + con p Q e

3.

1|: i i u + con 1 i m < .La prima condizione rappresenta il passo iniziale dellau-computazione, la seconda condizione rap-

presenta il passo finale, mentre la terza condizione rappresenta i passi intermedi dellau-computazione.

Lau-computazione appena vista detta diaccettazione se:

1. lo stato p a m uno stato di accettazione;2. lo statoq a 1 lo stato iniziale1q ;3. la pila a m vuota.

Diremo cheu accettata da se vi unau-computazione di accettazione di .

7/21/2019 PDF Document (92329)

63/125

EDIT by Qd Grammatiche - XIV Lez.

61

Con ( )L indichiamo linsieme di stringhe accettate da ovvero il linguaggio accettato : ( ) { }| , accettaL u u A u= (rif.D.S. W . pag. 320).

Nellesempio che segue si mostra come gli automi a pila siano capaci di riconoscere linguagg

regolari.Esempio 1 (rif.D.S. W . pag. 312 ex.1): sia 1 un automa a pila, lalfabeto dellautoma{ },a b e quellodello stack { } A (non confondere A con lusuale simbolo dellalfabeto), insieme degli stati { }1 2,Q q q = ,

{ }2F q = , le transizioni sono le seguenti:1 1 1 2 2 20 : , : 0 , : 0q a Aq q bA q q bA q . 1 deterministico infatti non ci sono coppie di istruzioni incompatibili tra loro; fin quando1

legge il simboloa viene fatto il push nello stack del simbolo A, questo sistema permette allautoma ditene-re traccia del numero dia lette, invece quando vengono letteb viene effettuato il pop dallo stack del sim-bolo A e si transita nello stato2q .

Il linguaggio riconosciuto da questo automa ( ) [ ] [ ]{ }1 | 0n nL a b n= > e lo si pu verificare facen-do degli esempi(facendo leggere delle stringhe del linguaggio allautoma e verificando che lautoma, alla fine della lesi trova in uno degli stati, in questo caso2q , di accettazione).

Come si pu notare da questo primo esempio di automa a pila, il linguaggio riconosciuto proprio unodi quei linguaggi non riconoscibili da automi finiti tradizionali (visti nella prima parte del corso), questoper evincere subito la potenza di questo nuovo strumento, quale lautoma pushdown.

Proviamo a far leggere allautoma pushdown la stringau ab= da cui si ha lau-computazione:1 2 3, , con ( )1 11, ,0q = , ( )2 22, ,q A = e ( )3 23, ,0q = , possiamo anche scriverla in questo modo:

( ) ( ) ( )1 1 21 1| |: 1, ,0 2, , 3, ,0u q q A q .

Come possiamo notare, nella terzau-configurazione, lo stato di accettazione e lo stack vuoto, ci vuol dire che la stringaab stata accettata dallautoma pushdown.

Inizialmente lo stack vuoto, alla lettura del simboloa , lautoma pushdown resta nello stato iniziale1q ,mentre viene caricato il simbolo A nello stack. Alla lettura del simbolob, lautoma pushdown transita nel-lo stato 2q e viene fatto il pop del simbolo A dallo stack.

Adesso facciamo un esempio con la stringav aab= che porta allau-computazione:

( ) ( ) ( ) ( )1 1 2 1 3 1 4 21, ,0 , 2, , , 3, , , 4, ,q q A q AA q A = = = =

che non di accettazione in quanto in4 lautoma pushdown s pervenuto in uno stato di accettazione ma lo stack non vuoto.

Ultima stringa su cui testare1 w aabb= dalla quale otteniamo la sequenza:( ) ( ) ( ) ( ) ( )1 1 2 2 21 1 1 1| | | |: 1, ,0 2, , 3, , 4, , 5, ,0w q q A q AA q A q

Dunque la stringaaabb accettata da 1 .

7/21/2019 PDF Document (92329)

64/125

Decima Quinta Lezione prima parte 24/11/2006

esempi sugli Automi Pushdown e relativi teoremi

Esempio 2: sia 2 con { }, ,T A a b c = ( T A sta perTape alphabet ), { },P A A B = ( P A sta perPushdown al- phabet ), { }1 2,Q q q = , { }2F q = , le transizioni seguono il seguente schema:1 10 :q a Aq , 1 10 :q b Bq ,

1 20 : 0q c q , 2 2: 0q aA q , 2 2: 0q bB q .

Anche in questo caso 2 deterministico in quanto non ci sono coppie di istruzioni incompatibili traloro.

Il linguaggio riconosciuto da2 ( ) { }{ }2 | ,R L u c u u a b = (quindi stringhe del tipo, ad esempio,a c a , , ,ab c ba aab c baa ).

Proviamo a far leggere la stringaw abcba = , otteniamo la sequenza diu-configurazioni:( ) ( ) ( ) ( ) ( ) ( )1 1 1 2 2 22 2 2 2 2| | | | |: 1, ,0 2, , 3, , 4, , 5, , 6, ,0w q q A q BA q BA q A q .

Non complicato capire il meccanismo di questo automa pushdown, alla lettura di simbolia o b allostato 1q vengono caricati nello stack rispettivamente i simboli A o B , mentre allo stato2q vengono toltidallo stack rispettivamente i simboli A o B . Il cambio di stato avviene soltanto alla lettura del simboloc .Durante la prima parte nella lettura della stringa lo stack viene caricato, tenendo traccia della stringau,una volta lettoc viene scaricato lo stack fin quando la stringaR u non viene letta tutta.

Esempio 3: Sia 3 un automa pushdown con { },T A a b= , { },P A A B = , { }1 2,Q q q = , { }2F q = ,le transizioni sono le seguenti:1 10 :q a Aq ,. 1 10 :q b Bq , 1 2: 0q aA q , 1 2: 0q bB q , 2 2: 0q aA q , 2 2: 0q bB q .

Questo il caso di un automa pushdown non deterministico infatti le coppie di transizioni prima-terzae seconda-quarta non sono compatibili tra loro (stesso stato, stesso simbolo letto, ma uno dei pop per cia-scuna coppia 0 , cio viene fatto un pop e un push contemporaneamente). In tal caso3 ha la capaci-t di seguire pi strade contemporaneamente quando si trova nello stato1q nel leggerea o b .

3 riconosce il linguaggio( ) { }{ }3 | , 0R L u u u a b u= (quindi stringhe del tipo, ad esempio,a a , ab ba , b b , abb bba , ).

Nella lettura della parolaaa si ottiene:

( ) ( ) ( )1 1 13 3| |: 1, ,0 2, , 3, ,aa q q A q AA

( )23| 2, ,?q ( )23| 3, ,0q .

Come si pu notare 3 in pi punti segue contemporaneamente strade differenti, ma, come acca-deva per gli automi non deterministici tradizionali, non sempre certe strade vengono prese in consizione, ma scartate, in questo caso dueu-configurazioni vengono scartate,( )22, ,?q perch non ha sensoeffettuare il push da uno stack che vuoto,( )13, ,q AA s accettabile comeu-configurazione ma nonpermette allautoma pushdown di accettare la stringaaa , quindi viene anchessa scartata.

I linguaggi riconosciuti dagli automi pushdown1 2 3, sono tutti e treC.F.

7/21/2019 PDF Document (92329)

65/125

EDIT by Qd Grammatiche - XV Lez. - I parte

63

Come abbiamo visto gli automi a pila offrono grosse potenzialit, tuttavia esistono altri tipi diguaggi che neanche gli automi a pila sono in grado di riconoscere, per cui esistono entit matemaancora pi potenti.

TEOREMA8.3 (non dim. rif.D.S. W . pag. 316): Sia una grammatica in forma normale di Chomsky, al-lora vi un automa a pila che riconosce il linguaggio generato da , si ha quindi ( ) ( )L L= .

TEOREMA8.4 (non dim.): Per ogni linguaggioC.F. L, vi un automa a pila che riconosce talelinguaggio, si ha quindi ( )L L= .

TEOREMA8.6 (non dim.): Per ogni automa a pila ,( )L un linguaggioC.F.

7/21/2019 PDF Document (92329)

66/125

Calcolabilit

Decima Quinta Lezione Seconda parte 24/11/2006

Introduzione ai Linguaggi di ProgrammazioneS -programmi

Introduzione ai Linguaggi di Programmazione(rif.D.S. W . pag. 17)

Il linguaggio che andiamo a studiare ha istruzioni che operano su un alfabeto con apparenti limzioni { }0,1,2, ,9 A = , come vedremo linguaggi che agiscono su questo alfabeto hanno in realt gros

potenzialit per la soluzione dei problemi. Attualmente si pensa che se non possibile risolvere un problema con i mezzi che abbiamo oggi a dispo-

sizione (pratici e teorici), allora il problema in questione non potr mai essere risolto, il problema di fattoirrisolvibile. Ovviamente tale affermazione non dimostrata, ma fino ad ora risultata vera.

DEFF.: Il concetto teorico di computabilit si basa su uno specificolinguaggio di programmazione f (oS ). Lalfabeto di tale linguaggio stato poco fa definito, le variabili avranno valori interi nongativi, in particolare denotiamo con i simboli:

1 2 3 X X X variabili di input (ingresso);

Y la variabile (unica) di output(uscita );inoltre con i simboli:

1 2 3 Z Z Z denotiamo le variabililocali .

In qualche caso le variabili potranno essere denotate in minuscolo e il pedice 1 spesso omesso, quindiin luogo di 1 X ad esempio, scriveremo X .

A differenza dei linguaggi di programmazione effettivamente utilizzati, il linguaggioS non ha un limitesuperiore (riferito ai valori che possono assumere le variabili) per via della sua natura teorica, tuttavia lavo-rare con questi linguaggi piuttosto semplice, soprattutto per chi ha gi un minimo di esperienza con laprogrammazione.

Le istruzioni scritte e riconosciute dal linguaggiof sono sostanzialmente tre:

1V V + incremento della variabileV ;1V V decremento diV (se 0V = il valore diV resta invariato);

IF GOTO0V L condizionale (se 0V = si passa allistruzione successiva,altrimenti si passa allistruzione etichettata daL).

In aggiunta alle variabili viste fino ad ora utilizziamo i simboli:1 1 1 1 1 2 2 A B C D E A B (anche inquesto caso il pedice 1 pu essere omesso). Questi simboli servono ad etichettare le istruzioni, racchiudendo talisimboli tra parentesi quadre[ ], come mostrato nel seguente esempio:

7/21/2019 PDF Document (92329)

67/125

EDIT by Qd Calcolabilit XV Lez. - II parte

65

[ ] 1L V V + Il simboloV viene considerato come una meta variabile, cio un simbolo cheRappresenta un dato, nel nostro caso un numero intero non negativo.

Luso delle etichette indispensabile, soprattutto per le istruzioni condizionali.

Sulla base e sulla composizione delle istruzioni appena viste possiamo definire gliS-programmi , suc-cessioni finite e ordinate di istruzioni(ovviamente a differenza degli insiemi, qui lordine con cui vengono scritte leistruzioni e essenziale).

Per convenzione la variabile duscitaY e le variabili localii Z con 1i inizialmente hanno valorenullo 0.

Vediamo un primo esempio diS -programma (a ):

in questo caso X lunica variabile dingresso,Y quella di uscita, e come

definito, inizialmente 0Y = .

TaleS -programmacopia il valore di X inY , formalmente scriveremo:

X viene decrementato eY incrementato fintantoch 0 X ad ogni passodel ciclo; se per inizialmente 0 X = , dopo la prima istruzione, X varrsempre 0, dopodichY verr incrementato diventando 1, poich 0 X = durante listruzione condizionale IF il programma terminer.

Vediamo un altro esempio diS -programma (b):

Se inizialmente 0 X = , Y rimane a 0 e si esce dal programma.

La variabile Z viene utilizzata come flag per uscire dal programma almomento opportuno.

Le istruzioni denotate con* rappresentano quello che viene chiamatosalto incondizionato.

Il programma suddiviso in due partic e t . Il primo gruppo diistruzioni di controllo, mentre il secondo gruppo quello che sioccupa del trasferimento vero e proprio dei valori numerici dalla variabile X alla variabileY .

In questo caso risulta:LetichettaE , non facendo riferimento a nessuna istruzione esistente,fa terminare il programma(E sta perExit ).

Lesempio appena visto rappresenta un perfezionamento dellS -programma precedente, il quale pre-sentava un grave difetto e cio di non restituire il risultato corretto nelleventualit che X fosse nulla, in-

[ ]

IF GOTO

11

0

A X X Y Y

X A

+

( )1 se 0

altrimentia x

f x x

==

[ ]

[ ]

IF 0 GOTO

IF GOTO

IF GOTO

10

111

0

X A B c Z Z

Z E

B X X Y Y

t Z Z

Z A

+

+ +

( ) 0,b x f x x =

7/21/2019 PDF Document (92329)

68/125

EDIT by Qd Calcolabilit XV Lez. - II parte

66

fatti con 0 X = in uscita avremmo avuto 1Y = e non 0Y = . Nellesempio corrente invece, per qualsia-si valore non negativo di X avviene la copia di X in Y (in verit non si tratta di una vera e propria copia, ma di untrasferimento in quanto al termine del programma il valore iniziale di X va perduto diventando 0 una sorta ditaglia e incol-la quindi).

Analizziamo ora le due istruzioni contrassegnate con*: 1 Z Z + e IF GOTO0 Z E . Esse rap-presentano ilsalto incondizionatoperch indipendentemente dai valori che pu assumere Z , lesecuzionedi queste due istruzione porta alla terminazione del programma. Difatti Z non sar mai non nulla equindi si salter allistruzione etichettata conE che, non esistendo, fa terminare il programma. La primaistruzione ci assicura che, anche se Z fosse nulla, comunque porterebbe alla terminazione del program-ma, essendo incrementata a 1. Il salto incondizionato stato realizzato a posta nel caso in cui si vfar terminare prematuramente il programma.

DEFF: Le due istruzioni viste pocanzi, assieme a tante altre, sono molto utilizzate, utile quraggruppare queste istruzioni in ununica entit che chiameremomacro (il cui significato concettualmentesimile a quello adoperato per i linguaggi di programmazione effettivamente utilizzati sui calcolatori). cio una sequen-za di istruzioni che pu essere richiamata pi volte allinterno di unS -programma indicando semplice-mente il nome dato alla macro, senza dover, ogni volta riscrivere tutte le istruzioni di cui compomacro.

La sequenza di istruzioni costituenti la macro viene chiamataespansione della macro.

Nel caso del salto incondizionato utilizzato nel precedenteS -programma denotiamo la macro sem-plicemente cos:GOTO L e la sua espansione :

I nomi delle variabili e delle etichette non sono importanti, necessario per farcorrispondere le variabili del programma chiamante con le istruzionidellespansione della macro.

Come avevamo gi fatto notare i programmi (a ) e (b) trasferisconoil contenuto di X inY , madistruggendo (azzerando) il valore iniziale di X . Usualmente si vuole che (durante una copia o assegnazione) il valoredi X resti intatto, come accade normalmente nelle istruzioni di assegna-zione della maggior parte dei linguaggi di programmazione, quindi an-diamo ad illustrare, facendo uso delle macro, il seguenteS -programma

(c ): Analizzando le varie istruzioni ci si accorge che se inizialmente X nullo allora il pro-gramma (dopo alcuni controlli eGOTO) restituir il corretto valore (nullo) diY (se

0 X = GOTO C , se 0 Z = GOTO E , 0 X Y = = );

mentre se 0 X , prima si trasferisce il suo contenuto inY e poi si ripristina il valoreiniziale di X in modo da ottenere dal programma i risultati desiderati (se

0 X GOTO B , avviene il trasferimento da X a Y e anche a Z, mediante la rei-terazione di alcune istruzioni);si perde per il contenuto di X , il quale viene ripristinato -GOTO D - trasferendo ilcontenuto della variabile dappoggio Z nuovamente in X .

Chiaramente la funzione computata la stessa del programma precedente:( ) , 0c f x x x = .

IF GOTO1

0 Z Z

Z L

+

[ ]

[ ]

[ ]

[ ]

IF 0 GOTO

GOTO

GOTO

IF 0 GOTO

GOTO

GOTO

11

1

11

A X B

C B X X

Y Y

Z Z A

C Z D

E D Z Z

X X

C

+ +

+

7/21/2019 PDF Document (92329)

69/125

EDIT by Qd Calcolabilit XV Lez. - II parte

67

Si fatto uso di macro che snelliscono il codice, importante far corrispondere i nomi delle vare le etichette delle istruzioni, ad esempio,GOTO C ha come espansione le due istruzioni: 1K K + e IF GOTO0K C (luso della variabileK ci assicura, non essendo mai stata utilizzata, che altre variabili del pro-gramma chiamante non vengano compromesse, ovviamente la variabileC allinterno dellespansione della macro corrispondealla variabileC usata per richiamare la macro, se ci fosse stata unaltra variabile nella chiamata, allora nellespansione av

mo trovato lo stesso nome della variabile menzionata nella chiamata). Anche se nellespansione della macro si usassero nomi di variabili uguali a quelli utilizzati esternamente,

bisognerebbe distinguere le variabili locali dalle altre variabili e non fare confusione con ambiguit chesporcherebbero il risultato.

Abbiamo visto nel terzo esempio diS -programma come una semplice operazione di assegnazionenon sia cos immediata da realizzare con le operazioni atomiche che abbiamo a disposizione, oltresappiamo che lassegnazione unoperazione largamente usata nei linguaggi di programmazione, to utile quindi trasformare in macro il programma (c ), tuttavia questultima, se utilizzata in un altroprogramma potrebbe non funzionare correttamente in quanto, per essere sempre corretta, le variabY e Z inizialmente devono essere nulle, e non detto che sia sempre cos, in quanto la variabileY in par-ticolare potrebbe essere stata utilizzata dal programma chiamante e contenere dei valori non numomento della chiamata della macro di assegnazione. Bisogna quindi, prima di richiamare tale mazzerare il valore della variabile a cui verr assegnato il dato. Risolviamo il problema con la segumarco diinizializzazione 0V la cui espansione :

[ ]IF GOTO

10

L V V V L

Con lausilio dellultima macro vista possiamo riscrivere, in termini di macro, il programma (c ) chedenoteremo con la scritturaV V la cui espansione la seguente:

(rif.D.S. W . pag. 21) Da notare che Z non stata inizializzata a 0 in quanto considerata variabile locale (se nel programma chiamante viene utilizzata una variabile con lo stesso nome Z allora questo nome deve essere cambiato), ilcui valore iniziale non vieneereditatodal programma chiamante n il suo valore finale verr restituito al programma chiamante, pi precisamente la variabile Z utilizzata nella marco non deve essere la stessa che,eventualmente, verr utilizzata nel programma chiamante, il discorso diverso invece perV (il cui nome e valore devono essere ereditati dal

programma chiamante, come visto prima nella macroGOTO L ). dunque buona norma, per evitare confusione, utilizzare per le variabililocali nomi differenti da quelli utilizzati nel programma chiamante, analogodiscorso vale per le etichette delle istruzioni.

[ ]

[ ]

[ ]

[ ]

IF 0 GOTOGOTO

GOTO

IF 0 GOTO

GOTO

GOTO

0

111

11

V A V B

C B V V

V V Z Z

AC Z D

E D Z Z

V V C

+ +

+

7/21/2019 PDF Document (92329)

70/125

EDIT by Qd Calcolabilit XV Lez. - II parte

68

Vediamo ora un altro importanteS -programma (d ) che, ricevendo in input due valori, computa lafunzione ( )1 2 1 2,d f x x x x = + .

Viene fatto uso della macro del salto incondizionato e dellassegnazione.

Il programma effettua la somma di1 X e 2 X ponendo il risultato inY , ecco le istruzioni:

Inizialmente viene posto il valore1 X inY ;dopodich, mediante una variabile temporanea Z , Y viene incrementato diuna unit 2 X volte.

Luso della variabile Z ha lo scopo di preservare il valore di2 X , il pro-gramma infatti funzionerebbe anche senza lutilizzo della variabiletemporanea Z , ma alla fine il valore di2 X andrebbe perso e, per lo stessoprincipio per cui stata progettata la precedente macro di assegnazione,

anche in questo caso si vuole che le variabili di entrata restinointatte .

Proseguiamo col mostrare un altroS -programma (e ) (rif.D.S. W . pag. 22)che esegue il prodotto di dueinteri e che computa la funzione( )1 2 1 2,e f x x x x = :

La moltiplicazione viene interpretata come una sequenza di somme, vengo-no infatti eseguite2 X somme di 1 X :

volte2

1 1 1 X

X X X + + +

Luso delletichetta2E , apparentemente non necessario, verr spiegato abreve. Come si pu notare viene fatto uso della macro1 1 Z X Y + la cuiespansione , in sostanza, il programma precedente. Ci sono per da farealcune riflessioni, il programma precedente sommava1 X e 2 X e poneva ilrisultato inY , se volessimo utilizzarlo come macro, cos com, nel contestodi questo programma avremmo il seguente codice:

Se osserviamo con attenzione i nomi delle variabili possiamo accorgerci cheutilizzando questo codice non otterremo il risultato sperato nel programmachiamante, per via di ambiguit nelluso delle etichette e delle variabili. Luso del

GOTO E ad esempio porterebbe alla terminazione prematura del programma (enon solo della macro come si potrebbe pensare), invece si vuole che, una voltaterminata la macro si ritorni al programma chiamante. Quindi necessario fareuso di unaltra etichetta (2E ) sia nellespansione della macro che nel programmachiamante. Altro problema rappresentato dalla variabileY che, nel contestodel programma chiamante, confusa con la variabile1 Z (abbiamo

1 1 Z X Y + e non 1 2Y X X + ). Quando nel programma chiamante scri- viamo listruzione1 1 Z X Y + ci aspettiamo che i valori di1 X e diY , dopolesecuzione della macro restino immutati e la loro somma venga memorizzata in

1 Z , ma ci non avviene nellespansione qui mostrata, oltre al problemadelletichettaE . Quindi vanno cambiati i nomi di alcune variabili ed etichette.

[ ]

[ ]

1

2

IF GOTO

GOTO

GOTO

0

11

Y X Z X

B Z AE

A Z Z Y Y

B

+

[ ]

[ ]

[ ]

2 2

2

2 2

1 1

2 1

IF GOTOGOTO

GOTO

0

1

E

Z X B Z A

E

A Z Z Z X Y Y Z

B

+

[ ]

[ ]

1

IF GOTO

GOTO

GOTO

0

11

Y X

Z Y

B Z A

E

A Z Z

Y Y

B

+

7/21/2019 PDF Document (92329)

71/125

EDIT by Qd Calcolabilit XV Lez. - II parte

69

Vediamo ora la corretta espansione da utilizzare per il programma chiamante con gli accorgimappena suggeriti:

[ ]

[ ]

1 1

3

2 3 2

2

2 3 3

1 1

2

IF GOTO

GOTO

GOTO

0

11

Z X Z Y

B Z AE

A Z Z Z Z

B

+

Vediamo lultimoS -programma ( f ) che, seppur con qualche limitazione, effettua la sottrazione di

due interi, ponendo il risultato nella variabile di uscita: Analizzando il programma si scopre che esso computa la se-guente funzione: ( )1 2 1 2, f f x x x x = se 1 2 x x mentre d unrisultatoindeterminato se 1 2 x x < , infatti il programma entra inun ciclo infinito (loop), tale condizione viene indicata medianteil simbolo Il loop avviene quando in A la variabileY nulla, in tal caso si ritorna(GOTO A) nuovamente allistruzione A e questo processo si ripeteallinfinito.

Formalmente possiamo scrivere la seguente funzione computatadal programma : ( )

1 2 1 21 2

se,

altrimenti f x x x x

f x x

= .

La funzione appena descritta prende il nome di funzione parziale il cui concetto importante perapprendere che non tutte le funzioni possono essere computate dagliS -programmi. Formalmente ab-biamo:

DEFF. (rif.D.S. W . pag. 3): Se una funzione f ha come dominio di definizione un sottoinsieme di (sottoinsieme improprio A ) diremo che f una funzione parziale sullinsieme dei naturali.

Nel caso in cui la funzione parziale abbia come dominio stesso( ), allora tale funzione dettatotale (cio sempre definita per tutti i valori di).

(rif.D.S. W . pag. 25) Con il termineasserzione(statement ) indichiamo unistruzione che pu avere unadelle seguenti forme:

4. IF GOTO

1. 12. 13.

0

V V V V V V

V L

+

[ ]

[ ]

[ ]

1

2

IF GOTO

GOTO

IF GOTO

GOTO

GOTO

0

0

11

Y X Z X

C Z AE

A Y B A

B Y Y Z Z

C

7/21/2019 PDF Document (92329)

72/125

EDIT by Qd Calcolabilit XV Lez. - II parte

70

La terza istruzione detta istruzione pigra (dummy ) in quanto la sua esecuzione allinterno di unprogramma non porta ad alcun effetto.

Formalmente unistruzione una delle quattro asserzioni viste, precedute o meno da[ ]L che unetichetta generica data allistruzione.

Un S-programma una successione finita di istruzioni.

Lalunghezza di unS -programma il numero delle sue istruzioni.

Un S -programma di lunghezza 0 detto programma vuoto ( privo di istruzioni da cui( ) 0 f x = x ).

Come abbiamo visto, le variabili di un programma, durante lesecuzione dello stesso, possono mere valori differenti, ci suggerisce la seguente definizione:

Lostato di un problema una lista di equazioni nella formaV m= , conV nome della variabileedm il suo valore, tale che:

1. vi unequazione per ogni variabile di ;2. non vi sono due equazioni con la stessa variabile.

Quindi uno stato indica i valori che possono assumere in certi istanti, non necessariamente inizle variabili del programma.

Se uno stato del programma , il valore diV allo stato il numeroq tale cheV q = una delle equazioni di .

Unistantanea (snapshot ) di un programma una coppia ordinata( ),i con 1 1i n + , il sim-bolon corrisponde alla lunghezza (numero di istruzioni) del programma, mentre e uno stato ad uncerto istante dellesecuzione del programma, in altre parole( ),i rappresenta il valore delle variabilinellistante precedente lesecuzione dellai -ma istruzione di .

7/21/2019 PDF Document (92329)

73/125

Decima Sesta Lezione01/12/2006

Ricapitolazione e seguito concetti sugliS -programmifunzioni parzialmente calcolabili - estensione delle macro

predicati - composizione di funzioni - ricorsione

Ricapitolazione concetti preliminari sugliS -programmi.

Data listantanea( ),i di ,i il numero di istruzione corrente, mentre lassegnazione cor-rente di valori delle variabili.

DEFF.: Unistantanea( ),i di dettaterminale se 1i = + .

( ),i dettanon terminale se vi unistantanea( ), j che successore di ( ),i .

Diamo una definizione per casi(in base alle asserzioni) di istantanea successore ( ), j di ( ),i :

1. la i -ma istruzione di 1V V + e contiene tra le equazioniV m= , allora 1 j i = + e siottiene da rimpiazzandoV m= con 1V m= + ;

2. la i -ma istruzione di 1V V e contiene tra le equazioniV m= , allora 1 j i = + e , se0m , allora si otterr da rimpiazzandoV m= con 1V m= , altrimenti (se 0m = ) = ;

3. lai -ma istruzione di V V , allora 1 j i = + e = ;

4. la i -ma istruzione di IF GOTO0V L allora = (essendo unasserzione di controllo e non dimodifica delle variabili, lo stato non cambia, ma il numero di istruzione potrebbe cambiare, se si effettua il salto), di-stinguiamo due sottocasi:

4.1. se 0V = , contiene lequazione 0V = , allora 1 j i = + (il salto non avviene e si prosegue con la suc-cessiva istruzione);

4.2. se 0V , contiene lequazioneV m= e, se letichettaL non fa riferimento a nessuna istru-zione allora 1 j n= + (il programma termina, in questo caso listantanea successore di( ),i unistantanea

terminale( )1,n + ). Mentre se fa riferimento a una o pi istruzioni, j sar il pi piccolo numerotale che la j -ma istruzione etichettata conL (ovvero la prima che si incontra dallalto verso ilbasso-per evitare diramazioni non deterministiche non facenti parte della natura degliS -programmi).

Lultimo caso visto spiega anche il comportamento del programma in situazioni nelle quali ci pi istruzioni contrassegnate con la stessa etichetta, in tal caso si fa riferimento sempre alla primsi incontra(le altre verranno ignorate come se non esistessero).

(rif.D.S. W . pag. 29): Un calcolo (computation) di unS -programma una successione finita di istan-

tanee 1 2, , , k s s s (lordine dei pedici non deve essere casuale)tale che 1i s + con 1,2, , 1i k = successore dii s ed k s unistantanea terminale.

7/21/2019 PDF Document (92329)

74/125

EDIT by Qd Calcolabilit XVI Lez.

72

Un processo di calcolonon terminale (da non confondere con lomonimo stato) di una successioneinfinita di istantanee1 2, ,s s , tale che 1i s + con 1,2,i = successore dii s .

(rif.D.S. W . pag. 28) Sia unS -programma e siano1 2, , mr r r con 1m (m indica il numero di varia-bili della funzione computata da ),con lo stato di dato dalle equazioni

1 1,

r =

2 2, X r = , , 0m m X r Y = = e dalle equazioni 0V = per ogni altra variabile di(variabili locali, in ognicaso che non siano variabili di ingresso,1i X i m o di uscitaY) denotiamo lostato iniziale di e con( )1, istantanea iniziale , con tali condizioni possono verificarsi due casi:

1. vi un calcolo di :1 2, , , k s s s (non si confondas con r ), allora con la scrittura( )( ) 1 2, , ,m mr r r indichiamo il valore diY allistantanea terminalek s con ( )1 1,s = ;

0 = se il programma terminante .

2. non vi un calcolo di (se listantanea iniziale ( )1, ) (ci non vuol dire che ilprogramma non sta girando, ma che entra in un loop infinito).In tal caso ( )( ) 1 2, , ,m mr r r assume un valore indefinito .

In effetti con la definizione appena data si formalizzato il comportamento di al termine dellacomputazione e a partire dallistantanea iniziale di.

Esempio 1: prendiamo in analisi il programma (b) che copiava il contenuto della variabile X in Y :( )(1 )

b x x = chiaramente( 1m = in quanto la variabile dingresso soltanto X ; X x = ; non dimentichiamo che im-

plicito considerare il valore di(1 )

b presupponendo listantanea iniziale( )1, ).

Esempio 2: consideriamo il programma:11

X X X X

+ + , la cui istantanea iniziale, con stato iniziale,

: ( ) (1, 1, = { })1, 0 X r Y = = . Dopo lesecuzione della prima istruzione abbiamo{ }( )12, 1, 0 X r Y = + = e, dopo la seconda istruzione abbiamo{ }( )13, 2, 0 X r Y = + = che listantanea terminale. La variabileY non viene menzionata nelle istruzioni del programma, quindi il suo valore resta immutato e cio nabbiamo dunque: ( )(1 ) 1 0r = .

Esempio 3(rif.D.S. W . pag. 31): consideriamo il programma con le seguenti istruzioni:

[ ]IF GOTO

10

A X X X A

+ (loop infinito)

Abbiamo la seguente istantanea iniziale{ }( )11, , 0 X r Y = = e poi { }( )12, 1, 0 X r Y = + = ,{ }( )11, 1, 0 X r Y = + = , { }( )12, 2, 0 X r Y = + = , da cui chiaramente ( )(1 ) 1r = , 1 0r .

DEFF. (rif.D.S. W . pag. 30): Per ogni e per ogni intero positivom, la funzione ( )( ) 1 2, , ,m m x x x la funzione dim argomenticalcolata dal programma .

7/21/2019 PDF Document (92329)

75/125

EDIT by Qd Calcolabilit XVI Lez.

73

Da notare chem un numero che si riferisce al numero di argomenti della funzione calcolata dprogramma e non dipende (o non si riferisce) al numero di variabili di input del programma, ovvenumero di argomenti della funzione calcolata dal programma non legato al numero di variabili dput del programma. Ci si evince da due casi particolari: abbiamo conn variabili di input conm n< (cio nella funzione( )m

compaiono meno argomenti del numero di variabili di input dellS -programma ), nel

calcolo della funzione risulter:1 1 2 2 1, , , , 0, , 0n n n mr X r X r X r r += = = = = , cio le variabili che nonfanno riferimento ad argomenti della funzione calcolata verranno considerati nulli anche se magar effettivamente cos; viceversa, sem n> (quindi abbiamo pi argomenti della funzione che variabili di input del programma) i valori degliargomenti non facenti riferimento a variabili del programma verranno semplicemente ignorati.

Per comprendere meglio i concetti appena descritti facciamo degli esempi di funzioni il cui numdi argomenti non corrisponde al numero di variabili di input del relativo programma. Facciamo rimento ai programmi (c ) e (d ).Come ricordiamo il programma (c ) effettuava unassegnazione, ha una sola variabile di input e abbiamo

( )(1 ) 1 1c r r = , qui abbiamo fatto combaciare il numero di argomenti della funzione con il numero di vriabili di input che pari a 1. Mentre se volessimo conoscere il valore della funzione calcolata da c ) cheha per due argomenti avremmo( )(2 ) 1 2 1,c r r r = , chiaramente il valore2r viene ignorato non essendocorrispondente di alcun valore di variabile di input.Ora riferiamoci al programma (d ) che effettuava la somma di due interi contenuti nelle due variabili diinput e la trasferiva nella variabile di uscitaY , abbiamo ( )(2 ) 1 2 1 2,c r r r r = + , mentre ( )(3 ) 1 2 3 1 2, ,r r r r r = + ,largomento3r viene ignorato. Vediamo ora il caso opposto ( )(1) 1 1 10c r r r = + = , in questo caso lo 0rimpiazza in qualche modo la va-riabile del programma che non ha corrispondenza con alcuna variabile( 2r non esiste, mentre2 X si).

DEFF.: Sia g una funzione parziale (con una o pi variabili) su, allora g si dice parzialmente calco-labile se esiste unS -programma che la calcola e cio se per ognim-pla( )1 2, , , m mmr r r S risul-ta ( ) ( )( )1 2 1 2, , , , , ,mm m g r r r r r r = .

Da sottolineare che nel caso in cui( )1 2, , , m g r r r = e ( )( ) 1 2, , ,m mr r r = non si pu concludereassolutamente che ( )m g = in quanto il simbolo non numericamente esprimibile.

Una funzione dettacalcolabile se totale ed parzialmente calcolabile(una funzione totale definita intutto il suo dominio, cio per ognim-pla di argomenti1 2, , , mr r r ).

Le funzioni parzialmente calcolabili vengono chiamate anchericorsive parziali , analogamente le fun-zioni calcolabili, cio sia totali che ricorsive parziali, vengono anche dettericorsive .

Ad esempio, dal programma visto prima:

[ ]

IF GOTO

1

0

A X X

X A

+

si ha ( )(1 ) x = che una funzione indefinita per ogni

7/21/2019 PDF Document (92329)

76/125

EDIT by Qd Calcolabilit XVI Lez.

74

valore di x , possiamo dunque affermare che il dominio della funzione linsieme vuoto che pursempre un sottoinsieme di(rif.D.S. W . pag. 3), quindi possiamo affermare che la funzione del program-ma suindicato appartiene allaClasse delle funzioni ricorsive parziali quindi una funzione ricorsiva parziale (o anche parzialmente calcolabile) pur non essendo definita per alcun naturale( quindi scorretto af-fermare che la funzione vista nellesempio non calcolabile).

Estensione delle macro(rif.D.S. W . pag. 32)

Facendo riferimento alluso delle macro, la seguente scrittura

( )1 2, , , nW f V V V

Rappresenta il trasferimento del valore di( )1 2, , , n f V V V , calcolato da qualcheS -programma, nella variabileW . In effetti lespansione della macro una sequenza di istruzioni che calco

( ) ( )( ) 1 2 1 2, , , , , ,n n nV V V f V V V = , quindi f una funzione calcolabile o parzialmente calcolabile eW rappresenta una variabile generica(che potrebbe anche essere uno degli argomentii V di f ) .

Ricorrendo a regole generali per quanto riguarda luso appropriato dei nomi delle variabili e detichette delle istruzioni, si pu ottenere uno schema generale per costruire espansioni di macro inin programmi chiamanti(per il dettaglio vedereD.S. W . pagg. 32-33).

Un caso particolare si presenta quando risulta ( )1 2, , , nW f V V V e ( )1 2, , , n f V V V = , alloraanche la funzione calcolata dal programma chiamante la macro dar luogo ad un valore indetermin

Ad esempio, il seguente programma fa uso di macro le cui estensioni calcolano funzioni che mono valori indeterminati per certi elementi del dominio:

1 2

3

Z X X Y Z X

+ Poich la macro 1 2 Z X X che fa riferimento al programma ( f )

computa la funzione ( ) 1 2 1 21 2 se

, altrimenti f

x x x x f x x

=

che per certi valori indeterminata, questainde-

terminazione verr in qualche modotramandata alla funzione chiamante che infatti computa la funzio-

ne ( ) ( )1 2 3 1 2(3 )

1 2 3

se, ,

altrimenti x x x x x

x x x +

=

.

Per ovviare a questi inconvenienti possiamo arricchire il nostro linguaggio di programmazione,che con luso (opportuno) delle macro, anche con luso dei predicati (pi articolati del tradizionale

0V ) allinterno dei costrutti selettiviIF.

DEF.: Un predicato P su un insiemeS una funzione totale tale chea S risulta:

7/21/2019 PDF Document (92329)

77/125

EDIT by Qd Calcolabilit XVI Lez.

75

( ) ( )

( ) ( )oppure

1

0

vero

falso

P a

P a

=

= (in realtP pu avere anche pi di un argomento).

Unosservazione interessante che luso dei predicati non pu essere adoperato per realizzare metgoritmici capaci di prevedere se un algoritmo andr in loop oppure no(si pu apprendere che un algoritmo entrato in loop esclusivamente quando entra in loop e non prima, vale ovviamente il contrario e cio che non si pu sapriori se un algoritmo non andr mai in loop o meno, ma ci non basta per affermare, in generale, che un programma narrester mai, in quanto un programma entrato in un ipotetico loop potrebbe anche fermarsi da un momento allaltro, menoch noi non conosciamo le istruzioni del programma. Un ipotetica macchina che esegue un programma non pu vedere se questo avr un calcolo (finito) o meno, tale certezza si ha solo se il programma termina). Conseguenza di que-sto concetto si vedr pi avanti quando si esibir un predicato che non calcolabile mediante uS -programma. Altro concetto da sottolineare che facilmente si fa confusione tra predicato e funzione parzialmcalcolabile. Un predicato una particolare funzione cheha vita propria indipendentemente dagliS -programmi, un predicato una funzione che, per come stata definita, sempre totale (e pu assusolo e soltanto i vaori 1 e 0) al di l del fatto che possa o non possa essere calcolata da unS -programma(potr capitare di incontrare funzioni che a prima vista sembrano predicati per come sono strutturati, ma nel momencui ci si accorge che tali presunti predicati assumono valori indeterminati o differenti da 0 o da 1, possiamo subito affche non sono predicati, ma funzioni, poi se tali funzioni sono calcolabili o parzialmente calcolabili questo un altro dso).

Con luso delle macro la forma generale che assume il costrutto di selezione :

( )1 2IF GOTO, , , nP V V V L

la cui espansione la seguente:

Viene calcolatoP memorizzato il risultato in Z ;seP vero alloro 0 Z quindi si va allistruzioneL;altrimenti 0 Z = e la macro termina.

Vediamo ora lesempio con un predicato largamente utilizzato:

IF 0V = GOTO L

ecco la sua espansione(non si badato alluso corretto dei nomi delle variabilie delle etichette delle istruzioni):

in questo caso il valore del predicato memorizzato inY e X corrisponde aV ;si ricordi cheY inizialmente nullo;se 0 X la macro termina (GOTOE ) e il valore diY resta nullo, il programma chiamante passa allistruzione successiva;se invece 0 X = allora 1Y = e il programma chiamante passa allistruzioneL;Nellesempio quindi, se il predicato" 0"V = vero assumer un valorenon nullo, quindi si passer allistruzioneL.

( )1 2IF GOTO

, , ,0

n Z P V V V Z L

IF GOTO01

X E Y Y

+

7/21/2019 PDF Document (92329)

78/125

EDIT by Qd Calcolabilit XVI Lez.

76

DEF. (rif.D.S. W . pag.34-35): EssendoP una particolare funzione, ha senso dire cheP o non calcola-bile, quindi si parla di predicato calcolabile o non calcolabile in base alle definizioni date prima di funzio-ni calcolabili(essendo i predicati funzioni totali, non ha senso parlare di parziale calcolabilit, abbiamo dunque che se ste unS -programma che calcola il predicatoP , alloraP calcolabile).

Mediante una generalizzazione possiamo fornire un esempio di predicato calcolabile che il seguente:

IF 0V > GOTO L

Il quale chiaramente una generalizzazione dellistruzioneIF GOTO0V L .

Composizione di funzioni(rif.D.S. W . pag. 39)

Mostriamo un metodo per combinare loutput di una o pi funzioni allinput di unaltra funzione(ad una o pi variabili) sulla base delle funzioni composte del tipo:( ) ( )( )h x f g x = . Diamo pertantola seguente definizione per formalizzare e generalizzare il concetto:

DEF.: Sia f una funzione dik variabili e siano1 2, , , k g g g funzioni din variabili. Se scriviamo( ) ( ) ( ) ( )( )1 2 1 1 2 2 1 2 1 2, , , , , , , , , , , , , , ,n n n k nh x x x f g x x x g x x x g x x x = allora si dice cheh ot-

tenuta percomposizione da f e 1 2, , , k g g g .

Attenzione a non confondere il numeron di variabili dih con il numero di variabilik di f , si sarebbeportati a pensare che essendoci unuguaglianza trah ed f il numero di argomenti dih debba coinciderecon quello di f , mah una funzione composta i cui argomenti sono1 2, , , n x x x e non 1 2, , , k g g g ,quindi luguaglianza definita pocanzi ben posta.Del resto ha senso scrivere ad esempio che( ) ( )1 1 2, j k f x f x x = se si applica la diagonalizzazionedellargomento, cio si impone ( )1 1 2, x x x con 1 2 x x = , le funzioni sono uguali sebbene j f ha un ar-gomento mentrek f ne ha due.

Ovviamente le funzioni 1 2, , , , k f g g g non sono necessariamente totali eh sar calco-lata quando tutte le funzioni ( )1 1 2 1, , , n g x x x z = , ( )2 1 2 2, , , n g x x x z = , ,

( )1 2, , ,k n k g x x x z = ed ( )1 2, , , n f z z z saranno calcolate. Tale imposizione pu esseregiustificata facendo uso delle macro e verificando la correttezza delluguaglianza inquesto modo:

durante la computazione vengono calcolateprima tutte le funzioni1 2, , , k g g g e memorizzati i valori rispettivamentein 1 2, , , k Z Z Z ;dopodich le variabili Z vengono adoperateper il calcolo di f il cui valore vienememorizzato inY

( )( )

( )

( )

1 1 1 2

2 2 1 2

1 2

1 2

, , ,, , ,

, , ,

, , ,

n

n

nk k

k f

Z g X X X

Z g X X X

Z g X X X

Y Z Z Z

7/21/2019 PDF Document (92329)

79/125

EDIT by Qd Calcolabilit XVI Lez.

77

La marco vista utile per dimostrare il teorema seguente:

TEOREMA 1.1(banale rif.D.S. W . pag 39): Seh ottenuta percomposizione delle funzioni (parzialmen-te) calcolabili 1 2, , , , k f g g g allorah (parzialmente) calcolabile.

DEF.: dobbiamo dimostrare che se1 2, , , , k f g g g sono (parzialmente) calcolabili allora ancheh (par-zialmente) calcolabile, ci immediato osservando la macro, infatti per dimostrare cheh (parzial-mente) calcolabile dobbiamo fornire unS -programma che la calcola utilizzando le funzioni (parzialmen-te) calcolabili (per ipotesi) 1 2, , , , k f g g g . ovvio che se ( )1 2, , , ni i Z g X X X , con 1 i k , e

( )1 2, , , k Y f Z Z Z sono (parzialmente) calcolabili, ne deriva cheh (parzialmente) calcolabile.

Ricorsione

(rif.D.S. W . pag. 40)

DEF.: Supponiamo chek sia una costante eh una funzione definitain questo modo: g una funzione totale di due variabili, allora diremo cheh ottenuta da g per ricorsione primitiva o semplicemente per ricorsione.

TEOREMA 2.1: Se h ottenuto da g per ricorsione primitiva e posto g calcolabile( g per definizione to-tale), allorah anchessa calcolabile (quindi totale anchessa).

DIM.: facile provare che una funzione costante del tipo( ) f x k = calcolabile, infatti essa calcolataad esempio dallS -programma:

11

volte

1

Y Y Y Y

k

Y Y

+ +

+

queste istruzioni rappresentano lespansione della macroY k .

La macro appena vista la utilizziamo per calcolare la funzioneh ottenuta da g per ricorsione primitiva:

si calcola primak e si memorizza il risultato inY ;

se largomento dih 0 allora si esce dal programma e( )0h k Y = = ;altrimenti (per hp. g calcolabile quindi il suo valore vienecalcolato e memorizzato inY) viene effettuato il calcolo di( ) ( )( )1 ,h t g t h t + = un passo alla volta incrementando il parametrot partendo da 0, cio seguendo lasequenza:

( )( ) ( )( )0

1 ,h k

h t g t h t

=+ =

[ ]( )

IF GOTO

GOTO

0,11

Y k A X E

Y g Z Y Z Z X X

A

=

+

7/21/2019 PDF Document (92329)

80/125

EDIT by Qd Calcolabilit XVI Lez.

78

( )( ) ( )( ) ( )( ) ( )( )

( ) ( )( )( ) ( )( )

01 0, 0 0,2 1, 1

1 2, 21, 1

h k Y

h g h g k

h g h

h x g x h x

h x g x h x

= =

= =

=

= =

Avendo fornito unS -programma che calcolah abbiamo dimostrato il teorema.

Complichiamo un po il concetto appena visto in modo da dare una definizione pi generale di risione.

DEF.: Sia:( ) ( )( ) ( )( )

1 2 1 2

1 2 1 2 1 2

, , , ,0 , , ,, , , , 1 , , , , , , , , ,

n n

n n n

h x x x f x x x

h x x x t g t h x x x t x x x

=

+ =

allora la funzioneh a 1n + variabili si diceottenuta per ricorsione primitiva o semplicemente perricor-sione dalle funzioni totali f (din variabili) e g (di 2n + variabili).

TEOREMA 2.2: Siah ottenuta dalle funzioni a pi variabili f e g per ricorsione primitiva (secondo

la definizione appena vista), se f e g sono calcolabili allorah anchessa calcolabile.DIM.: Come per il teorema precedente, basta trovare unS -programma che calcolah (questa strategia ricordaquella adoperata per dimostrare teorema sui linguaggi regolare eC.F. per i quali si esibivano rispettivamente automi ricono-scitori e grammatiche generatrici). Ricordiamo che per ipotesi g ed f sono calcolabili, il seguenteS -programma calcolah, il cui schema del tutto simile a quello dellS -programma utilizzato per la dimo-strazione del teorema precedente :

viene memorizzato il valore di f inY il parametrot della funzioneh rappresentato dalla variabile1n X +

se risulta ( )1 2, , , ,0nh x x x il programma termina e il suo valore diuscita sar ( )1 2, , , ,0nY h x x x altrimenti parte il ciclo che calcola la funzione ricorsiva partendoda 11, , nt t X += =

( )[ ]

( )

1 2

1

1 2

1 1

IF GOTO

GOTO

, , ,0, , , , ,1

1

n

n

n

n n

Y f X X X

A X E

Y g Z Y X X X Z Z X X

A

+

+ +

=

+

7/21/2019 PDF Document (92329)

81/125

Decima Settima Lezione5/12/2006

ClassiPRC Funzioni e Predicati primitivi ricorsivi

Classi PRC (rif.D.S. W . pag. 42)

DEFF.: Sia data una classe di funzioni totali, si dice che essa unaclassePRC ( primitive recursively clo-sed ) se:

1. contiene le funzioni iniziali (che definiremo tra poco);2. contiene funzioni ottenute da funzioni, che appartengono a , mediante composi

zione e ricorsione primitiva.

Le seguenti funzioni sono chiamate funzioni iniziali:

( ) 1s x x = + funzione successore ;( ) 0n x = funzione nulla ;( )1 2, , ,ni n i u x x x x = con 1 i n funzioni di proiezione .

TEOREMA 3.1: La classe delle funzioni calcolabili una classePRC.

DIM.: Dobbiamo dimostrare che le funzioni iniziali e le funzioni ottenute mediante composizione corsione primitiva da funzioni della classePRC sono calcolabili. I teoremi 1.1(composizione di funzioni), 2.1(ricorsione con una variabile) e 2.2(ricorsione con pi variabili)dimostrano parte del teorema, manca da verifica-re che le funzioni iniziali siano calcolabili, quindi bisogna esibire degliS -programmi che le computi-no. La funzione successore( ) 1s x x = + calcolata dal programma 1Y X + , mentre la funzione

( ) 0n x = calcolata dal programma vuoto, infine le (infinite) funzioni di proiezione( )1 2, , ,ni n i u x x x x = sono calcolate dai programmi i Y X .Quindi possiamo concludere che la classe delle funzioni calcolabili una classePRC.

DEF.: Una funzione detta primitiva ricorsiva (il concetto di funzione primitiva ricorsiva diverso da quellodi funzione appartenente ad una classePRC sebbene i due concetti siano strettamente connessi fra loro)se pu essere ot-tenuta dalle funzioni iniziali applicando un numero finito di volte composizione e ricorsione primda cui abbiamo:

COROLLARIO 3.2: La classe delle funzioni primitive ricorsive una classePRC, la cui dimostrazione immediata.

DEF.: Si distinguono tre sottoclassi:

1: classePRC di funzioni totali calcolabili daS -programmi; 2 : classe di funzioni primitive ricorsive; 3: classe di tutte le funzioni totali su.

7/21/2019 PDF Document (92329)

82/125

EDIT by Qd Calcolabilit XVII Lez.

80

TEOREMA 3.3 (rif.D.S. W . pag. 43): Una funzione primitiva ricorsiva se e solo se appartiene a tuttele classiPRC (quindi linsieme delle funzioni primitive ricorsive rappresenta il nucleo di ogni classePRC, intersezione ditutte le classiPRC).

DIM. : Dimostrare che se una funzione appartiene a tutte le classiPRC allora una funzione primiti- va ricorsiva una cosa abbastanza semplice, in quanto per il corollario 3.2 la classe delle funzionitiva ricorsive una classePRC (una funzione che appartiene a tutte le classiPRC per il corollario 3.2 apparterr anchealla classePRC delle funzioni primitive ricorsive, quindi deve essere necessariamente una funzione primitiva ricorsiva).

DIM. : Vogliamo ora dimostrare che se una funzione primitiva ricorsiva allora appartiene ad oclassePRC(e non solo alla classePRC delle funzioni primitive ricorsive). Sia f una funzione primitiva ricorsiva e

una classePRCqualsiasi, vogliamo dimostrare che f . Essendo f primitiva ricorsiva essa deriva( ottenuta) da una serie di funzioni1 2, , , n f f f , dove ogni funzione o deriva dalle precedenti mediantecomposizione o ricorsione, oppure una funzione iniziale. Le funzioni iniziali (per la definizione dclassePRC) appartengono alla classePRC e (sempre per definizione) vi appartengono anche tutte lefunzioni ottenute per ricorsione o per composizione, quindi f da cui (avendo considerato co-me una qualunque classePRC) abbiamo che f appartiene alla classePRC, pi precisamente f appartienea ogni classePRC.

COROLLARIO 3.4: Ogni funzione primitiva ricorsiva calcolabile(ci non vuol dire necessariamente cheogni funzione appartenente ad una classePRC qualsiasi calcolabile, si ribadisce il fatto che il concetto di funzione primitivaricorsiva differente da quello di funzione appartenente ad una classePRC). Il contrario non sempre vero, infatti esistonofunzioni calcolabili che non sono primitive ricorsive.

DIM.: La dimostrazione immediata, osservando il teorema precedente si ha che ogni funzione prim

va ricorsiva appartiene ad ogni classePRC e ciascuna classePRC costituita da funzioni calcolabili(per ladefinizione di classePRC e per il teorema 3.1).

Dagli ultimi concetti visti si pu affermare che una qualsiasi classePRC deve contenere almeno lefunzioni primitive ricorsive, in pi pu contenere altre funzioni totali purch soddisfino le propriecui devono godere le funzioni appartenenti ad una classePRC (si richiede cio che siano totali e ottenutedalle funzioni iniziali o da altre funzioni appartenenti alla classe mediante composizione e ricorsiocui si pu intuire che una classePRC potrebbe contenere anche funzioni iniziali non calcolabili,limportante che il gruppo di funzioni iniziali sia almeno rappresentato dalle infinite funzioni susore, nulla e di proiezione, ma ci non vieta che possano esistere classiPRC costitute da funzioni inizialiaggiuntive). importante fissare bene i concetti visti fino ad ora, in quanto molto di ci che segubaser su questi concetti.

Diamo ora un elenco di funzioni primitive ricorsive (e quindi calcolabili):

1) x y + ( )1 , f x y x y = +

Vediamo come ricavare la funzione adoperando solo le operazioni di ricorsione e composizione

( )( ) ( )

11 1

,0 ,, 1 , 1

f x x

f x y f x y

=+ = + da cui ricaviamo:

( ) ( )( ) ( )( )

11 1

1 1 1

,0 ,, 1 , , ,

f x u x

x y g y f x y x

=+ =

7/21/2019 PDF Document (92329)

83/125

EDIT by Qd Calcolabilit XVII Lez.

81

con ( ) ( )( )31 1 2 3 2 1 2 3 2 1, , , , x g x x x s u x x x = +=

Per comprendere meglio luso della ricorsione primitiva riscriviamo la formula utilizzando le lettereadottate per la definizione di ricorsione primitiva per funzioni a pi variabili, abbiamo:

( ) ( )( ) ( )( )

11 1 1

1 1 1

,0

, 1 , , ,,h x u x

h x t g t h x t x

=

+ =

dove chiaramenteh corrisponde a1 f , 1 x a x , t a y e g a 1 g .

Abbiamo ottenuto tali equazioni adoperando le operazioni di composizione (in particolare1 g stata ot-tenuta componendo le funzioni iniziali proiezione e successore) e ricorsione primitiva.

La funzione 1) quindi ricorsiva primitiva dunque calcolabile(sebbene gi sapessimo che tale funzione eracalcolata dal programma (d ) ora sappiamo che anche primitiva ricorsiva).

Vediamo ora un altro esempio di funzione primitiva ricorsiva:

2) x y ( )2 ,h x y x y =

ottenibile da:

( )( ) ( )

2

2 2

,0 0,, 1 ,

h x

h x y h x y x

=+ = + da cui:

( ) ( )( ) ( )( )

2

2 2 2

,0 0,, 1 , , ,

h x n x

h x y g y h x y x

= =+ =

con ( ) ( ) ( )( )3 31 2 3 1 2 1 2 3 3 1 2 3, , , , , , , g x x x f u x x x u x x x = , dove chiaramente1 f la funzionesom-ma vista prima.

Si ha difatti: ( ) ( )( ) ( ) ( )3 31 2 1 2 3 3 1 2 3 1 2 3 2 3 2, , , , , , , f u x x x u x x x f x x x x h x y x = = + = + .

Le formule viste, osservando la natura delle funzioni utilizzate, portano ad affermare che la fun2h primitiva ricorsiva.

3) ! x ( fattoriale ) ( ) ( )0! 1,1 ! ! x x s x =+ = ,

pi precisamente se ( )3! x h x = abbiamo:( )

( ) ( )( )3

3 3 3

0 1,1 ,

h

h t g t h t

=

+ =

con ( ) ( )3 1 2 1 2, g x x s x x = che primitiva ricorsiva in quanto pu essere scritta cos:

( ) ( )( )

( )2 23 1 2 1 1 2 2 1 2, , , g x x s u x x u x x = (chiaramente il prodotto usato una funzione primitiva ricorsiva),

quindi la funzione fattoriale una funzione primitiva ricorsiva.

7/21/2019 PDF Document (92329)

84/125

EDIT by Qd Calcolabilit XVII Lez.

82

Le funzioni che abbiamo visto sono state costruite mediante le funzioni iniziali che possono eimmaginate come dei mattoni, mentre la ricorsione primitiva e la composizione sono il cemento cquale costruire le funzioni primitive ricorsive; ogni volta che viene aggiunta una funzione al nostgaglio di funzioni ricorsive primitive possiamo adoperarla a mo di mattone per costruire funzionmitive ricorsive pi complesse, proprio come abbiamo fatto per la funzione3 g , per costruire la qualeabbiamo adoperato il prodotto visto in precedenza, mentre sottinteso che la funzione( )3 0h ottenu-ta da ( )0s . Osservando tale principio si ottengono le seguenti funzioni potenzae predecessore :

4) y x 0

1

1, y y

x

x x x +=

= (da notare che in questo caso00 1= );

5) ( )5 p x ( )5sese

1 00 0 x x

p x x

= = da cui abbiamo:

( )( )

5

5

0 0,1

p

p t t

=+ =

In questo caso la funzione5 p pu essere computata dalla singola istruzione: 1 X X , risulta

( ) ( ) ( )51

5 p x x = con 5 : 1 X X .

In termini di funzioni iniziali le due funzioni appena viste si ottengono come segue:

4)( ) ( )( )( ) ( )( )

4

4 4

,0 1,, 1 , , ,

h x s n x

h x t g t h x t x

= =

+ = con ( ) ( ) ( )( )3 34 1 2 3 2 2 1 2 3 3 1 2 3 2 3, , , , , , , g x x x h u x x x u x x x x x = = ;

5)( )

( ) ( )( )5

5 5 5

0 0,1 ,

p

p t g t p t

=

+ = con ( ) ( )2

5 1 2 1, g x x u t = .

Proseguiamo la rassegna di funzioni primitive ricorsive:

6) x y (differenzatra x e y ) se

0 se x y x y

x y x y

= < il puntino serve a distinguere tale funzione

da quella vista in precedenza x y il cui valore per x y < indefinito, mentre in questo caso non lo , la funzione 6

dunque totale (altrimenti non ci sarebbero neanche i presupposti per affermare che essa primitiva ricorsiva).

In termini di ricorsione primitiva la 6 diventa:

( ) ( )5

0 ,1

x x x t p x t

= + =

e in termini di funzioni iniziali abbiamo:

( ) ( )

( ) ( )( )

16 1

6 6 6

,0 ,

, 1