Informatica teorica: sintesi

I I I

–

Ogni stato del minimale è una classe della partizione e quindi si devono trovare le classi di

stati indistiguibili.

4.1 Teorema di Nerode

Sia A = (Q,∑,δ,q0,F) un automa che riconosca L.

π={Q ,Q ,...,Q } la partizione di indistinguibilità.

1 2 m

L'automa minimo che riconosce L è

MA= (Q ,∑ ,δ ,q0 ,F ) dove

M M M M M

Q ={Q ,Q ,...,Q }

M 1 2 m

q0 =[q0]

M ∈Q ∈∑

δ ([q],a)=[δ(q,a)], Ɐq AND Ɐa

M ∈

F ={ [q] | q F}

M

Affinchè la funzione di transizione sia ben definita, si deve mostrare che applicando δ a

qualunque stato di una classe si arriva alla stessa classe:

∈ ∈

(δ ([q],a)=[δ(q,a)], Ɐq Q AND Ɐa ∑)

M

se p q, allora δ(p,a) δ(q,a)

I I

5 – GRAMMATICA GENERATRICE DI PALINDROME E PARENTESI

L = Linguaggio delle palindrome

G = Grammatica che genera L

G = <{S},{a,b},S,P>

dove P sono le seguenti regole di produzione:

S -> aSa, bSb, a, b, aa, bb

L = Linguaggio delle parentesi

G = Grammatica che genera L

G = <{S},{ '(' , ')' },S,P>

dove P sono le seguenti regole di produzione:

S -> (S), ( ), S S,

6 – PUMPING LEMMA PER I LINGUAGGI REGOLARI

∈

Sia L un linguaggio regolare, allora ⱻn, Ɐw L | |w| >= n ==> w=xyz tale che:

1: y != ε;

2: |xy| <= n ∈

3: Ɐk >= 0, xy z L

k

Se si verificano tutte e 3 le proprietà, Ɐk, allora il linguaggio è regolare. Altrimenti, se cade

almeno una delle tre proprietà, il linguaggio non è regolare:

1: y = ε oppure

2: |xy| > n oppure

∉

3: ⱻk>0, t.c. xy z L

k

Esempio. Il linguaggio a b con k>0

k k

aaa.....aaabbb....bbb

******n*****|*****n*****

| x | y | z |

itero le a, ma le b restano del loro numero iniziale, quindi non siamo nel linguaggio: cade

la terza proprietà

| x | y | z |

in questo modo |xy|>n, quindi cade la proprietà 2.

6 – PUMPING LEMMA PER I CONTEXT - FREE

∈

Sia L un linguaggio CF. Esiste allora una costante n tale che se Ɐz L con |z|>=n si può

fattorizzare in z=uvwxy con:

1: |vwx| <= n

2: vx != ε ∈

i i

3: Ɐi >=0, uv wx y L

Per dimostrare che il linguaggio non sia context-free, basta far cadere almeno una delle

proprietà di cui sopra, altrimenti, per dimostrare che sia c.f. bisogna fornire una

grammatica, con le sue regole di produzione, che generi il linguaggio.

7 – AUTOMA E LINGUAGGI LOCALI, ALGORITMO DI BARRY E SETHI E

FORMULE DI COSTRUZIONE DELLA SUBSET CONSTRUCTION

(costruzione per sottoinsiemi)

Un linguaggio locale è un linguaggio che può essere descritto dalla 4pla: (INI(L),

FIN(L), DIG(L), NULL(L))

Un automa locale è un automa deterministico, non per forza completo, che

riconosce un linguaggio locale. Esso è definito:

Q = {q0} U ∑

– in q0 non entrano archi

– se NULL(L) = ε, q0 è di accettazione, altrimenti no

– ∈

tutti gli archi etichettati con a ∑ entrano nello stato q

– a

gli stati finali sono quelli corrispondenti alle lettere di FIN

– da q0 escono le transizioni per gli stati etichettati esattamente con le stesse lettere

– dell'insieme INI

le transizioni sono definite dall'insieme DIG: cioè esiste una transizione da un nodo

– ∈

