Appunti completi corso Principi dell'informatica

L'informatica teorica e i suoi fondamenti

L'informatica teorica pone le basi per uno studio sistematico dell'informatica, quali sono i limiti teorici della computazione, i modelli automatici (automi) che formalizzano il tutto, teoria della computazione. E sarà pieno di formalismi... Affronteremo tantissimi modelli: non è possibile impararli tutti a memoria, vedremo quali sono quelli fondamentali da cui derivano tutti gli altri che possiamo inventarci noi. Per realizzare un progetto ci vuole un modello, ovvero un'astrazione della realtà che semplifica alcuni dettagli meno importanti.

Noi tratteremo modelli formali, cioè oggetti matematici che descrivono parti della realtà che vogliamo rappresentare. Dobbiamo interpretare i risultati sul modello alla realtà per il nostro progetto. Un modello è adeguato quando i risultati che fornisce hanno effettivamente utilità pratica. Questi modelli ovviamente poi sono la base su cui si costruisce un programma informatico. Tra l'altro esistono pure dei software che, dati dei requisiti in linguaggio formale, generano automaticamente degli stub di codice da cui iniziare! Quindi la specifica non è per forza espressa in un linguaggio naturale, ma direttamente in linguaggio formale.

Modelli generali e specializzati

I modelli poi devono essere generali, cioè partono da concetti di base che poi si specializzano nel caso particolare. I modelli specializzati sono tantissimi, quelli generali sono pochi e vanno saputi per generare tutto il resto. I modelli possono classificarsi in operazionali, che descrivono come cambia concretamente la realtà in base allo stato attuale e quali sono le operazioni che si possono fare sul sistema. Alcune descrizioni non sono operazionali, sono descrittive, cioè consistono nella mera specifica delle proprietà che deve avere il sistema descritto senza specificare come devono essere raggiunte queste proprietà.

Un esempio può essere l'ellisse. Il modello operazionale dice che possiamo disegnare un ellisse posando opportunamente due chiodi per i fuochi e una corda per disegnare i punti dell'ellisse. Viene detto come realizzare l'ellisse e quali operazioni bisogna fare. Secondo un modello descrittivo invece l'ellisse è il luogo dei punti che seguono l'equazione x²/a² + y²/b² = 1.

Esempi di modelli in informatica

In informatica si può fare l'esempio con un algoritmo di ordinamento. Il modello operazionale è composto dalle operazioni da compiere, per esempio, nel selection sort. Un modello descrittivo dice semplicemente di trovare una permutazione dell'array tale che l'elemento i sia minore o uguale all'elemento i+1.

Linguaggi formali

Inizieremo la nostra avventura parlando di linguaggi formali. Per parlare di un linguaggio ci serve una componente iniziale che è l'alfabeto, un insieme finito di simboli:

• Lettere romane: {a, b, c, d … z}
• Cifre: {0, 1, 2, 3 … 9}
• Cifre binarie: {0, 1}

Con questi alfabeti possiamo ottenere delle stringhe, sequenze finite di simboli alfabetici:

• Parole: a, aa, aab, baku...
• Numeri: 58362, 69, 127, 906, 07

La lunghezza di una stringa è il numero di simboli contenuti in una stringa. Se la stringa è x, la sua lunghezza si indica con |x|. |a| = 1; |191| = 3. La stringa vuota è una stringa di lunghezza zero e la indichiamo con ε, per cui |ε| = 0.

Operazioni con le stringhe

Le stringhe si possono confrontare. Due stringhe x e y sono uguali se e solo se: |x| = |y|; ∀x_i = y_i (1 ≤ i ≤ n). Ovvero hanno la stessa lunghezza e hanno gli stessi caratteri in ordine.

Le stringhe si possono concatenare. Indichiamo l'operazione di concatenazione (o prodotto) con il simbolo . per cui aaba.bdca = aababdca. Notare che:

• L'elemento neutro è la stringa vuota.
• La concatenazione di una stringa con se stessa può essere indicata come una potenza, per cui x.x = x² e x.x.x = x³.
• È un'operazione associativa ma non commutativa.

Data una stringa s, x è una sua sottostringa se esistono due stringhe y e z tali che s = yxz. Se z = ε allora y è un prefisso, mentre se y = ε allora z è un suffisso. Ogni stringa può essere sottostringa di se stessa.

La stella di Kleeni

