Appunti di Algoritmi e Principi dell'informatica

Automi

Modelli ingegneristici

L’ingegnere, durante la fase di progettazione, utilizza modelli fisici e modelli formali (oggetti matematici).

Tramite i modelli formali:

• Si formalizza il problema: da entità reali ad astrazioni matematiche.
• Si risolve il problema.
• Si interpreta il risultato, attuando delle valutazioni nelle scelte di progetto.

NB: un modello si considera adeguato se i risultati riflettono le proprietà fisiche considerate.

Fasi dell’ingegneria del software

• 1. Analisi requisiti: documento di specifica (linguaggio naturale).
• 2. Progetto: architettura del software tramite pallogrammi (linguaggio naturale).
• 3. Implementazione: codice (linguaggio formale).

Tendenza: uso di linguaggi formali in tutte le fasi in modo tale da avere sempre a disposizione programmi eseguibili.

Caratteristiche dei modelli informatici

• Generalità.
• Flessibilità.
• Attitudine dinamica e critica: confronto modello-realtà e analisi e sintesi del modello.

Tipologie

• Modelli operazionali: macchine astratte basate sul concetto di “stato” del modello.
• Modelli descrittivi: per formulare proprietà desiderate.

Esempio: ellisse: il modello operazionale è il disegno mentre il modello descrittivo è l’equazione.

Automi 1

Il linguaggio: un metamodello

Per determinare un linguaggio servono:

• Alfabeto o vocabolario: insieme finito di simboli base.
• Stringa: sequenza ordinata e finita di elementi dell’alfabeto.

OSS 1: la stringa nulla (cioè senza caratteri) si indica con ε∗.

OSS 2: rappresenta l’insieme di tutte le stringhe che si possono costruire Asull’alfabeto .A ∗

Un linguaggio è un qualsiasi sottoinsieme di (sia finito che infinito).A

Operazioni sui linguaggi:

• Insiemistiche.
• Concatenazione.
• Traduzione: τ(x).

Conclusione: Il concetto di linguaggio e le operazioni base ad esso associate forniscono un mezzo espressivo estremamente generale per descrivere sistemi di ogni tipo, le loro proprietà e i problemi ad essi connessi.

Automi a stati finiti

Un automa è un sistema dinamico discreto a tempo invariante. Quando si trova in uno stato può accettare solo un sottoinsieme dei simboli del suo alfabeto.

Un automa a stati finiti (Finite State Automation, FSA) è un tipo di automa che permette di descrivere con precisione e in modo formale il comportamento di molti sistemi.

Un FSA è costituito da:

• Un insieme finito di stati (Q).
• Un insieme finito di ingressi (alfabeto).
• : × → Una funzione di transizione parziale: δ Q I Q.

Automi 2

Esempio di automa

FSA come riconoscitore di linguaggi?

∈ cioè: la stringa appartiene al linguaggio ?x L x L

∈ sse una sequenza di mosse parte da uno stato iniziale e giunge in uno stato x L finale o di accettazione (quindi si dice che la sequenza di mosse è accettata).

OSS: Si dice mossa uno scatto di transizione, cioè un cambiamento di stato.

Formalizzazione: ∗ ∗: × →

1) Sequenza di mosse: δ Q I Q

∗ è definita induttivamente da :δ δ

∗ (q, =δ ε) q

∗ ∗(q, = (q,δ y.i) δ(δ y).i)

Con stringa non vuota il cui ultimo carattere è .y.i i

Esempio:

