●
U = {u1,u2,...um} insieme finito dei possibili simboli in uscita
●
S = {s1,s2,...,sh}insieme finito degli stati
●
f : I x S ---> U funzione delle uscite, che collega l'uscita al valore attuale
dell'ingresso e dello stato, U(t) = f(S(t),I(t))
●
g : I x S ---> P(S) funzione di transizione parziale degli stati interni
successivi, che collega al valore attuale dell'ingresso e dello stato un
sottoinsieme di S.
Linguaggi Regolari
L'insieme dei linguaggi regolari basati su un alfabeto Σ è definito ricorsivamente
come segue:
●
il linguaggio vuoto Ф è un linguaggio regolare
●
la stringa vuota ε è un linguaggio regolare
●
per ogni a Є Σ il linguaggio singleton {a} è un linguaggio regolare.
●
Se A e B sono linguaggi regolari allora A U B A o B e A* sono linguaggi
regolari
●
nessun altro linguaggio su Σ è regolare.
Tutti i linguaggi finiti sono regolari. Un altro topico esempio include il
linguaggio che consiste di tutte le stringhe dell'alfabeto {a,b} e che contiene un
numero pari di a , o il linguaggio consiste di tutte le stringhe nella forma: alcune
a seguite da alcune b.
I linguaggi regolari sono chiusi rispetto alle seguenti operazioni:
●
L complemento
●
L* stella di Kleene
●
L1 o L2 concatenazione
●
L1∪ L2 unione
●
L1∩ L2 intersezione
49