La stella di Kleeni è un operatore unario che si applica ad un insieme di simboli e si indica con il simbolo * e rappresenta l'insieme di tutte le stringhe scrivibili con quell'alfabeto, inclusa la stringa vuota. Naturalmente è un insieme infinito! Contiene la stringa vuota, tutte le stringhe di lunghezza 1, poi lunghezza 2, 3, 4... Se A = {a, b, c} allora A* = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab...}

Strutture algebriche

Il semigruppo è una coppia <S, °> tali che S è un alfabeto chiuso rispetto a ° e ° è un operatore binario associativo. Per esempio l'alfabeto delle cifre decimali (che genera i numeri naturali) e l'operatore di addizione <N, +> formano un semigruppo dato che l'addizione è chiusa rispetto ai numeri naturali ed è un'operazione associativa.

Il monoide è un semigruppo per cui ∀x ∃u (x°u = u°x = x) ovvero che ammette l'esistenza di un elemento neutro. Riprendendo l'esempio precedente, l'addizione è anche un monoide perché ammette elemento neutro 0. Anche la moltiplicazione è un monoide perché è associativa, chiusa rispetto all'insieme N ed ha elemento neutro 1.

Il gruppo è un monoide tale che ∀x ∃x^-1 (x°x^-1 = x^-1°x = u) ovvero che ammette l'esistenza di un elemento inverso. L'addizione sui numeri naturali quindi non è un gruppo, perché l'elemento inverso è un numero negativo, fuori dall'insieme N.

Linguaggi e automi

Linguaggi come insiemi di stringhe

Un linguaggio è un insieme di stringhe formato su un alfabeto. Linguaggi possono essere le lingue naturali come l'italiano, l'inglese, l'ungherese, ma anche i linguaggi di programmazione C, Java, Python e lo sono persino i linguaggi grafici, la musica, il multimedia! Un linguaggio come l'italiano è infinito, perché non ha un limite superiore alla lunghezza delle parole, delle frasi, dei libri che si possono scrivere.

Più formalmente un linguaggio L su un alfabeto A è un sottoinsieme del monoide libero A*. Se ci pensi è verissimo. Dato che i linguaggi sono sottoinsiemi, possiamo applicare tutte le operazioni degli insiemi che abbiamo visto in precedenza:

• Unione: L₁ ∪ L₂ è il linguaggio contenente stringhe di L₁ più quelle di L₂.
• Intersezione: L₁ ∩ L₂ è il linguaggio contenente stringhe contenute sia in L₁ che in L₂.
• Differenza: L₁ – L₂ è il linguaggio L₁ a cui vengono tolte le stringhe di L₂.
• Complementazione: CL equivale a A* - L.
• Concatenazione: L₁ . L₂ = {x.y | x ∈ L₁, y ∈ L₂}.
• Elevamento a potenza: L⁰ = {ε} e Lⁱ = L^i-1.L.
• Chiusura di Kleeni: L* = Unione con n da 0 a ∞ di Lⁿ.

I linguaggi, se sono finiti, possono essere rappresentati come una lista di tutte le stringhe possibili, altrimenti (come nella maggior parte dei casi) devono essere rappresentati in maniera compatta con una notazione matematica/insiemistica. Ma cosa possono rappresentare questi linguaggi? Per noi sono solo insiemi di stringhe, ma il loro scopo è rappresentare informazioni e il modo in cui elaborarle.

Automi a stati finiti

Gli automi a stati finiti sono il modello operazionale più semplice, in cui il sistema ha un numero finito di stati possibili, esempio {on, off}, {1, 2, 3, 4, 5, 6 … k}, canale TV ecc. Essi possono essere rappresentati graficamente con cerchi contenenti il nome dello stato. Hanno un insieme di simboli in ingresso, appunto un alfabeto! E ciascun simbolo alfabetico rappresenta un impulso che l'automa riceve dal mondo esterno. In base ai vari impulsi, lo stato può cambiare e si hanno delle transizioni. Graficamente le transizioni sono frecce che vanno da uno stato all'altro.

Un esempio del flip flop! Gli FSA sono il modello più semplice di computazione e molti strumenti si possono realizzare così, ma ci sono limitazioni che vedremo più avanti. Definiamolo formalmente: un automa a stati finiti è una tupla di tre elementi <Q, A, δ> dove:

