1. Classificazione dei sistemi

È importante andare a definire la Teoria generale dei sistemi, ovvero la disciplina il cui obiettivo è fornire un metodo rigoroso di analisi e sintesi di una situazione reale allo scopo di studiarne il comportamento.

Per sistema si intende un insieme di elementi distinti, in relazione fra di loro secondo leggi ben precise, che concorrono al raggiungimento di un obiettivo comune, oppure di una evoluzione comune.

I sistemi sono classificabili in 3 diverse tipologie rispetto alla natura:

• sistemi naturali
• sistemi artificiali
• sistemi misti

In seguito, andremo a capire la differenza tra queste 3 tipologie, ma prima è importante capire come ogni sistema è composto. 

Secondo la Teoria generale dei sistemi un sistema contiene:

• obiettivi da raggiungere
• parti o elementi che lo compongono
• interazioni con il mondo esterno (ingressi ed uscite)
  • interazioni manipolabili, detti anche segnali di controllo
  • interazioni non manipolabili, detti anche disturbi. Non sono prevedibili e non sono controllabili direttamente
• relazioni che descrivono i rapporti tra i vari componenti

Esistono poi i sottosistemi, ovvero dei sistemi che uniti creano un unico sistema.

Ogni sottosistema, pur essendo considerato a tutti gli effetti un sistema, concorre al raggiungimento dell’obiettivo del sistema principale di cui fa parte.

Oltre agli ingressi e alle uscite, descritte attraverso opportune variabili, esiste un’altra grandezza che caratterizza un sistema: lo stato interno. 

Lo stato interno rappresenta le proprietà intrinseche, o caratteristiche, di un sistema ovvero le informazioni necessarie e sufficienti atte a descriverne le condizioni in cui si trova il sistema in un determinato istante.

Esistono due funzioni che gestiscono i flussi all’interno di un sistema. La prima è la funzione di transizione dello stato f() che permette di calcolare quale valore assumerà lo stato del sistema s(t) in un generico istante t, in base allo stato iniziale s(t₀) e a tutti gli ingressi applicati al sistema all’istante t₀fino a t, cioè i(t).

s(t) = f(s(t₀), i(t)) 

La seconda è la funzione di trasformazione delle uscite g(), che ci permette di calcolare quale valore avrà l’uscita u(t) ad un generico istante t, conoscendo il valore dello stato e degli ingressi sempre nell’istante t.

u(t) = g(s(t₀), i(t))

È possibile identificare i sistemi in un’altra classificazione rispetto al comportamento:

• sistema aperto, ovvero i sistemi che scambiano qualcosa con l’ambiente esterno, ad esempio un televisore che necessita della corrente elettrica per funzionare;
• sistema chiuso: ovvero i sistemi che non scambiano nulla con l’ambiente esterno. È importante notare che praticamente non esistono sistemi che non interagiscono con l’ambiente esterno, al massimo possono essere chiusi rispetto a determinati elementi. Nei sistemi chiusi, l’interazione con l’ambiente esterno è secondario rispetto allo scopo primario del sistema;
• sistema deterministico, ovvero i sistemi il cui comportamento è inequivocabilmente noto. Per esempio, il tasto power-on sul telecomando è chiaro che produrrà il segnale per l’accensione del tv;
• sistema probabilistico: ovvero i sistemi in cui non c’è una corrispondenza univoca tra sollecitazione e comportamento. Per esempio, nella roulette il lancio della pallina, in teoria, dovrebbe corrispondere a un risultato casuale.
• sistema continuo, ovvero i sistemi la cui condizione in un certo istante di tempo è diversa da quella nell’istante precedente, anche se di un intervallo molto piccolo. Per esempio, un aereo che percorre un tragitto, non avrà mai la stessa posizione di un attimo prima nel momento attuale;
• sistema discreto, ovvero i sistemi che si possono trovare in un numero finito di condizioni uniche, totalmente diverse dalle altre, che rimangono stabili per un intervallo di tempo fino ad una nuova sollecitazione. Per esempio, una lampada che può essere spenta o accesa, in condizione stabile fino ad una sollecitazione;
• sistemi statici, ovvero i sistemi in cui la condizione rimane almeno apparentemente invariata nel tempo.
• sistemi dinamici, ovvero i sistemi in cui la condizione varia percettibilmente durante il periodo di osservazione;
• sistemi stazionari o invarianti nel tempo, ovvero sistemi in cui ad una certa sollecitazione il sistema risponde sempre allo stesso modo;
• sistemi istantanei o combinatori, ovvero i sistemi in cui il comportamento in risposta ad una certa sollecitazione non dipende dalla condizione del sistema stesso al momento della sollecitazione;
• sistema propriamente dinamico o sequenziale, ovvero i sistemi il cui comportamento in sistema propriamente dinamico, o sequenziale: è un sistema il cui comportamento in risposta ad una particolare sollecitazione è determinato dalla condizione in cui si trova al momento stesso della sollecitazione.

