)CHEJE A FHE?EFE @AEBH=JE?= 4=
=AA ,=EAA .=?A@= LA>AH $

Algoritmi e principi dell'informatica

Raaele Daniele Facendola

November 6, 2011

Contents

1 Modelli dell'informatica 3

1.1 Linguaggi . . . 3

1.2 Automi . . . 3

1.2.1 Automi a stati niti - FSA . . . 3

1.2.2 Automi a pila - PDA . . . 4

1.2.3 Macchine di Turing - MT . . . 4

1.3 Modelli nondeterministici . . . 4

1.3.1 Automi non deterministici . . . 4

1.3.2 Reti di Petri - PN . . . 5

1.4 Confronto tra le potenze degli automi . . . 5

1.5 Grammatiche . . . 6

1.5.1 Linguaggi . . . 6

1.5.2 Conversione da automa a grammatica . . . 6

1.5.3 Conversione da grammatica ad automa . . . 6

1.6 Formalizzazione dei problemi in logica del I ordine . . . 6

1 Modelli dell'informatica

1.1 Linguaggi

• Costruiti su un alfabeto A (vocabolario), denito come un insieme nito di simboli base

• Usati per comporre stringhe, ovvero una sequenza nita di elementi dell'alfabeto (anche con ripetizioni)

• Presenza della stringa nulla ϵ, dalla lunghezza pari a 0 ( |ϵ| = 0 ).

• Le stringhe godono dell'operazione associativa e noncommtativa . di concatenazione (es: a . b, stringa a seguita dalla stringa b ). ϵ rappresenta l'elemento neutro dell'operazione considerata.

• L'insieme di tutte le possibili stringhe che è possibile costruire mediante l'alfabeto A considerato (compreso ϵ) è denito come A*. Matematicamente A* è monoide libero costruito su A mediante l'operazione ..

• E' sempre possibile denire un insieme L ⊆ A∗. Se A fosse l'alfabeto comune, L potrebbe essere la lingua italiana ad esempio o il lunguaggio C ma anche l'insieme di tutte le stringhe con un numero pari di vocali, ecc. L è chiamato linguaggio.

• I linguaggi sono insiemi e, come tali, godono delle proprietà di unione, intersezione, dierenza e negazione (denita come ¬L = A ∗ −L).

• E' possibile concatenare due linguaggi mediante l'operatore .: il risultato è l'insieme di tutte le combinazioni che si ottengono concatenando una stringa del primo linguaggio con una del secondo (ma NON il contrario!!!).

• Deniamo Lⁱcome la concatenazione di L con se stesso i volte. Per convenzioneL⁰= ϵ.

• Defniamo L∗ =∪_∞

n=0Lⁿ. e L⁺= L∗ −ϵ=∪_∞

n=1L^n

• Attenzione! ϵ ̸= ∅! ϵ.L = L , ∅.L = ∅

1.2 Automi

1.2.1 Automi a stati niti - FSA

Un automa a stato nito (FSA) è costituito da:

• Un insieme nito Q di stati qi

• Un insieme nito di ingressi I, sottoinsieme di un alfabeto qualunque A

• Una funzione di transizione (parziale) δ : Q × I → Q