q a un nodo q se 'ab' DIG

a b

Proprietà di chiusura: dati i linguaggi locali L' e L'', di alfabeti disgiunti ∑'∩∑''=Ø, risultano

locali anche i linguaggi L' U L'', concatenazione L'L'' .

Dato un linguaggio L, il linguaggio L* è locale.

7.1 Passi dell'algoritmo di Berry e Sethi

I passi da seguire per l'algoritmo di Berry e Sethi sono i seguenti 5:

1 – linearizzazione dell'espressione E, mettendo i pedici ad ogni singolo

componente dell'espressione;

2 – costruzione della 4-pla (INI,FIN,DIG,NULL);

3 – costruzione dell'automa locale A per il linguaggio dato da E';

4 – decodifica di E' togliendo la numerazione;

5 – conversione da NFA a DFA tramite subset-construction

7.1.1 Regole per la costruzione ricorsiva della 4pla (INI,FIN,DIG,NULL)

NULL

NULL(ε)=ε

NULL(Ø)=Ø ∈

NULL(a)=Ø Ɐa ∑

NULL(e U e') = NULL(e) U NULL(e')

NULL (ee') = NULL(e) ∩ NULL(e')

NULL(e*)=ε

INI

INI(Ø)=Ø

INI(ε)=Ø ∈

INI(a)={a} Ɐa ∑

INI(e U e') = INI(e) U INI(e')

INI(ee') = INI(e) U NULL(e)INI(e')

INI(e*)=INI(e)

FIN

FIN(Ø)=Ø

FIN(ε)=Ø ∈

FIN(a)={a} Ɐa ∑

FIN(e U e') = FIN(e) U FIN(e')

FIN(ee') = FIN(e') U FIN(e)NULL(e')

FIN(e*)=FIN(e)

DIG

DIG(Ø)=Ø

DIG(ε)=Ø ∈

DIG(a)=Ø Ɐa ∑

DIG(e U e') = DIG(e) U DIG(e')

DIG(ee') = DIG(e) U DIG(e') U FIN(e)INI(e')

DIG(e*) = DIG(e) U FIN(e)INI(e)

7.1.2 Subset Construction

La Subset Construction trasforma un NFA in un DFA tramite la costruzione dell'automa per

sottoinsiemi. Si parte dallo stato iniziale e si vede dove porta l'etichetta. Esempio:

q0 --> a --> q1

q0 --> a --> q4

quindi {q0} con input 'a' porta nello stato {q1,q4};

poi, per esempio, q1--> a --> {q5,q6} e q4 --> a --> {q5,q7}, quindi {q1,q4}--> a

-->{q5,q6,q7}

Si procede sempre in questa maniera, fino a completare tutti gli archi.

n

Se il numero di stati del DFA costruito è uguale a 2 (formula per il numero dei

sottoinsiemi) allora il DFA è completo.

8 – MACCHINA DI TURING

Definizione formale:

Una macchina di Turing (MT) è una 7pla M=(Q,∑,Г,δ,q0,B,F) dove:

Q è l'insieme finito degli stati

– ∑ è l'albeto di input

– ⊆Г)

Г è l'alfabeto di nastro (∑

– δ:QxГ --> QxГx{L.R} è la funzione di transizione e {L,R} è l'insieme dei simboli di

– direzione

q0 lo stato iniziale

– ∈Г

B - ∑ è il blank

– ⊆

F Q l'insieme degli stati finali

–

Infine, si richiede che (F x Г) ∩ dom (δ) = Ø

Funzionamento:

L'idea di Alan Turing (matematico da cui prende il nome la stessa macchina), era quella di

pensare ad una macchina in grado di scrivere simboli su un nastro potenzialmente infinito,

rappresentando il fatto che si abbia una quantità illimitata di carta dove registrare i risultati

parziali del calcolo.

Il nastro è formato da celle che rappresentano la quantità di memoria unitaria.

La macchina utilizza un alfabeto finito, col quale possiamo rappresentare un'infinità di dati

nel nastro. Uno dei simboli è il blank (B) che rappresenta l'assenza di simboli (spazio

bianco).

Il corpo pensante della macchina è detto controllo realizzato mediante una quantità fiita di

stati.

Il controllo della MT ha accesso al nastro attraverso una testina di lettura e scrittura che

permette di leggere o scrivere un simbolo alla volta.

x x x x x

B B B ... ... B B B

1 i-1 i i+1 n

Controllo

Il meccanismo di base di una MT è il seguente:

vi è un nastro, diviso in celle di uguale dimensione, posto in posizione orizzontale,

– che si estende all'infinito sia verso destra che verso sinistra;

vi è una testina che prima legge una cella del nastro, poi, in base a ciò che c'è

– scritto, in base allo stato in cui si trova la macchina e in base a ciò che dice la

funzione di transizione δ, si scrive un simbolo nella cella, cambia stato ed, infine, si

sposta verso sinistra o destra sul nastro.

8.1 Configurazione istantanea o ID ∈

1 – Una configurazione è una tripla (α,q,β) Г*xQxГ* dove q è lo stato attuale;

2 – αβ è la sequenza di simboli contenuti nelle celle che appartengono alla porzione di

nastro compresa tra il simbolo non-blank più a sinistra e il simbolo non blank più a destra

3 – la testina si trova sopra la cella che contiene il primo simbolo della stringa β

x x x x x

B B B ... ... B B B

1 i-1 i i+1 n

q

Quindi si ha x x ...x qx x ...x

1 2 i-1 i i+1 n

dove q è lo stato, la sequenza delle x è la porzione non-blank del nastro e la testina è

i

sopra l'i-esimo simbolo.

8.2 Computazione

Una computazione è una successione di configurazioni istantanee e si dice terminante se

dall'ultimo stato non escono transizioni.

Esistono MT che non terminano, cioè non calcolano nulla a partire da un dato input.

8.3 Mossa

Il simbolo Ⱶ indica una mossa di M da una configurazione a un'altra:

LEFT

se δ(q,x )=(p,Y,L), allora x x ...x qx x ...x Ⱶ x x ...px Yx ...x

i 1 2 i-1 i i+1 n M 1 2 i-1 i+1 n

RIGHT

se, invece, δ(q,x )=(p,Y,R), allora x x ...x qx x ...x Ⱶ x x ...x Ypx ...x

i 1 2 i-1 i i+1 n M 1 2 i-1 i+1 n

Mossa LEFT con i=1 e con i=n&Y=B

i=1 --> qx x ...x x x ...x Ⱶ pBYx ...x x ...x

1 2 i-1 i i+1 n M 2 i-1 i+1 n

i=n & Y=B --> x x ...x x x ...qx Ⱶ x x ...x x ...px

1 2 i-1 i i+1 n M 1 2 i-1 i+1 n-1

Mossa RIGHT con i=n e con i=1&Y=B

i=n --> x x ...x x x ...qx Ⱶ x x ...x x x ...x YpB

1 2 i-1 i i+1 n M 1 2 i-1 i i+1 n-1

i=1 & Y=B --> qx x ...x x x ...qx Ⱶ px x ...x x x ...x x

1 2 i-1 i i+1 n M 1 2 i-1 i i+1 n-1 n

8.4 Computazione

Una computazione è una successione finita di configurazioni istantanee.

Una computazione è terminante se parte dalla configurazione iniziale e l'ultima

configurazione è di arresto, cioè per essa non essa non è definita la funzione di

transizione.

8.5 Input e ouput

L'input è la stringa scritta sul nastro nella configurazione inziale.

L'output è la stringa scritta sul nastro in una configurazione terminante.

Un esempio con la Macchina di Turing: la somma di 2 numeri interi positivi

Prima di tutto, possiamo assumere che un numero naturale x sia rappresentato da x+1

simboli 1, quindi 0=1, 1=11, 2=111, 3=1111 ecc...

Inoltre, assiumiamo che i 2 numeri interi siano inizalmente presenti sul nastro uno di

seguito all'altro e separati dal simbolo ';' (punto e virgola)

Il simbolo '@' è il blank.

Lo spostamento a destra è identificato da 1 e lo sp