di Mark Shead
Un’introduzione ai concetti dell’informatica
L’informatica ci permette di programmare, ma è possibile fare molta programmazione senza capire i concetti informatici sottostanti.
Questa non è sempre una brutta cosa. Quando programmiamo, lavoriamo ad un livello di astrazione molto più alto.
Quando guidiamo una macchina, ci preoccupiamo solo di due o tre pedali, un cambio e un volante. Si può tranquillamente utilizzare un’auto senza avere un’idea chiara di come funziona.
Tuttavia, se si vuole utilizzare un’auto al limite delle sue capacità, è necessario conoscere molto di più sulle automobili che i tre pedali, il cambio e il volante.
Lo stesso vale per la programmazione. Un sacco di lavoro quotidiano può essere svolto con poca o nessuna comprensione dell’informatica. Non c’è bisogno di capire la teoria computazionale per costruire un modulo “Contattaci” in PHP.
Tuttavia, se avete intenzione di scrivere codice che richiede un calcolo serio, avrete bisogno di capire un po’ di più su come funziona il calcolo sotto il cofano.
Lo scopo di questo articolo è di fornire alcune nozioni fondamentali sul calcolo. Se c’è interesse, potrei seguire con alcuni argomenti più avanzati, ma in questo momento voglio guardare la logica dietro uno dei più semplici dispositivi computazionali astratti – una macchina a stati finiti.
Macchine a stati finiti
Una macchina a stati finiti è un’astrazione matematica usata per progettare algoritmi.
In termini più semplici, una macchina a stati legge una serie di input. Quando legge un input, passa a uno stato diverso. Ogni stato specifica a quale stato passare, per un dato input. Questo sembra complicato ma è davvero molto semplice.
Immaginate un dispositivo che legge un lungo pezzo di carta. Per ogni pollice di carta c’è una singola lettera stampata su di esso – o la lettera ‘a’ o la lettera ‘b’.
Come la macchina a stati legge ogni lettera, cambia stato. Ecco una macchina a stati molto semplice:
I cerchi sono “stati” in cui la macchina può trovarsi. Le frecce sono le transizioni. Quindi, se siete nello stato s e leggete una ‘a’, passerete allo stato q. Se leggete una ‘b’, rimarrete nello stato s.
Quindi, se iniziamo su s e leggiamo il nastro di carta sopra da sinistra a destra, leggeremo la ‘a’ e passeremo allo stato q.
Poi, leggeremo ‘b’ e torneremo allo stato s.
Un’altra ‘b’ ci terrà su s, seguita da una ‘a’ – che ci riporta allo stato q. Abbastanza semplice, ma qual è il punto?
Beh, si scopre che si può far scorrere un nastro attraverso la macchina a stati e dire qualcosa sulla sequenza di lettere, esaminando lo stato in cui si finisce.
Nella nostra semplice macchina a stati di cui sopra, se finiamo nello stato s, il nastro deve finire con una lettera ‘b’. Se finiamo nello stato q, il nastro finisce con la lettera ‘a’.
Questo può sembrare inutile, ma ci sono un sacco di problemi che possono essere risolti con questo tipo di approccio. Un esempio molto semplice potrebbe essere quello di determinare se una pagina di HTML contiene questi tag in quest’ordine:
<html> <head> </head> <body> </body> </html>La macchina a stati può spostarsi in uno stato che mostra che ha letto il tag html, andare in loop fino al tag head, andare in loop fino al tag head close, e così via.
Se riesce ad arrivare allo stato finale, allora avete quei particolari tag nell’ordine corretto.
Le macchine a stati finiti possono anche essere usate per rappresentare molti altri sistemi – come la meccanica di un parchimetro, di una macchina per la vendita di bibite, di una pompa di benzina automatica, e ogni genere di altre cose.
Macchine a stati finiti deterministiche
Le macchine a stati che abbiamo visto finora sono tutte macchine a stati deterministici. Da qualsiasi stato, c’è solo una transizione per ogni input consentito. In altre parole, non ci possono essere due percorsi che portano fuori da uno stato quando si legge la lettera ‘a’. All’inizio, sembra stupido anche solo fare questa distinzione.
A che serve un insieme di decisioni se lo stesso input può portare a spostarsi in più di uno stato? Non si può dire ad un computer, if x == true allora esegui doSomethingBig o esegui doSomethingSmall, si può? Passa attraverso tutta la sua elaborazione, e poi lo stato finale viene letto, e poi viene intrapresa un’azione. Una macchina a stati non fa nulla mentre passa da uno stato all’altro.
Elabora, e quando arriva alla fine, lo stato viene letto e qualcosa di esterno fa scattare l’azione desiderata (per esempio, erogare una lattina di soda). Questo è un concetto importante quando si parla di macchine a stati finiti non deterministiche.
Macchine a stati finiti non deterministiche
Le macchine a stati finiti non deterministiche sono macchine a stati finiti dove un dato input da uno stato particolare può portare a più di uno stato diverso.
Per esempio, diciamo che vogliamo costruire una macchina a stati finiti che possa riconoscere stringhe di lettere che:
- iniziano con la lettera ‘a’
- e sono poi seguite da zero o più occorrenze della lettera ‘b’
- o, zero o più occorrenze della lettera ‘c’
- sono terminate dalla prossima lettera dell’alfabeto.
Le stringhe valide sarebbero:
- abbbbbbbbbc
- abbbc
- acccd
- acccccd
- ac (zero occorrenze di b)
- ad (zero occorrenze di c)
Quindi riconoscerà la lettera ‘a’ seguita da zero o più della stessa lettera di ‘b’ o ‘c’, seguito dalla lettera successiva dell’alfabeto.
Un modo molto semplice per rappresentare questo è con una macchina a stati che assomiglia a quella qui sotto, dove uno stato finale di t significa che la stringa è stata accettata e corrisponde al modello.
Vedi il problema? Dal punto di partenza s, non sappiamo quale percorso prendere. Se leggiamo la lettera ‘a’, non sappiamo se andare allo stato q o r.
Ci sono alcuni modi per risolvere questo problema. Uno è il backtracking. Semplicemente si prendono tutti i percorsi possibili, e si ignorano o si esce da quelli in cui ci si blocca.
Questo è fondamentalmente il modo in cui funziona la maggior parte dei computer che giocano a scacchi. Guardano tutte le possibilità – e tutte le possibilità di quelle possibilità – e scelgono il percorso che dà loro il maggior numero di vantaggi sull’avversario.
L’altra opzione è convertire la macchina non deterministica in una deterministica.
Uno degli attributi interessanti di una macchina non deterministica è che esiste un algoritmo per trasformare qualsiasi macchina non deterministica in una deterministica. Tuttavia, è spesso molto più complicato.
Per nostra fortuna, l’esempio qui sopra è solo leggermente più complicato. Infatti, questo è abbastanza semplice che possiamo trasformarlo in una macchina deterministica nella nostra testa, senza l’aiuto di un algoritmo formale.
La macchina qui sotto è una versione deterministica della macchina non deterministica di cui sopra. Nella macchina qui sotto, uno stato finale di t o v è raggiunto da qualsiasi stringa accettata dalla macchina.
Il modello non deterministico ha quattro stati e sei transizioni. Il modello deterministico ha sei stati, dieci transizioni e due possibili stati finali.
Non è molto di più, ma la complessità di solito cresce esponenzialmente. Una macchina non deterministica di dimensioni moderate può produrre una macchina deterministica assolutamente enorme.
Espressioni regolari
Se avete fatto qualche tipo di programmazione, probabilmente avete incontrato le espressioni regolari. Le espressioni regolari e le macchine a stati finiti sono funzionalmente equivalenti. Tutto ciò che si può accettare o abbinare con un’espressione regolare, può essere accettato o abbinato con una macchina a stati finiti.
Per esempio, il modello descritto sopra potrebbe essere abbinato all’espressione regolare: a(b*c|c*d)
Le espressioni regolari e le macchine a stati finiti hanno anche le stesse limitazioni. In particolare, entrambe possono corrispondere o accettare solo schemi che possono essere gestiti con una memoria finita.
Quindi che tipo di schemi non possono corrispondere? Supponiamo che vogliate abbinare solo stringhe di ‘a’ e ‘b’, dove ci sono un certo numero di ‘a’ seguite da un numero uguale di ‘b’. Oppure n ‘a’ seguite da n ‘b’, dove n è un certo numero.
Esempi sarebbero:
- ab
- aabb
- aaaaaabbbbbbbb
- aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb
All’inizio, questo sembra un lavoro facile per una macchina a stati finiti. Il problema è che finirete rapidamente gli stati, o dovrete assumere un numero infinito di stati – a quel punto non è più una macchina a stati finiti.
Diciamo che create una macchina a stati finiti che può accettare fino a 20 ‘a’ seguite da 20 ‘b’. Questo funziona bene, finché non si ottiene una stringa di 21 ‘a’ seguita da 21 ‘b’ – a quel punto si dovrà riscrivere la macchina per gestire una stringa più lunga.
Per ogni stringa che si può riconoscere, ce n’è una un po’ più lunga che la macchina non può riconoscere perché finisce la memoria.
Questo è noto come il Lemma del pompaggio che fondamentalmente dice: “se il vostro schema ha una sezione che può essere ripetuta (come quella) qui sopra, allora lo schema non è regolare”.
In altre parole, né un’espressione regolare né una macchina a stati finiti possono essere costruite per riconoscere tutte le stringhe che corrispondono allo schema.
Se guardate attentamente, noterete che questo tipo di schema dove ogni ‘a’ ha una ‘b’ corrispondente, sembra molto simile all’HTML. All’interno di ogni coppia di tag, si può avere qualsiasi numero di altre coppie di tag corrispondenti.
Così, mentre si può essere in grado di usare un’espressione regolare o una macchina a stati finiti per riconoscere se una pagina di HTML ha il <html>, <head>; e <body> elementi nell’ordine corretto, non si può usare un’espressione regolare per dire se un’intera pagina HTML è valida o meno – perché l’HTML non è uno schema regolare.
Macchine di Turing
Come si riconoscono i modelli non regolari?
C’è un dispositivo teorico che è simile ad una macchina a stati, chiamato macchina di Turing. È simile ad una macchina a stati finiti in quanto ha una striscia di carta che legge. Ma una macchina di Turing può cancellare e scrivere sul nastro di carta.
Spiegare una macchina di Turing richiederebbe più spazio di quanto ne abbiamo qui, ma ci sono alcuni punti importanti rilevanti per la nostra discussione sulle macchine a stati finiti e sulle espressioni regolari.
Le macchine di Turing sono computazionalmente complete – cioè tutto ciò che può essere calcolato, può essere calcolato su una macchina di Turing.
Siccome una macchina di Turing può scrivere e leggere dal nastro di carta, non è limitata ad un numero finito di stati. Il nastro di carta può essere assunto di lunghezza infinita. Naturalmente, i computer reali non hanno una quantità infinita di memoria. Ma di solito contengono abbastanza memoria in modo da non raggiungere il limite per il tipo di problemi che elaborano.
Le macchine di Turing ci danno un dispositivo meccanico immaginario che ci permette di visualizzare e capire come funziona il processo computazionale. È particolarmente utile per capire i limiti della computazione. Se c’è interesse farò un altro articolo sulle Macchine di Turing in futuro.
Perché è importante?
Allora, qual è il punto? Come ti aiuterà a creare il prossimo modulo PHP?
A prescindere dai loro limiti, le macchine a stati sono un concetto molto centrale per l’informatica. In particolare, è significativo che per ogni macchina a stati non deterministica che puoi progettare, esiste una macchina a stati deterministica che fa la stessa cosa.
Questo è un punto chiave, perché significa che puoi progettare il tuo algoritmo in qualsiasi modo sia più facile da pensare. Una volta che avete un algoritmo funzionante, potete convertirlo in qualsiasi forma sia più efficiente.
La comprensione che le macchine a stati finiti e le espressioni regolari sono funzionalmente equivalenti apre alcuni usi incredibilmente interessanti per i motori di espressione regolare – in particolare quando si tratta di creare regole di business che possono essere cambiate senza ricompilare un sistema.
Una base in Computer Science ti permette di prendere un problema che non sai come risolvere e ragionare: “Non so come risolvere X, ma so come risolvere Y. E so come convertire una soluzione per Y in una soluzione per X. Quindi, ora so come risolvere X.”
Se ti è piaciuto questo articolo, potresti apprezzare il mio canale YouTube dove occasionalmente creo un video o un cartone animato su qualche aspetto della creazione di software. Ho anche una mailing list per le persone che vorrebbero una mail occasionale quando produco qualcosa di nuovo.
Originariamente pubblicato su blog.markshead.com l’11 febbraio 2018.