• Q è l'insieme finito degli stati.
• A è l'alfabeto di ingresso (insieme di impulsi esterni).
• δ è la funzione di transizione, cioè la specifica di come il sistema deve evolversi in Q quando riceve A, una funzione Q × A → Q.

La funzione può essere parziale, cioè non essere definita per ogni coppia (Q, A), altrimenti è detta totale. Un FSA con una funzione totale è detto completo. Per realizzare un FSA che riconosca i linguaggi, è necessario definire uno stato iniziale e uno finale. Questo modello quindi deve contenere non solo stati, input e transizioni, ma anche stati iniziali e finali. Graficamente gli stati iniziali sono cerchi con una freccia entrante, mentre gli stati finali sono due cerchi uno dentro l'altro. La tupla completa quindi ha cinque elementi <Q, A, δ, q₀, F> con:

• q₀ ∈ Q lo stato iniziale (ne consideriamo solo uno).
• F ⊆ Q l'insieme degli stati finali.

Presa una sequenza di input esterni, essa è una sequenza di accettazione se, al termine, raggiunge uno degli stati finali. Queste sequenze sono di fatto stringhe :) Data una sequenza di passi, qual è lo stato che raggiungo applicando vari input?

δ*: Q × A* → Q

La funzione δ* è definita ricorsivamente come:

• δ*(q, ε) = q
• δ*(q, y.i) = δ(δ*(q, y), i)

Un esempio pratico se no non capisci più: riconoscitore di variabili C. Il linguaggio di un automa è dato dall'insieme di tutte quelle stringhe per cui da uno stato iniziale raggiungi uno stato finale. Dall'esempio precedente è chiaro che, data una funzione parziale, possiamo renderla totale aggiungendo uno stato di errore in cui si troverà l'automa se riceve un input non definito.

Trasduttori a stati finiti

I trasduttori a stati finiti sono una variante degli FSA. Questi ultimi avevano un solo nastro di ingresso con cui cambiavano stato. Gli FST invece dispongono anche di un nastro di uscita per cui possono comunicare con l'esterno scrivendo le loro "stringhe" e funzionano come una sorta di traduttore. Possono essere definiti con l'equazione y = τ(x) dove:

• x è l'input.
• y è l'output.
• τ è una funzione di traduzione dal linguaggio L₁ a L₂.

Questa funzione di traduzione può essere una stupidata come inverti le lettere a e b, oppure raddoppia le occorrenze di 1, ma anche qualcosa di più utile come un compressore di file, un compilatore, un traduttore italiano-inglese. Graficamente la traduzione è indicata sulle frecce nella forma input/output.

Vediamo un esempio importante: questo traduttore raddoppia le occorrenze di 1 e dimezza quelle di 0. Che stringhe accetta? Risposta: quelle con un numero pari di zeri, anche nessuno. Formalmente un FST è una tupla <Q, I, δ, q₀, F, O, η> dove:

• O è l'insieme degli output accettati.
• η è una funzione Q × I → O*.

La traduzione è effettuata solo sulle stringhe accettabili. Come abbiamo fatto per δ*, definiamo η* ricorsivamente:

• η*(q, ε) = ε
• η*(q, y.i) = η*(q, y).η(δ*(q, y), i)

Pumping lemma

Esaminiamo il potere espressivo di questa classe di automi. Per come sono fatti, è possibile che determinate sottostringhe formino un ciclo, ovvero una sequenza di caratteri che da uno stato portano allo stesso stato di partenza e che può essere ripetuta un numero indefinito di volte. Questo implica che gli automi a stati finiti accettano linguaggi di cardinalità infinita. Più formalmente, se x ∈ L e |x| ≥ |Q| allora deve esistere q ∈ Q e w ∈ L tale che:

• x = ywz
• δ*(q, w) = q

In soldoni: se una stringa è più lunga del numero di stati dell'automa, sicuramente esiste una sua sottostringa non vuota che compone un ciclo. Ne consegue che ∀n ≥ 0 yⁿwⁿz ∈ L. Questa caratteristica è chiamata pumping lemma.

Il pumping lemma ci permette di "decidere" (parola importante) se il linguaggio di un determinato FSA ha cardinalità nulla o infinita. Verificare la cardinalità nulla significa controllare la sua vacuità (o emptyness) e senza pumping lemma sarebbe un disastro: dovremmo provare tutte le stringhe possibili. Se ne accetta una allora non è vuoto, se non la accetta continuo, ma tutte le stringhe possibili sono infinite, quindi, se un automa ha un linguaggio vuoto, ci vorrebbe un'eternità di tempo per verificarlo, per questo non si tratta di una procedura di decisione. Con il pumping lemma invece abbiamo una procedura di decisione, perché richiede un tempo finito.