2. Concetto di automa

Prima di adoperare un elaboratore impartendogli degli ordini, è necessario fare una fase di iniziale di strategia per risolvere il problema che abbiamo da porgli.

Questa fase produce una sequenza di passi elementari per la risoluzione di un problema che viene definita con il nome di algoritmo.

L’algoritmo è composto da istruzioni, ovvero parole sistemate che specificano le operazioni da eseguire, e i dati, ovvero insieme di oggetti su cui operare.

Una macchina che esegue in maniera automatica le istruzioni contenute in un algoritmo è chiamata automa (dal greco autòmaton che significa “che si muove da sé”).

Un automa è quindi un dispositivo in grado di eseguire delle istruzioni in maniera automatica partendo da dei dati forniti in ingresso, per quindi produrre dei risultati fornendo dei dati in uscita.

Un esempio classico di automa è un ascensore. Come sappiamo un ascensore per funzionare ha bisogno di una persona che prema un pulsante per dirigersi verso un determinato piano dell’edificio. L’ascensore conosce il piano in cui è al momento della pressione del tasto e in base al tasto premuto dalla persona, si muoverà in alto o in basso nell’edificio. Possiamo quindi andare a definire le parti che compongono un automa con l’aiuto del nostro esempio. 

Il pulsante premuto dalla persona può essere considerato come ingresso, mentre il piano in cui si trova l’ascensore a fine corsa può essere considerato come uscita. Invece il livello in cui l’ascensore si trova prima di iniziare la corsa viene definito come stato dell’automa. Infine, abbiamo i due criteri: il primo che viene utilizzato per passare da uno stato ad un altro (inizio e fine corsa) e il secondo con cui il sistema emette l’output. 

Gli elementi che descrivono gli ingressi, le uscite e gli stati si dicono rispettivamente variabili di ingresso, variabili di uscita e variabili di stato.

3. Automa a stati finiti 

Una macchina a stati finiti (a volte chiamata automa a stati finiti) è un modello di calcolo che può essere implementato con hardware o software e può essere utilizzato per simulare la logica sequenziale e alcuni programmi per computer. Gli automi a stati finiti generano linguaggi regolari. Le macchine a stati finiti possono essere utilizzate per modellare problemi in molti campi, tra cui matematica, intelligenza artificiale, giochi e linguistica.

Esistono due tipi di macchine a stati finiti (FSM): macchine a stati finiti deterministici, spesso chiamate automi finiti deterministici, e macchine a stati finiti non deterministici, spesso chiamate automi finiti non deterministici. Ci sono lievi variazioni nei modi in cui le macchine a stato sono rappresentate visivamente, ma le idee dietro di loro derivano dalle stesse idee computazionali. Per definizione, gli automi finiti deterministici riconoscono, o accettano, i linguaggi regolari, e un linguaggio è regolare se un automa finito deterministico lo accetta. Gli FSM vengono solitamente istruiti utilizzando linguaggi costituiti da stringhe binarie che seguono un particolare modello.

Sia i linguaggi regolari che quelli non regolari possono essere costituiti da stringhe binarie. Un esempio di linguaggio di stringhe binario è: il linguaggio di tutte le stringhe che hanno uno 0 come primo carattere. In questo linguaggio, 001, 010, 0 e 01111 sono stringhe valide (insieme a molte altre), ma stringhe come 111, 10000, 1 e 11001100 (insieme a molte altre) non sono in questo linguaggio.

Un automa deterministico finito (DFA) è descritto da una tupla a cinque elementi: (Q,Σ,δ,q₀,F)​

Q = un insieme finito di stati

Σ = un alfabeto di input finito e non vuoto

δ = una serie di funzioni di transizione

q₀ = lo stato iniziale

F = l’insieme degli stati accettanti

Deve esserci esattamente una funzione di transizione per ogni simbolo di input in Σ da ogni stato.

I DFA possono essere rappresentati da grafi di transizione di questo tipo:

In questo grafo è possibile notare diverse componenti:

• la freccia più a sinistra solitamente viene utilizzata per indicare i simboli ricevuti in input dall’automa;
• con i cerchi si indicano gli stati dell’automa, vengono assegnati con un numero interno crescente che indica l’ordine degli stati dell’automa;
• le frecce che passano da uno stato ad un altro indicano una transizione di stato dell’automa, vengono inseriti i valori che permettono la transizione sopra la freccia (Es. per passare dallo stato q₀ allo stato q₁ è necessario ricevere in input il simbolo “1”);
• esistono anche frecce ricorsive che partono da uno stato dell’automa e ritornano sullo stesso stato. Queste frecce indicano che se ricevuto in input quel simbolo, lo stato dell’automa non varia ma rimane costante;
• il doppio cerchio indica lo stato finale dell’autom.

Siano A e B due linguaggi, definiamo le operazioni di unione, concatenazione e star come segue:

• unione: A ∪ B = {x | x ∈ A ∨ x ∈ B}, ovvero l’insieme delle stringhe che appartengono a ad almeno uno dei due linguaggi;
• concatenazione: A • B = {xy | x ∈ A ∧ y ∈ B}, ovvero l’insieme delle stringhe formate da una stringa di A seguita da una di B;
• star: A∗ = {x1x2…xk | k ≥ 0 ∧ xi ∈ A}, l’insieme di tutte le concatenazioni delle stringhe di A.

Una collezione di oggetti è chiusa rispetto ad una determinata operazione se applicando l’operazione ai membri della collezione si ottiene un oggetto appartenente ancora alla collezione. Facendo riferimento ai linguaggi possiamo dire che una classe di linguaggi è chiusa rispetto ad un’operazione se applicando l’operazione ai linguaggi della classe otteniamo ancora un linguaggio della stessa classe.

4. Automi riconoscitori

Gli automi riconoscitori sono automi che possono riconoscere la presenza di una sequenza di simboli che vengono immessi tramite l’input. È possibile, per esempio, utilizzare questi automi per conoscere delle stringhe immesse in input.

Il funzionamento parte dal primo stato in cui viene presentato in ingresso un simbolo, in base al simbolo l’automa cambia o resta nello stesso stato. L’insieme delle operazioni e la struttura data all’automa rende possibile il riconoscimento di una sequenza di simboli scelta.

Facciamo un esempio:

Vogliamo realizzare un automa che riconosce la sequenza “BOB”.

Per prima cosa è necessario utilizzare una grammatica formata dalle lettere che compongono la nostra sequenza, ovvero “B” e “O”.

Il primo stato dell’automa deve ricevere in input la lettera B e successivamente cambiare stato in quello successivo, se dovesse ricevere in input la lettera O allora rimarrebbe nello stesso stato. 

Quando passiamo allo stato successivo (ovvero il 2° stato) l’uscita del sistema y, che sarebbe l’indicatore di riconoscimento riuscito, rimane impostato a 0, cioè non è stata ancora riconosciuta la sequenza voluta.

Nel secondo stato è necessario ricevere la lettera O e quindi passare allo stato successivo, se invece riceve una R allora rimane nello stesso stato ricorsivamente, come nel prima stato.

L’automa viene costruito con questa metodologia fino a creare un automa che riceve e riconosce in input la sequenza “BOB”.

L’immagine indica lo schema dell’automa, la freccia che collega lo stato 2 con lo stato 1 con la lettera B, indica lo stato finale in cui viene riconosciuta l’intera sequenza ricercata “BOB”.

5. Tabelle di transizione 

Oltre ai grafi di transizione che abbiamo visto in precedenza, è possibile rappresentare un automa con i suoi vari stati tramite le tabelle di transizione.

Le tabelle di transizione sono tabelle con un numero di righe pari al numero degli stati dell’automa e un numero di colonne pari al numero dei diversi ingressi. Le celle contengono una coppia formata dallo stato successivo e dall’uscita da emettere. 

In questo esempio di tabella di transizione possiamo trovare sulle colonne gli ingressi (in questo caso 2) e sulle righe gli stati dell’automa (in questo caso 2).

Per esempio, se siamo nello stato 1 e viene ricevuto in ingresso il SImbolo 1, come possiamo vedere dalla tabella, lo stato dell’automa cambierà e si sposterà nello stato 2. Se invece fossimo nello stato 2 e riceviamo in ingresso il simbolo 2 allora l’automa muterà nello stato 1.

Possiamo anche andare ad inserire le uscite dell’automa con una sbarra dopo lo stato successivo, come nel seguente esempio: