Appunti di Algoritmi e Principi dell'informatica

Automi

Modelli ingegneristici

L’ingegnere, durate 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

A

sull’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)

δ δ(δ δ((δ ε), δ(δ(q

1 1 1 1

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

∈

2) Stato iniziale: q Q

0 ⊆

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

Perciò: ∗

∈ ⟺ (q , ∈

x L δ x) F

0

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

Automi 3

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 riconoscitori

Q, I, δ, q F

0

: alfabeto di uscita

O ∗

: × → : 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) F

0 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, ∈

n

yw z L

Conseguenze del Pumping Lemma:

∅?

= ∃x ∈ ⟺ ∃y ∈ ∣y∣ < ∣Q∣

:



L L L, ∣Q∣ − 1

numero di passi massimo per arrivare allo stato finale:

Automi 4

∣L∣ = ∞? ∃x ∈ ∣Q∣ ⟸ ∣x∣ < 2∣Q∣

L, ∣Q∣ − 1

numero 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 parentesi

L 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 volte

m m

= = , > 0 ⟹ ∈ ∀r

k m+r⋅k m : non va bene, ci

x ywz, w a k a b L,

sono troppe a

= = , > 0 ⟹ + ∈ ∀r

k 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 va

x ywz, w a b k, s a a b b L

bene, si stanno mischiando le e le

a b

□

Quindi non è un automa a strati finiti.

Proprietà di chiusura dei FSA

= {L }

Sia una famiglia di linguaggi. Si dice che è CHIUSA rispetto ad

L L

i ∀L , ∈ ∈

un’operazione se .

OP L L, L OP L L

1 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

sostiturire 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 la

x

scandisce completamente (cioè la testina di lettura giunge fino alla fine di ) e,

x

giunto 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 traduttori

Q, I, q F

0

Γ alfabeto di pila (per comodità è disgiunto)

simbolo iniziale di pila

Z

0 ∗

: × (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 controllo

q : stringa ancora da leggere nel nastro di ingresso (la testina è posizionata sul

x

primo carattere di )

x

: stringa dei caratteri in pila (convenzione: sinistra-basso, alto-destra)

γ

: stringa già scritta nel nastro di uscita

z ′ ′ ′

=< [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 F

0 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 pila

b c

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

Il problema nasce dal fatto che la lettura della pila è distruttiva, perciò date le

posso 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 linguaggio

b c b c

dell’automa a pila NON è chiuso rispetto all’INTERSEZIONE.

2n

{a ∣n > 0} ∪ {a ∣n > 0}

n n n non è accettato dagli automi a pila ma

b b

2n

{a ∣n > 0} {a ∣n > 0}

n n n

e lo sono quindi si deduce che il linguaggio

b b

dell’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 utilizzaremo è 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 memoria

k

stato dell’organo di controllo

Automi 9

Azione conseguente: ′

cambiamento di stato: da a

q q

riscritttura di un carattere al posto di quello letto su ogni nastro di memoria:

′

→ ,

A A

i i

1≤ ≤

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 memoria

Z

0

[nastro di uscita tutto blank]

Testine nelle posizioni 0-esime di ogni nastro

Stato iniziale dell’organo di controllo in q

0

Automi 10

Stringa di ingresso a partire dalla 0-esima cella del nastro corrispondente,

x

seguita 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 ferma

q 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 (è diversa

dalla MT a un nastro di memoria!!!!):

ha un’unica testina e ha movimenti

illimitati da destra e a sinistra, infatti

funge da ingresso, memoria e

uscita.

2. MT a nastro bidimensionale

Automi 11

NB: le MT sono tutte equivalenti, è

possibile dimostrarlo emulando

macchine diverse e codificando i nastri

consequenzialmente

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) q

1 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 una

x

sequenza

∗

⊢ < >, ∈

c q, ε, γ q F

0

⊢ non è più univoca

Note: ⊂ : cioè gli APDN possono riconoscere un linguaggio

L(AP D) L(APND)

non riconoscibile dagli APD, di conseguenza sono più potenti.

La costruzione precedente può essere facilmetne generalizzata ottenendo

una 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+1

P(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 MND

x

che termina in uno stato di accettazione.

Può una MT deterministica stabilire se una sua corrispettiva ND accetta ,

x

ossia 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 in

esso un cammino che termina in uno stato di accettazione (algoriti di visita di

alberi mediante MT) se l’albero è finito. Altrimenti un algoritmo di vistita in

profondità potrebbe perdersi in un percorso infinito prima di arrivare a quello

che finisce in uno stato di accettazione, un’alternativa è l’utilizzo di algoritmi di

visita in ampiezza.

Conclusioni

Il non determinismo è un’utile astrazione per descrivere problemi/algoritmi di

ricerca, situazioni in cui non esistono elementi di scelta (o sono tra loro

indifferenti) e computazioni parallele.

In generale non aumenta la potenza del calcolo (almento 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è generanno

stringhe attraverso un processo di riscrittura.

Definizione formale

= (V , , ,

G V P S)

N T

: alfabeto non terminale (lettere maiuscole)

V

N : alfabeto terminale (lettere minuscole)

V

T