∗ ∗ ∗(q , 01) = (q , 0), 1) = (q , 0), 1) = , 0), 1)δ δ(δ δ((δ ε), δ(δ(q1 1 1 1

Nota: si usa l’asterisco per indicare la ripetizione.

∈2) Stato iniziale: q Q0

⊆3) Stato/i finale/i o di accettazione: F Q

Perciò: ∗∈ ⟺ (q , ∈x L δ x) F0

Nota 2: in matematica, l’asterisco rappresenta la chiusura riflessiva e transitiva.

Automi 3

FSA come traduttore

FSA come traduttore = Data una stringa in ingresso, l’automa stampa la sua traduzione .x y τ(x)

Formalizzazione:

=< , , > , con:T Q, I, δ, q F O, η0

< , > come per gli FSA riconoscitoriQ, I, δ, q F0

: alfabeto di uscitaO

∗: × → : ciò che viene scritto in uscitaη Q I O

∗ ∗ ∗: × → da stato a stringa di outputη Q I O

∗ (q, =η ε) ε

∗ ∗(q, = (q,η y.i) η(q, y).η(δ y), i)

Esempio:

∗ ∗ ∗ ∗ ∗(q , 10) = (q , 1).η(δ (q , 1), 0) = (q , (q , 1).ε = 11η η η ε).η(δ ε),0 0 0 0 0

Perciò: ∗ ∗= (q , ⟺ (q , ∈τ(x) η x) δ x) F0 0

Analisi del modello a strati finiti

Modello semplice ma poca capacità espressiva.

Due tipi: accettori e traduttori.

Si usano i cicli per accettare linguaggi infiniti.

Linguaggi infiniti e FSA

Per accettare linguaggi infiniti si usano i cicli, governati dal Pumping Lemma.

Pumping Lemma +∈ ∣x∣ > ∣Q∣ ∈ ∈Se e allora esistono e tali che:x L q Q w I

=x ywz

∗ (q, =δ w) q

∀n ≥ 0, ∈nyw z L

Conseguenze del Pumping Lemma:

∅?= ∃x ∈ ⟺ ∃y ∈ ∣y∣ < ∣Q∣:L L L, ∣Q∣ − 1numero di passi massimo per arrivare allo stato finale:

Automi 4

∣L∣ = ∞? ∃x ∈ ∣Q∣ ⟸ ∣x∣ < 2∣Q∣L, ∣Q∣ − 1numero di passi massimo per arrivare allo stato finale: e la lunghezza∣Q∣massima di un ciclo è

Conseguenza negativa:

= {a ∣n > 0}n n rappresenta il comportamento dei linguaggi a parentesiL b

→ = "(" , = ")"a b

Non esiste alcun FSA in grado di leggerlo.

Dim:

Supponiamo per assurdo che ci sia un FSA in grado di riconoscere .L

= , > ∣Q∣m m

Consideriamo e applichiamo il P.L:x a b m

= è possibile fattorizzare in tre modi:x aaaaaaaaa...bbbbbbbbb...volte voltem m

= = , > 0 ⟹ ∈ ∀rk m+r⋅k m : non va bene, cix ywz, w a k a b L,sono troppe a

= = , > 0 ⟹ + ∈ ∀rk m m+r⋅k : non va bene,x ywz, w b k a b L,ci sono troppe b

= = , > 0 ⟹ ∈k s mk k s ms : non vax ywz, w a b k, s a a b b Lbene, si stanno mischiando le e lea b

□

Quindi non è un automa a strati finiti.

Proprietà di chiusura dei FSA

= {L }Sia una famiglia di linguaggi. Si dice che è chiusa rispetto adL Li ∀L , ∈ ∈un’operazione se .OP L L, L OP L L1 2 1 2

Si definiscono linguaggi regolari (REG) tutti i linguaggi riconosciuti dai FSA.

La famiglia dei linguaggi regolari è chiusa rispetto a:

• ∪, ∩, ¬operazioni insiemistiche:
• Concatenazione.
• *...

Automi 5

Automi a pila

Un automa a pila è un tipo di automa la cui memoria di lavoro è costituita da una pila, una struttura i cui dati possono essere estratti unicamente in ordine inverso rispetto a quello di inserimento. Automa a pila

Funzionamento

In funzione del:

• Simbolo letto dal nastro di ingresso (potrebbe anche essere la stringa vuota).
• Simbolo letto dalla pila.
• Stato dell’organo di controllo.

L’automa può:

• Cambiare stato.
• Spostare di una posizione la testina di lettura.
• Sostituire al simbolo letto dalla pila, una stringa di simboli (anche nulla) A α.
• [Se traduttore] scrivere una stringa (anche nulla) nel nastro di uscita (spostando di conseguenza la testina).

La stringa di ingresso viene riconosciuta (quindi accettata) se: l’automa laxscandisce completamente (cioè la testina di lettura giunge fino alla fine di ) e,xgiunto alla fine, esso si trova in uno stato di accettazione (come FSA).

Automi 6

Se l’automa è anche traduttore, è la stringa che si trova nel nastro diτ(x)scrittura dopo che è stata completamente scandita (solo se è accettata,x x=⊥altrimenti la traduzione è indefinita, cioè ).τ(x)

Formalizzazione di AP traduttori

< , , [O, >Γ,Automa [traduttore] a pila: Q, I, δ, q Z F η]0 0

, [O] come FSA traduttoriQ, I, q F0

Γ alfabeto di pila (per comodità è disgiunto)

simbolo iniziale di pilaZ0

∗: × (I ∪ {ε}) × → ×Γ Γ è parzialeδ Q Q δ

∗: × (I ∪ {ε}) × →Γ è definita dove è definitaη Q O η δ

< >=p, α δ(q, i, A)=w η(q, i, A)

Notazione grafica

Configurazione: concetto generale di stato della macchina.

=< [z] > :c q, x, γ, [ ]

Indico con la parte per un traduttore: lo stato dell’organo di controlloq : stringa ancora da leggere nel nastro di ingresso (la testina è posizionata sulxprimo carattere di )x: stringa dei caratteri in pila (convenzione: sinistra-basso, alto-destra)γ: stringa già scritta nel nastro di uscitaz

′ ′ ′=< [z] > ⊢ =< , , [z.w] >Transizione tra configurazioni: c q, i.y, βA, c q x βα,

′=< , > [η(q, =Caso 1: δ(q, i, A) q α i, A) w]′ =x y

′=< , > [η(q, =Caso 2: δ(q, ε, A) q α ε, A) w]′ =x i.y

∀q, =⊥ ⟹ ∀i =⊥)NB: A(δ(q, ε, A) δ(q, i, A)

Automi 7

Altrimenti: non determinismo.

Accettazione [e traduzione] di una stringa:

∗⊢ ⊢: chiusura transitiva e riflessiva di ∗∈ [z = ↔ =< , , [ε] > ⊢ =< [z] >, ∈x L τ(x)] c q x, Z c q, ε, γ, q F0 0 0 F

Proprietà degli automi a pila (soprattutto riconoscitori)

NB: quando li usiamo, definiamo un linguaggio deterministico.

{a ∣n > 0}n n n non è accettato dagli automi a pilab c

Si può applicare un’estensione del Pumping Lemma per dimostrarlo.

Il problema nasce dal fatto che la lettura della pila è distruttiva, perciò date leposso contare o le o le .a b c

∗ ∗{a ∣n > 0} = {a } ∩ {a }n n n n n n n :b c b c b c

∗ ∗{a } {a }n n n nè accettato così come , si ricava che il linguaggiob c b cdell’automa a pila non è chiuso rispetto all’intersezione.

2n{a ∣n > 0} ∪ {a ∣n > 0}n n n non è accettato dagli automi a pila mab b

2n{a ∣n > 0} {a ∣n > 0}n n ne lo sono quindi si deduce che il linguaggiob bdell’automa a pila non è chiuso rispetto all’unione.

Il linguaggio dell’automa a pila è chiuso rispetto al complemento. Non si può dimostrare in modo semplice.

Automi 8

Macchina di Turing

Alan Turing, 1912-1954

Il modello della Macchina di Turing (MT) che utilizzeremo è detto modello a k nastri.

NB: è determinato all’inizio, non può cambiare in corso d’opera.k Macchina di Turing a k nastri

Note

• La lunghezza di ogni nastro è infinita.
• Ogni nastro ha una testina che può muoversi avanti (destra) e indietro (sinistra) un carattere alla volta.
• Nelle caselle non occupate dai caratteri della stringa ci sono i caratteri vuoti, blank .b

Formalizzazione parziale della MT

La mossa:

Lettura di:

• Un carattere in corrispondenza della testina di ingresso.
• Caratteri in corrispondenza delle testine dei nastri di memoriak.
• Stato dell’organo di controllo.

Automi 9

Azione conseguente:

• ′cambiamento di stato: da aq q.
• Riscrittura di un carattere al posto di quello letto su ogni nastro di memoria:′→ ,A Ai i1≤ ≤i k.
• [Scrittura di un carattere sul nastro di uscita]+ 2.
• Spostamento delle testine:k
• Le testine di memoria e di ingresso possono:
• Spostarsi a destra ( )R.
• Spostarsi a sinistra ( )L.
• Stare ferme ( )S.
• La testina di uscita può:
• Spostarsi a destra ( )R.
• Stare ferma ( )S.

Se si sposta senza scrivere lascia un blank.

Allora:

[η] : × × → × × {R, [×O × {R,k k k+1Γ Γ Parziali!!δ, Q I Q L, S} S}]

Notazione grafica

Configurazione iniziale.

Seguito da tutti blank nei nastri di memoriaZ0

[Nastro di uscita tutto blank]

Testine nelle posizioni 0-esime di ogni nastro.

Stato iniziale dell’organo di controllo in q0

Automi 10

Stringa di ingresso a partire dalla 0-esima cella del nastro corrispondente,xseguita da tutti blank.

Configurazione finale ⊆Stato di accettazione: F Q [η], (q, ...) =⊥ ∀q ∈Per comodità, convenzione: δ, F

La stringa di ingresso è accettata se e solo se:x

• Dopo un numero finito di mosse la macchina si ferma.
• ∈lo stato in cui si trova quando si fermaq F.

NB: non è accettata se:x

• ∈la macchina si ferma in uno stato / F.
• La macchina non si ferma (va in loop).

Proprietà della MT

∩ ∪La MT è chiusa rispetto all’intersezione e all’unione , infatti una MT può facilmente simularne due sia in serie che in parallelo. Non è però chiusa rispetto al complemento.

Modelli equivalenti

• 1. MT a nastro singolo (è diversadalla MT a un nastro di memoria!!!!):ha un’unica testina e ha movimentiillimitati da destra e a sinistra, infattifunge da ingresso, memoria euscita.
• 2. MT a nastro bidimensionale.

Automi 11

NB: le MT sono tutte equivalenti, è possibile dimostrarlo emulandomacchine diverse e codificando i nastriconsequenzialmente.

Modelli operazionali non deterministici

Il non determinismo serve per progettare algoritmi di calcolo parallelo.

Rendiamo non deterministici i modelli visti fin’ora:

FSA non deterministico , = {q , }δ(q a) q1 2 3

: × → P(Q)δ Q I

Formalizzazione della sequenza di mosse:

∗ (q, = {q}δ ε) ⋃

∗ ′(q, = ,δ y.i) δ(q i)′ ∗∈δ (q,y)q

Quale linguaggio viene accettato?

∅∗∈ ⟺ (q , ∩ =x L δ x) F 0

Tra i vari modi di funzionamento dell’automa è sufficiente che uno di essi abbia successo per accettere la stringa di ingresso.

Nota: gli FSA ND non sono più potenti degli FSA D, tuttavia è possibile ricavare un FSA D da un FSA ND quindi alle volte può essere più comodo progettare un FSA ND per poi ricavare il deterministico.

Automi 12

AP non deterministici

Nota: in realtà gli AP nascono non deterministici: × (I ∪ {ε}) × → (Q ×PΓδ Q F∗ )Γ

NB: l’indice F sta per finito.

L’APDN accetta se esiste unaxsequenza

∗⊢ < >, ∈c q, ε, γ q F0

⊢ non è più univoca

Note: ⊂ : cioè gli APDN possono riconoscere un linguaggioL(AP D) L(APND)non riconoscibile dagli APD, di conseguenza sono più potenti.

La costruzione precedente può essere facilmente generalizzata ottenendouna dimostrazione costruttiva di chiusura rispetto all’unione degli APDN.

La chiusura rispetto all’intersezione continua a non esistere.

Dato che gli APDN sono chiusi rispetto all’unione ma non rispetto all’intersezione, allora non possono essere chiusi rispetto al complemento.

MT non deterministiche

[η] : × × → × × {R, [×O × {R,k k k+1P(QΓ Γδ, Q I L, S} S}])

Albero delle computazioni.

Automi 13

Note: è accettata da una MT ND se e solo se esiste una computazione della MNDxche termina in uno stato di accettazione.

Può una MT deterministica stabilire se una sua corrispettiva ND accetta ,xossia accettare a sua volta se e solo se la MT ND la accetta?x

Si tratta di percorrere l’albero delle computazioni ND per stabilire se esiste inesso un cammino che termina in uno stato di accettazione (algoritmi di visita dialberi mediante MT) se l’albero è finito. Altrimenti un algoritmo di visita inprofondità potrebbe perdersi in un percorso infinito prima di arrivare a quelloche finisce in uno stato di accettazione, un’alternativa è l’utilizzo di algoritmi divisita in ampiezza.

Conclusioni

Il non determinismo è un’utile astrazione per descrivere problemi/algoritmi diricerca, situazioni in cui non esistono elementi di scelta (o sono tra loroindifferenti) e computazioni parallele.

In generale non aumenta la potenza del calcolo (almeno nel caso delle MT) peròpuò fornire descrizioni più compatte.

Aumenta la potenza degli automi a pila.

Automi 14

Grammatiche

Le grammatiche formali sono un modello generativo, cioè generano stringhe attraverso un processo di riscrittura.

Definizione formale

= (V , , ,G V P S)N T

: alfabeto non terminale (lettere maiuscole)VN

: alfabeto terminale (lettere minuscole)VT