Un automa può essere usato per riconoscere linguaggi (ovvero data una sequenza di simboli di input l'automa deve stabilire se la sequenza appartiene oppure no ad un insieme L di stringhe valide).

Un riconoscitore di linguaggi < Q, I, δ, q0, F >possiede un insieme di stati nali (o di accettazione) F ⊆ Q (stati per i quali l'automa decreta la validità della stringa in ingresso) e uno stato iniziale q0∈ Q (stato dalla quale l'automa inizia la sua attività).

Un automa può essere usato anche per tradurre le stringhe di un linguaggio in ingresso in altre (anche appartenenti ad un linguaggio dierente!). Agli elementi descritti sopra si aggiungono anche l'alfabeto di output O e la funzione parziale di traduzione η : Q × I → O. Un automa traduttore può pertanto essere descritto mediante la 7-upla < Q, I, δ, q0, F, O, η >. A partire dalle n-uple di cui sopra è possibile scrivere l'automa identicando in primo luogo tutti gli stati Q come circonferenze (riportanto il nome dello stato al loro interno), quindi identicando tutte le transizioni della funzione δ : Qi× Ij → Qk come frecce che partono dallo stato Qi ed arrivano allo stato Qkmediante una freccia identicata come Ij. Gli stati nali vengono cerchiati ulteriormente, mentre la funzione η segue le stesse speciche della funzione δ.

Se un automa a stati niti accetta una stringa di lunghezza superiore al numero degli stati Q, allora all'interno dell'automa è presente un ciclo che può essere ripetuto innite volte. Se partendo dallo stato iniziale raggiungiamo uno stato qualsiasi K mediante la sequenza y, e da K raggiungiamo nuovamente K mediante una sequenza w allora l'automa accetta tutte le stringhe della forma x = y.wⁿ.z, dove z è la sequenza che è necessario fornire dopo w per mandare in accettazione l'automa. La conclusione di cui sopra è chiamata pumping lemma.

(chiusura rispetto alle varie operazioni e linguaggi accettati a breve!)

1.2.2 Automi a pila - PDA

Un automa a pila fondamentalmente è un FSA arricchito mediante una memoria di tipo LIFO: per ogni transizione l'automa estrae un simbolo dalla pila e lo legge, quindi può inserire sulla stessa un qualsiasi numero di altri simboli (anche nessuno!).

L'automa potrebbe decidere anche di non leggere nulla in ingresso sfruttando i simboli sulla pila (epsilon transition).

Fondamentalmente un automa a pila si comporta esattamente come quelli visti in precedenze, quindi può fungere sia da riconoscitore di linguaggi che da traduttore (ma ovviamente avendo una memoria innita è in grado di riconoscere molti più linguaggi rispetto ai precedenti). Gracamente su ogni arco di transizione, accanto al simbolo in lettura, si fa seguire il simbolo da leggere sulla pila, seguito dal carattere / seguito a sua volta dai simboli che si vogliono impilare ( se l'automa è anche un traduttore allora dopo i simboli da impilare si fa seguire il simbolo da scrivere).

Una transizione del tipo a, Z / QT, b signica semplicemente: leggi in ingresso a e spila Z dalla memoria, quindi impila prima Q e poi T, quindi scrivi b in uscita. Formalizzando un automa a Pila è descritto dalla 9-upla < Q, I, Γ, δ, q0, Z0, F, O, η >doveΓ è l'alfabeto della pila, Z0è il simbolo iniziale della pila (non necessario), δ ridenita come δ : Q × (I ∪ {ϵ}) × Γ → Q × Γ e η : Q× (I ∪ {ϵ}) × Γ → O

(chiusura rispetto alle varie operazioni e linguaggi accettati a breve!)

1.2.3 Macchine di Turing - MT

Una macchina di Turing è un automa che può leggere dati da un nastro in ingresso, scrivere dati su un nastro di uscita e memorizzare informazioni su k nastri di memoria. Ciascun nastro di memoria è gestito attraverso una testina in grado di leggere e scrivere su di esso e successivamente spostarsi di una posizione a destra o a sinistra oppure rimanere ferme a seconda delle necessità.

La macchina di Turing uciale in realtà è costituita da un unico nastro che funge sia da nastro di ingresso, di uscita o di memorizzazione e, pur avendo lo stesso potere espressivo del modello precedente, risulta molto più complicato da studiare.

In realtà tutti i nastri di scrittura possono scrivere un simbolo speciale noto come blank ♭.

Nella congurazione iniziale la macchina di Turing:

• I nastri contengono solo ♭.

• In ogni nastro c'è un simboloZ0 come segnaposto della posizione 0-esima, tranne nel nastro di ingresso che contiene la stringa da elaborare.

• Lo stato iniziale dell'organo di controllo è q0

Come per gli altri automi, una volta fermata, la macchina può trovarsi in uno stato di accettazione o meno. In realtà la macchina potrebbe non fermarsi (il che signica che la stringa in ingresso non è accettata).

1.3 Modelli nondeterministici

1.3.1 Automi non deterministici

Gli automi non deterministici sono degli automi in grado di eettuare delle decisioni autonome a prescindere dai valori di ingresso e dallo stato dell'automa. Sono facilmente riconoscibili dal fatto che esistono degli stati che ammettono a fronte degli stessi ingressi diverse transizioni: sta alla macchina decidere quale strada seguire. In generale se uno stato possiede almeno una

problema), in realtà esegue contemporaneamente ed in parallelo tutte le possibili scelte in modo esaustivo: se una combinazione tra le tante porta la macchina in uno stato di accettazione allora l'ingresso è accettato.

Tutti i modelli visti n'ora possiedono una variante nondeterministi ma gli automi a stati niti deterministici e non hanno lo stesso potere espressivo, mentre gli automi a pila nondeterministici (NPDA) ne hanno uno più grande di quelli deterministici.

1.3.2 Reti di Petri - PN

Le reti di Petri sono un modello per gli automi non deterministici ma presentano importanti novità rispetto alle precedenti.

Gli stati sono chiamati posti e possono contenere un numero variabile di cosiddetti token (indenticati da dei pallini all'interno del posto). Gli archi possono collegare i posti solo alle transizioni e mai ad altri stati. Le transizioni rappresentano degli sbarramenti ed ammettono più archi in ingresso e più archi in uscita. La transizione è abilitata se e solo se tutti gli archi in ingresso sono collegati a stati che contengono almeno un token in essi, è disattivata in ogni altro caso. Quando una transizione si abilita (in maniera del tutto nondeterministica) gli stati collegati tramite gli archi di ingresso perdono un token, mentre tutti gli stati collegati attraverso gli archi di uscita ne ricevono uno. Se due o più transizioni sono abilitate il nondeterminismo decide quale transizione abilitare.

Una rete di Petri è descritta dalla n-upla: < P, T, IF, OF >

• P, insieme nito dei posti

• T,insieme nito delle transizioni

• IF : P × T → Nfunzione di input delle transizioni

• OF : T × P → Nfunzione di output delle transizioni Il numero di token in un determinato istante è detto marcatura:

M : P → N

In una marcatura M la transizione t è abilitata sse ∀p(M(p) ≥ IF (p, t))

Riconoscitori di linguaggi Un riconoscitore con le reti di Petri è descritto mediante la n-upla: < P, T, IF, OF, Σ, L, Mo, F >

dove

• Σ è l'alfabeto di input

• Moè la marcatura iniziale

• F è l'insieme delle marcature nali

• T è una funzione che etichetta ogni transizione con un simbolo dlel'alfabeto o ϵ(ogni transizione viene abilitata (se il numero di token lo permette) dalla lettura di un simbolo pari all'etichetta associata alla transizione)

Reti di Petri con archi inibitori Per rendere più potenti le reti di Petri, vengono introdotti i cosiddetti archi inibitori: sono degli archi che funzionano in maniera complementare a quelli nomali. Una transizione è abilitata se tutti gli stati collegati tramite gli archi in ingresso hanno almeno un token ciascuno e se tutti gli stati collegati tramite archi inibitori in ingresso non possiedono nemmeno un token.

1.4 Confronto tra le potenze degli automi

• F SA ⊂ P DA ⊂ NP DA ⊂ MT

• F SA ⊂ P N ⊂ MT

• P DA ∩ P N ̸= Ø

• NP DA ∩ P N ̸= Ø

1.5 Grammatiche

Una grammatica è un modello generativo, produce cioè stringhe di un linguaggio mediante un processo di riscrittura: partendo da una stringa di caratteri non terminali (per convenzione maiuscoli) ed applicato semplici conversioni, genera una stringa di caratteri terminali (minuscoli).

Una grammatica < VN, V_T, P, S >è denita da:

• VN: alfabeto o vocabolario nonterminale

• VT: alfabeto o vocabolario terminale

• V = VN∪ VT

• S ∈ VN elemento di VN chiamato assioma o simbolo terminale

• P ⊆ VN⁺× V^∗: insieme delle regole di riscrittura (produzioni sintattiche) della forma A → B (riscrivi la A come B)

• P = {< α, β >} per comodità scriveremo P = {α → β}

1.5.1 Linguaggi

Deniamo linguaggio generato da una grammatica L(G) = {x|x ∈ V_T^∗∧S⇒ x}, come insieme di tutte le stringhe costituite^∗ da soli simboli terminali derivabili da S (in un certo numero di passi, arbitrariamente grande).

1.5.2 Conversione da automa a grammatica

Dato un automa a stati niti vogliamo costruire una grammatica equivalente ponendo:

• VN = Q

• VT = I

• S =< q0>

• Per ogni δ(q, i) = q^′poniamo < q >→ i < q^′>, inoltre se q^′∈ F aggiungiamo < q >→ i

1.5.3 Conversione da grammatica ad automa Rispetto al caso precedente poniamo:

• Q = VN∪ {qF}

• I = VT

• < qo>= S

• F = {qF}

• Per ogni A → bC poniamo δ(A, b) = C

• Per ogni A → b poniamo δ(A, b) = qF

L'automa a stati nito ottenuto è nondeterministico.

E' possibile costruire una MT nondeterministica sulla base di una grammatica: basta scandire il nastro in ingresso alla ricerca della parte sinistra di qualche produzione (non necessariamente la prima individuata ed in modo totalmente nondeterministico) e sostituirla con la corrispettiva parte destra.

1.6 Formalizzazione dei problemi in logica del I ordine

E' possibile usare i linguaggi del primo ordine per formalizzare le proprietà dei sistemi o le speciche di un programma (o di un suo frammento) al ne di evitare ambiguità.

In quest'ultimo caso le precondizioni formalizzano il formato dei dati su cui si andrà a lavorare (questo permette ad esempio di avvantaggiarsi di tecniche più sosticate durante la stesura di un programma... se una funzione deve cercare un numero all'interno di un insieme la funzione sarà molto più eciente se si sa che l'insieme è ordinato, magari usando l'algoritmo di