tendenzialmente più semplice.
3.2 Linguaggi regolari , automi a stati finiti
Alla base di tutta l'informatica vi sono due concetti fondamentali, che risultano
strettamente interconnessi tra loro: quello di automa e quello di linguaggio.
Il concetto di automa può essere introdotto come segue:
●
per automa si intende un dispositivo che stabilisce una precisa relazione
tra un dato di ingresso e un dato di uscita, soddisfacendo ai seguenti
vincoli di realizzabilità fisica:
●
se l'automa è fatto di parti, queste sono in numero finito;
●
l'ingresso e l'uscita sono denotabili attraverso un insieme finito di
simboli.
In questo modo non si considera alcun aspetto “fisico” o tecnologico specifico.
L'automa potrebbe essere realizzato da un insieme di dispositivi elettronici
digitali oppure dispositivi meccanici o biologici. L'obiettivo è di astrarre dai
singoli, specifici casi concreti elencando le caratteristiche ritenute essenziali.
Il risultato di questo processo di astrazione consiste nella definizione di
opportuni modelli matematici, cioè di sistemi formali che definiscono di fatto il
concetto stesso di computabilità, cioè costituiscono l'ossatura portante della
teoria della computabilità. Un automa a stati finiti(ASF) è un sistema dinamico,
invariante, discreto nell'avanzamento e nelle interazioni nel quale gli insiemi dei
possibili valori di ingresso, uscita e stato sono insiemi finiti.
●
Dinamico: evolve nel tempo passando da uno stato all'altro in funzione
dei segnali d'ingresso e dello stato precedente;
●
Invariante: a parità di condizioni iniziali il comportamento del sistema è
sempre lo stesso;
47