Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

PRINCIPALI DI

•ARGOMENTI

INFORMATICA TEORICA

chiusura linguaggi regolari e context-free (dimostrazione)

quintupla di A e A complemento

dato il linguaggio { (a^n b)* | con n pari } scrivere l' automa e complemento

che vuol dire automa minimo? (definizione)

• vuol dire che due stati sono indistinguibili?

•cosa

minimale è unico?

•il

i problemi P e NP ? (spiegazione)

che vuol dire tempo polinomale?

Scrivere la grammatica delle stringhe palindrome

Scrivere la grammatica delle parentesi

CNF e trasformazione di una grammatica

lemma di iterazione (P. Lemma 2, dimostrazione)

• verifichiamo se due automi riconoscono lo stesso linguaggio?

•Come

automa minimo unico? (dimostrazione per assurdo)

Problemi: emptyness , inclusion (spiegazione e dimostrazione)

Berry e Sethy (spiegazione algoritmo)

Linguaggi Locali (definizione e quadrupla)

NFA e DFA hanno la stessa potenza? (dimostrazione con subset)

Macchina di Turing

• chi dice che la macchina di turing riesce a calcolare tutte le funzioni?

(Turing/Church)

descrizione e spiegazione della macchina (con settupla)

transizioni della macchina per fare la somma di due numeri

• 1 - CHIUSURA DEI LINGUAGGI REGOLARI

I linguaggi regolari sono chiusi per:

unione

– intersezione

– complemento

1.1 Chiusura per intersezione

∈ ∈

Teorema: Se L1 e L2 REC, allora L1 ∩L2 REC

Dimostrazione per costruzione. Si costruisce un automa che rinosce l'intersezione dei 2

linguagggi:

siano A1 e A2 due automi, anche incompleti, che riconoscono rispettivamente i linguaggi

L1 ed L2

L1=L(A1), L2=L(A2)

A1 = (Q,∑,δ ,q0 ,F ) A2 = (Q,∑,δ ,q0 ,F )

1 1 1 2 2 2

si costruisce l'automa per intersezione A = (Q,∑,δ,q0,F) dove

∈ ∈

Q= {(q1,q2)|q1 Q1 AND q2 Q2} cioè Q=Q1xQ2

q0=(q0 ,q0 )

1 2

δ=((q1,q2),a)=(δ (q1,a),δ (q2,a)) Ɐa per cui ⱻ entrambe le transizioni

1 2

∈ ∈

F={(q1,q2)|q1 F1 AND q2 F2} cioè F=F1xF2

È semplice provare che A rinosce L1∩L2

w è accettata dall'automa costruito:

δ*((q0 ,q0 ),w) F1xF2

1 2 ∈

(δ *(q1,w),δ *(q2,w)) F1xF2

1 2

∈ ∈

w L1 AND w L2

w ( L1∩L2)

1.2 Chiusura per complemento

∈ ∈

c

Teorema: se L REC, L REC

Dimostrazione per costruzione. Si costruisce un automa che riconosce il complemento

c

L = ∑* - L c c

Dato A = (Q,∑,δ,q0,F) che riconosce L, si costruisce A = (Q,∑,δ,q0,F )

si completa l'automa, quindi bisogna sempre dichiarare l'alfabeto rispetto al quale si

– vuol fare la costruzione

gli stati di accettazione diventano di non accettazione e viceversa

c c

A riconosce L . c c

Se A riconosce L=stringhe num pari di 1, allora A riconosce L stringhe num dispari di 1.

1.3 Chiusura per unione

∈ ∈

Teorema: se L1 e L2 REC, allora (L1 U L2) REC

Ci sono 2 modi per dimostrarlo:

1 – tramite la legge di Morgan:

c c c c c c

L1 U L2 = (L1∩L2) ==> (L1 U L2) = (L1 U L2 )

2 – per costruzione:

siano A1 e A2 due automi che riconoscono rispettivamente i linguaggi L1 e L2, ipotizzati

completi A1 = (Q,∑,δ ,q0 ,F ) A2 = (Q,∑,δ ,q0 ,F ), si costruisce l'automa unione

1 1 1 2 2 2

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

∈ ∈

Q= {(q1,q2)|q1 Q1 AND q2 Q2} cioè Q=Q1xQ2

q0=(q0 ,q0 )

1 2 ∈

δ=((q1,q2),a)=(δ (q1,a),δ (q2,a)) essendo l'automa completo, Ɐa ∑ ⱻ tutte le transizioni

1 2

∈ ∈

F={(q1,q2)|q1 F1 OR q2 F2} (non solo F=F1xF2)

Si può provare che A riconosce (L1 U L2), fanendo l'unione tramite l'ε-transizioni.

Altre operazioni regolari sono: concatenazione, differenza insiemistica, reverse, star di

Kleene. 2 - CHIUSURA DEI LINGUAGGI CONTEXT-FREE

(linguaggi liberi dal contesto)

2.1 Chiusura per unione

Siano <∑ ,V ,S ,P > e <∑ ,V ,S ,P > due linguaggi non contestuali, la loro unione diventa:

1 1 1 1 2 2 2 2

<∑ U ∑ , V U V U {S'}, S', P U P > dove S' -> S U S nuovo assioma.

1 2 1 2 1 2 1 2

Si ottiene così una grammatica non contestuale, che genera l'unione di 2 linguaggi.

2.2 Chiusura per concatenazione

avendo <∑ U ∑ , V U V U {S'}, S', P U P > aggiungiamo la regola di produzione

1 2 1 2 1 2

S' -> S U S ed S' è il nuovo assioma.

1 2

2.3 Chiusura per iterazione

Dato <∑ ,V ,S ,P > si ha <∑ ,V U {S'},S',P> aggiungiamo S'->S S'|ε e usiamo S' come

1 1 1 1 1 1 1

nuovo assioma.

2.4 Chiusura per intersezione

L'intersezione di due linguaggi c.f. non è necessariamente c.f.

n n m n m n n n n

Es. {a b c |n>=1}^{a b c |n>=1} non è context free perchè viene a b c che non è cf.

2.5 Chiusura per complemento

La chiusura per complemento non è necessariamente context free e lo si dimostra con De

1c 2c c

Morgan (L U L ) = L1∩L2 e l'intersezione non è necessariamente context free.

3 – DFA E AUTOMA MINIMALE

Un DFA (quintupla Q,∑,δ,q0,F) è un automa a stati finiti deterministico che, dopo aver letto

una sequenza in input, si ferma in un singolo stato. Esso è composto da 5 componenti:

Q insieme degli stati;

– ∑ insieme dei caratteri di input;

– δ(q,a) funzione di transizione;

– q0 stato iniziale;

– F stato finale o di accettazione che è incluso in Q; possono esistere più stati finali.

Tra tutti gli automi equivalenti, l'automa minimale è quello con il minor numero di stati:

per i DFA il minimale è unico;

– per gli NFA il minimale non è unico

Minimizzare un automa significa trovare il minimale equivalente. Esistono vari algortimi di

minimizzazione: 2

algoritmo di Moore O(n )

– algoritmo di Hopcroft O(n log n)

– algorimo di Brzozowski (tempo esponenziale)

dove n=numero di stati dell'automa da minimizzare

4 – RELAZIONE DI INDISTINGUIBILITÀ

La relazione di indistinguibilità è una relazione tra gli stati di un automa.

Sia A = (Q,∑,δ,q0,F) un DFA e {p,q} Q.

∈∑* ∈ ∈

Allora, pIq <=>Ɐw | δ*(p,w) F <=> δ(q,w) F.

Invece, p e q sono distinguibili se:

∈ ∈ ∉

ⱻw ∑* | δ*(p,w) F AND δ*(p,w) F o viceversa.

La relazione di indistiguibilità è una relazione di equivalenza:

∈Q

proprietà riflessiva: p p Ɐp

I

– ∈Q

proprietà simmetrica: p q => q p Ɐp,q

I I

– ∈

proprietà transitiva: p q, q r => p r Ɐp,q,r Q

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 β


ACQUISTATO

1 volte

PAGINE

21

PESO

229.35 KB

AUTORE

astrex

PUBBLICATO

11 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Palermo - Unipa
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher astrex di informazioni apprese con la frequenza delle lezioni di Informatica teorica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Palermo - Unipa o del prof Castiglione Giuseppe.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Sintesi basi dati
Appunto
Riepilogo di Metodi Matematici per Informatica
Appunto
Sintesi del Corso di Sistemi Operativi
Appunto
Riepilogo JAVA Prima Parte
Appunto