Algoritmi & Principi dell'informatica

Algoritmi e principi dell'informatica

Concetti fondamentali

Elementi di un linguaggio: alfabeto (insieme finito di simboli base), stringa (sequenza ordinata e finita di simboli base dell'alfabeto). Ɛ = stringa nulla cioè |Ɛ| = 0. A* = insieme di tutte le stringhe, inclusa Ɛ, su A (A = {0,1}, A* = {Ɛ, 0, 1, 00, 01, 10, …}).

Operazioni su una stringa: "." = concatenazione cioè se a = xxyy e b = xy allora a.b = xxyyxy.

Linguaggio: L è un linguaggio cioè L è sottoinsieme di A* (L ⊆ A* esempio: C, Pascal, Italiano etc.).

Operazioni sugli insiemi

• Insiemistiche: Unione, intersezione, sottrazione, negazione.
• Concatenazione: L = {0,1} L = {a,b} L .L = {Ɛ, 0, 1, a, b, 11b, abb, 010b, …}.

0 + L = {Ɛ}, L* = insieme di tutte le stringhe su L (inclusa Ɛ), L = insieme di tutte le stringhe su L (esclusa Ɛ).

Traduzione: funzione da L1 a L2 (y = f(x)) (esempio: sostituzione di a con b f(abaabb) = babbaa).

Macchine a stati finiti (FSA)

Le macchine a stati finiti hanno un insieme finito di stati. (Es: Acceso, spento). La ricezione di un ingresso crea una transizione di stato. Un FSA è formato da un insieme finito di stati, insieme finito di ingressi (alfabeto) e una funzione di transizione (δ: Q x I -> Q).

Automa riconoscitore

Sequenza di mosse: parte da uno stato iniziale ed è accettata se giunge ad uno stato finale o di accettazione.

• Formalizzazione: Sequenza di mosse δ*: Q x I* -> Q
• Stato iniziale q ∈ Q
• Stati finali o di accettazione F ⊆ Q
• Appartenenza x ∈ L <-> δ*(q ,x) ∈ F

Automa traduttore

Sequenza di mosse che parte da una stringa e ne ottiene un'altra.

• Formalizzazione: T = <Q,I, δ,q0,F,O,η> con <Q,I, δ,q0,F> come per A riconoscitore, O alfabeto di uscita e η: Q x I -> O*.
• η*: Q x I* -> O*
• Traduzione: f(x) = η*(q0,x) <-> δ*(q0,x) ∈ F

Pumping lemma

Un ciclo in un automa è percorribile da 0 a N volte. Formalmente: se x∈L e |x|>|Q| esiste un q∈Q e un w∈I tali che (x = ywz δ*(q,w) = q)n => ywz ∈ L, ∀n >= 0.

Si possono cioè "pompare" i w (fornisce una condizione necessaria ma non sufficiente per avere un linguaggio regolare). NB: Gli FSA accettano linguaggi regolari. Il pumping lemma ha come conseguenza che un FSA non è in grado di riconoscere n nL = {aⁿ bⁿ | n>0}, per contare un N qualsiasi occorre memoria (cioè numero di stati) potenzialmente infiniti.

Chiusura e operazioni sugli FSA

Dato L = {Li} (insieme di linguaggi), L è chiuso rispetto a OP <-> ∀ L1, L2 ∈ L si ha che L1 OP L2 ∈ L.

Dato R insieme di linguaggi regolari riconosciuti da un FSA, R è chiuso rispetto tutte le operazioni insiemistiche (unione, intersezione, sottrazione, complemento), rispetto alla concatenazione (".") e rispetto all'operazione di "*".

Due FSA si possono intersecare (simulare il funzionamento parallelo di due FSA A e B accoppiandoli). Formalmente: Dati A=<Q_a,I,δ_a,q_0a,F_a> e B=<Q_b,I,δ_b,q_0b,F_b> si ottiene l'intersezione <A,B> con la quintupla <Q_a x Q_b,I,δ,<q_0a,q_0b>,F_a x F_b> dove δ(<q_a,q_b>,i)=<δ_a(q_a,i),δ_b(q_b,i)>. Si dimostra che L(<A,B>)=L(A) ∩ L(B).

Due FSA si possono unire con una costruzione simile all'intersezione: <Q_a x Q_b,I,δ,<q_0a,q_0b>,F_a x Q_b U Q_a x F_b>. Un'altra possibilità è utilizzare il complemento di Morgan: A U B = !(!A ∩ !B) che però può causare problemi dettati dal fatto che δ è parziale, in alcuni casi non funziona.

Automi a pila

Arricchendo un FSA con una memoria a pila si ottiene un automa più potente, detto "a pila". Mossa dell'automa a pila può avvenire in funzione del simbolo letto dal nastro di ingresso (potrebbe leggere Ɛ), del simbolo letto dalla pila o dallo stato dell'organo di controllo (cioè cambia stato, sposta di una posizione la testina di lettura, sostituire al simbolo A letto dalla pila una stringa α di simboli o se è un traduttore scrivere una stringa nel nastro di uscita spostando di conseguenza la testina.

La stringa x in ingresso viene accettata (riconosciuta) se:

• L'automa la scandisce completamente (la testina arriva alla fine di x).
• Giunto alla fine di x esso si trova in uno stato di accettazione (come in un FSA).
• Se l'automa è un traduttore f(x) è la stringa che si trova nel nastro di scrittura dopo che x è stata scandita completamente (solo se x è accettata altrimenti f(x) = indefinito).

Un automa a pila può riconoscere aⁿbⁿ, si utilizza il concetto di "spilamento" per contare o di epsilon mossa.

Formalizzazione (traduttore)

Insieme di <Q,I,Γ,δ,q₀,Z₀,F[O,η]> con Q,I,q₀ e F[O] come in un FSA traduttore, Γ alfabeto di pila e Z₀ simbolo iniziale della pila.

δ: Q x (I U {Ɛ}) x Γ -> Q x Γ* (NB: δ parziale).

η: Q x (I U {Ɛ}) x Γ -> O* (NB: η definita dove δ è definita).

Concetto generale di "stato": c = <q,x,γ,[z]> con q stato dell'organo di controllo, x stringa ancora da leggere sul nastro di ingresso, γ stringa dei caratteri in pila e z stringa già scritta sul nastro di uscita.

Quindi: x ∈ L [z = f(x)] <-> c = <q₀,x,Z₀,[Ɛ]> |- * c = <q,Ɛ,γ,[z]>, q ∈ F. Con |- * chiusura riflessiva e transitiva di |- (con |- simbolo di transizione).

La memoria a pila di un automa a pila è LIFO. Il linguaggio L = {aⁿbⁿ |n>0} è riconoscibile da un automa a pila però L = {aⁿbⁿcⁿ |n>0} non lo è perché la memoria di un automa a pila è distruttiva (per leggerla serve cancellarne il contenuto sostituendo il carattere letto con una Ɛ). Quindi una volta contato n volte b per ogni a non rimane modo di contare c. Un automa a pila è in grado anche di riconoscere L = {aⁿb²ⁿ |n>0}, basta contare due b per ogni a, però non è in grado di riconoscere {aⁿbⁿ |n>0}U{aⁿb²ⁿ |n>0} perché se svuoto tutta la pila con b perdo memoria e se poi ci sono altre b non sono in grado di contarlo. L'insieme dei linguaggi riconosciuti da un automa a pila non sono chiusi rispetto all'unione né all'intersezione per lo stesso motivo degli FSA: il problema complementare non sempre è valido come soluzione al problema diretto perché la funzione δ è parziale, in più le Ɛ mosse possono portare a cicli che portano a non arrivare mai in fondo ad una stringa, questo comporta che la stringa non è accettata né dall'automa F né dall'automa per il problema complementare !F = Q-F.

Esistono costrutti che tolgono i cicli delle Ɛ mosse e costrutti che obbligano l'automa a decidere l'accettazione solo alla fine di una sequenza finita di Ɛ mosse ciò ci porta a concludere che non sempre si può risolvere il problema positivo con quello negativo, bisogna essere sicuri di poter "arrivare in fondo".

Macchine di Turing (MT)

Migliorando ulteriormente un AP si ottiene una Macchina di Turing (MT) a K nastri. Descrizione informale: automa con ingresso, uscita, organo di controllo e alfabeto di memoria; i nastri sono sequenze infinite di celle, esiste un carattere speciale (blank) per indicare uno spazio vuoto; le testine di lettura e scrittura funzionano come quelle durante la lettura di un carattere in corrispondenza degli AP.

La mossa della macchina di Turing avviene durante la lettura di un carattere in corrispondenza della testina del nastro di ingresso, di k caratteri in corrispondenza delle testine dei nastri di memoria oppure per la lettura dello stato dell'organo di controllo. Le conseguenze possono essere un cambiamento di stato, la riscrittura di un carattere al posto di quello letto su ogni nastro di memoria, la scrittura di un carattere sul nastro di uscita, lo spostamento delle k+2 testine (le testine di memoria e di ingresso possono spostarsi verso destra R o verso sinistra L o stare ferme S, quella del nastro di uscita può spostarsi di una posizione a destra o stare ferma e se si sposta senza aver scritto lascia il blank.

Formalizzazione: <δ,[η]>: Q x I x Γ^k -> Q x Γ^k x {R,L,S}^k x [O x {R,S}]. (NB: parziali). Una MT ha una configurazione iniziale: Z₀ seguito da tutti blank nei nastri di memoria.

• Nastro di uscita tutto blank.
• Testine nelle posizioni 0-esime di ogni nastro.
• Stato iniziale dell'organo di controllo q₀.
• Stringa di ingresso x a partire dalla 0-esima cella del nastro corrispondente seguita da tutti blank.

Una MT giunge ad una configurazione finale quando:

• Stati di accettazione F ⊆ Q, per convenzione: <δ,[η]>(q,…) = per ogni Q ∈ F.
• La macchina si ferma quando <δ,[η]>(q,…) = ┴.

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

• Dopo un numero finito di mosse la macchina si ferma (Cioè <δ,[η]>(q,…) = ┴).
• Lo stato q in cui si trova quando si ferma appartiene a F (cioè è in uno stato di accettazione).

Chiusura e operazioni sulle Macchine di Turing

Una MT è in grado di riconoscere L = {aⁿbⁿcⁿ |n>0}. Una MT è chiusa rispetto l'intersezione, l'unione, la differenza, la concatenazione e la "*". Non è chiusa rispetto al complemento. NB: MT a nastro singolo è diversa da una MT a un nastro – di memoria (il nastro unico illimitato a Sx e Dx funge sia da ingresso sia da memoria che da uscita).

Le varie versioni di MT sono tutte tra loro equivalenti rispetto alla capacità riconoscitiva e traduttiva. L'accesso alla memoria di una MT è sequenziale invece che diretto (rispetto ad una macchina di VN), questo però non incide sulla sua capacità computazionale (classe di problemi risolvibili).

Non determinismo

Un FSA non deterministico è un FSA con più percorsi possibili. Formalmente: δ(q₁,a) = {q₂,q₃} con δ: Q x I -> P(Q). Durante l'esecuzione l'automa prenderà prima una strada e poi l'altra provando ogni possibile percorso finché non giungerà ad una fine.

Formalizzazione della sequenza di mosse (δ*): δ*(q, Ɛ) = {q} e δ*(q,y.i) = ∪ q'∈δ*(q,y)δ(q',i). Una stringa x è accettata (x ∈ L) se e solo se δ*(q₀,x) ∩ F ≠ insieme vuoto. Tutti gli FSA ND possono essere trasformati in FSA D. Ogni insieme di stati implicati da un nondeterminismo viene trasformato in un singolo stato che contiene i suddetti sottostati. Questo implica che gli FSA ND non sono più potenti degli FSA D ciò non implica che sono inutili in quanto tramite un FSA ND potrebbe essere più facile formalizzare un problema. Si crea l'FSA ND e poi lo si trasforma in uno deterministico.

Automi a Pila Non Deterministici (APND)

Formalizzando si ha δ: Q x (I U {Ɛ}) x Γ -> ℤ (Q x Γ*). L'APND accetta x se esiste una sequenza C₀ |-*<q,Ɛ,γ>, q ∈ F. NB: |- non è più univoca perché può seguire più strade! Gli APND possono riconoscere un linguaggio non riconoscibile dagli AP deterministici, sono quindi più potenti degli AP normali. Gli APND sono chiusi rispetto all'unione (cosa non valida per gli AP). Continua a non sussistere la chiusura rispetto l'intersezione. Non essendo chiusi rispetto all'intersezione non può nemmeno essere chiusi rispetto al complemento. Nell'ambito del non determinismo scambiare un problema con il suo opposto non funziona.

Macchine di Turing Non Deterministiche

Formalizzazione: <δ,[η]>: Q x I x Γ^k -> ℤ(Q x Γ^k x {R,L,S}^k x [O x {R,S}]). Le configurazioni (iniziali e finali), transizioni, sequenze di transizioni e accettazioni sono definite come per una MT deterministica. Una stringa x è accettata da una MTND se e solo se esiste una computazione della MND che termina in uno stato di accettazione. Si tratta quindi di visitare l'albero delle computazioni e stabilire se una di queste termina in uno stato di accettazione oppure no quindi il non determinismo non aumenta la potenza di una MT.

Grammatiche

Grammatica: insieme di regole per costruire frasi (stringhe) di un linguaggio, genera stringhe di un linguaggio attraverso un processo di riscrittura.

Definizione formale: G = <V_t,V_n,P,S> con V_n alfabeto non terminale, V_t alfabeto terminale (V = V_t U V_n), S∈V è un elemento particolare di V detto assioma (o simbolo iniziale) e P⊆V x V* insieme delle regole di riscrittura (o produzioni sintattiche). Si ha che P = {<α,β>} e si scriverà P = {α -> β}.

Esempio: V_n = {S,A,B,C} V_t = {a,b,c,d} S P = {S->AB, BA->cCd, CBS->ab, A->Ɛ}.

Relazione di derivazione immediata (rispetto alla grammatica precedente): aaBAS => aacCdS si sostituisce la coppia di elementi con quelli che genera (in questo caso BA->cCd).

Linguaggio generato da una grammatica: insieme di tutte le stringhe costituite da soli simboli terminali derivabili (in un numero qualsiasi di passi) da S cioè L(G) = {x|x∈V* ∩ S*=>x}.

Primo esempio: L(G₁) = {aa,bb}*.