Ovvero prendiamo una stringa qualsiasi che ipotizziamo possa essere accettata dall'automa: se questa ha lunghezza maggiore o uguale al numero di stati, esisterà sicuramente una sottostringa più corta del numero di stati che corrisponde all'attraversamento di cicli nell'automa. Ciò significa che per testare la vacuità del linguaggio di un automa non dobbiamo provare un'infinità di stringhe, ma solo quelle con lunghezza minore del numero di stati. Potrebbero essere un numero grande, ma sicuramente finito!

Possiamo anche verificare se l'automa ha un linguaggio di cardinalità infinita controllando un numero limitato di stringhe. Abbiamo detto che se in un automa esistono dei cicli, allora il suo linguaggio ha cardinalità infinita, perché ogni ciclo può essere percorso un numero arbitrario di volte. Questo vuol dire che, per verificare la condizione di cardinalità infinita, non dobbiamo testare infinite stringhe, ma solo quelle di lunghezza compresa tra Q (incluso) e 2Q (escluso), cioè tutte quelle che possono generare un singolo ciclo. Se almeno una stringa in quell'intervallo è accettata, allora il linguaggio dell'automa ha cardinalità infinita.

Limiti degli FSA

Vediamo però ora alcuni aspetti negativi degli FSA: non possono riconoscere tutti i linguaggi. Per esempio L = {aⁿbⁿ | n > 0} non è riconoscibile da nessun FSA e lo dimostriamo con il pumping lemma. Pensiamo per assurdo che un FSA possa riconoscere un linguaggio del tipo a^mb^m con n > |Q|. Secondo il pumping lemma avremmo tre casi:

• x = ywz con w = a^k k > 0 → a^ka^kb ∈ L k → Non è vero
• Stessa cosa con w = b
• x = ywz con w = a^kb^s k, s > 0 → a^ka^kb ∈ L k → Non è vero

Non so manco io che vogliono dire queste cose. Fa niente. Comunque il concetto è che gli FSA non sanno contare un numero arbitrario di volte. Potremmo tranquillamente fare un linguaggio del tipo aⁿb^m con n compreso tra 1 e 4, ma non con n qualsiasi. Non potremmo quindi usare un FSA per fare, per esempio, un controllo del bilanciamento delle parentesi in un'espressione matematica o in un linguaggio di programmazione, perché non esiste un limite superiore. Beh in teoria qualsiasi computer alla fine è a stati finiti perché c'è sempre un limite alla memoria massima, ma non avrebbe senso considerare un computer al pari di un FSA per quanto riguarda l'astrazione.

Operazioni sugli FSA

Definiamo le operazioni che si possono compiere sugli FSA. Ogni tipo di automa appartiene ad una classe di automi che può interpretare una certa famiglia di linguaggi che indichiamo con L. In particolare, l'insieme dei linguaggi interpretabili da un FSA si chiama classe dei linguaggi regolari e la indichiamo con R. È una classe chiusa in tutte le operazioni che conosciamo, anche la concatenazione e la stella di Kleeni.

L'intersezione di due automi è un automa che comprende il linguaggio intersezione. Formalmente, dati:

• A₁ = <Q₁, I, δ₁, q₀₁, F₁>
• A₂ = <Q₂, I, δ₂, q₀₂, F₂>

<A₁, A₂> = <Q₁ × Q₂, I, δ, <q₀₁, q₀₂>, F₁ × F₂>

• δ(<q₁, q₂>, i) = <δ₁(q₁, i), δ₂(q₂, i)>

Come detto, il linguaggio dell'automa intersezione è l'intersezione dei linguaggi. L'unione si costruisce in modo simile:

• A₁ = <Q₁, I, δ₁, q₀₁, F₁>
• A₂ = <Q₂, I, δ₂, q₀₂, F₂>

<A₁, A₂> = <Q₁ × Q₂, I, δ, <q₀₁, q₀₂>, F₁ × Q₂ ∪ Q₁ × F₂>

• δ(<q₁, q₂>, i) = <δ₁(q₁, i), δ₂(q₂, i)>