Automi a stati finiti

Note

Gli automi a stati finiti sono dei semplici modelli operativi di calcolo. Modellano il calcolo come una serie di passi discreti da una condizione (stato) alla successiva. Gli FSA hanno memoria del calcolo formata da un insieme finito di stati. Formalmente, è costituito da:

• L’insieme finito dei suoi stati $Q$
• L’alfabeto dei simboli in ingresso $I$
• Una funzione di transizione, che mappa una coppia in uno stato di destinazione $\delta :Q\times I\to Q$
• Stato iniziale dell’automa $q_0\in Q$
• L’insieme di stati finali $F\subseteq Q$

È possibile usare un FSA per riconoscere le parole di un linguaggio. Se l’automa, leggendo una stringa, partendo da $q_0$ termina in uno stato finale, la stringa appartiene al linguaggio.

FSA Riconoscitore

Note

Possiamo formalizzare l’accettazione di un linguaggio $L$ su $I$, da parte di un FSA $(Q,I,\delta ,q_0,F)$ come:

$$x\in L⟺{\delta }^{\ast }(q_0,x)\in F$$

Dove ${\delta }^{\ast }:Q\times I\to Q$, è una sequenza di mosse, estensione di $\delta$ induttivamente definita come:

$$\{\begin{array}{l}\forall q\in Q{\delta }^{\ast }(q,\epsilon )=q\\ {\delta }^{\ast }(q,y.i)=\delta ({\delta }^{\ast }(q,y),i)i\in I,y\in I^{\ast }\end{array}$$

Esempio

Di seguito un FSA riconoscitore per un linguaggio $L=\{\text{stringhe che cominciano con 01}\}$

Esempio

Di seguito un FSA riconoscitore del linguaggio degli identificatori del linguaggio c. Si ha che $L_{\text{id}}$ è definito su $I=\{a,b,\cdots ,z,A,B,\cdots ,Z,0,1,\cdots ,9,\_\}$:

FSA Traduttore

Note

Un FSA traduttore da $L_1$ a $L_2$ associa un simbolo letto e uno scritto a ogni transizione. Formalmente un FSA traduttore è una $7$-upla $\mathcal{A}$ $(Q,I,\delta ,q_0,F,O,\eta )$ , dove:

• $(Q,I,\delta ,q_0,F)$ sono come nell’FSA riconoscitore
• $O$ è l’alfabeto di uscita
• $\eta :Q\times I\to O^{\ast }$ è la funzione di traduzione.

Formalizziamo, analogamente a ${\delta }^{\ast }$, ${\eta }^{\ast }:Q\times I^{\ast }\to O^{\ast }$ come successione di traduzioni di elementi, e quindi come traduzione di stringhe:

$$\{\begin{array}{l}{\eta }^{\ast }(q,\epsilon )=\epsilon \\ {\eta }^{\ast }(q,y.i)={\eta }^{\ast }(q,y).\eta ({\delta }^{\ast }(q,y),i)i\in I,>y\in I^{\ast }\end{array}$$

Di conseguenza l’intero calcolo della traduzione è formalizzato come:

$$\tau (x)={\eta }^{\ast }(q_0,x)⟺{\delta }^{\ast }(q_0,x)\in F$$

Esempio

Di seguito un FSA traduttore che traduce da $L_1$ a $L_2$, entrambi definiti su $\{0,1{\}}^{\ast }$, con un numero di $O$ pari, aventi funzione di traduzione $\tau$ che dimezza gli $0$ e raddoppia gli $1$.

Pumping lemma

Note

Il pumping lemma è la formalizzazione di un comportamento ciclico in un FSA, cioè l’esistenza di un ciclo percorribile $0,1,2,\cdots ,n$ volte. Il pumping lemma afferma che se $\exists x\in L$, dove $L$ è un linguaggio riconosciuto da un FSA, con $|x|\ge |Q|$ (dove $Q$ è l’insieme degli stati), allora esistono $q\in Q$ e $w\in I^{+}$ tali che $x=y.w.z$ con $y,z\in I^{\ast }$ e ${\delta }^{\ast }(q,w)=q$, cioè esiste una sottostringa di $x$ che viene riconosciuta dall’automa effettuando un’iterazione su un ciclo di stati.

Dal pumping lemma consegue che $y.w^n.z\in L\forall n\ge 0$, che segue dal poter effettuare zero o più iterazioni del ciclo.

$$\exists x\in L_{\text{FSA}}|x|\ge |Q|⟹\exists u,v,w\in I|x=u.w.z|uv|\le n,v\ne \epsilon \forall k\in \mathbb{N}u.v^k.w\in L_{\text{FSA}}$$

Si può dire, con la condizione $L=\varnothing$, se $\exists x\in L$ allora $\exists y\in L|y|<|Q|$, cioè che se una parola ha “cicli di riconoscimento” è possibile eliminarli, ed è possibile dare in pasto le $y$ all FSA e verificare se almeno una appartiene a $L$.

Inoltre si può dire, se $|L|=\infty$, allora $\exists x\in L|Q|\le |x|<2|Q|$, cioè $x$ ha un ciclo di riconoscimento.

Limitazioni degli FSA

Un FSA non può riconoscere un linguaggio $L=\{a^n.b^{n}n\ge 0\}$. Per dimostrarlo, sia $x\in L$ con $x=a^m.b^m\frac{m}{2}>|Q|$. Applicando il pumping lemma si ha che $x=y.w.z$, con una $w$ tra le seguenti forme:

• $w=a^k$, pompando $w$ ottengo $\forall r\in \mathbb{N}{a}^{m-k}{b}^{r\cdot k}{b}^m\in L$ che è assurdo.
• $w=b^k$, pompando $w$ ottengo $\forall r\in \mathbb{N}{a}^m{b}^{r\cdot k}{b}^{m-k}\in L$ che è assurdo.
• $w=a^k{b}^h$, pompando $w$ ottengo $\forall r\in \mathbb{N}{a}^{m-k}(a^k{b}^h{)}^r{b}^{m-h}\in L$ che è assurdo.

Linguaggi regolari

Note

La famiglia di linguaggi riconoscibili con un FSA è detta famiglia dei linguaggi regolari $R$ o REG. Si ha che $R$ è chiusa rispetto a $\cup ,\cap ,\neg ,\setminus ,.,\ast ,+$.

Famiglie di linguaggi

Una famiglia di linguaggi è un insieme i cui elementi sono linguaggi $L=\{L_i\}$. $L$ è chiusa rispetto ad un operazione binaria $\star$ se $\forall L_1,L_2\in L$ vale $L_1\star L_2\in L$.

Intersezioni tra linguaggi regolari

Note

Dati due FSA riconoscitori: È possibile ottenere il riconoscitore del linguaggio intersezione facendoli funzionare insieme, con la condizione che di effettuare una transizione solo se c’è in entrambi: Formalmente, dati due FSA ${\mathcal{A}}_1:(Q_1,I_1,{\delta }_1,q,F_1)$ e ${\mathcal{A}}_2:(Q_2,I_2,{\delta }_2,s,F_2)$, si ha che l’automa intersezione ${\mathcal{A}}_{\cap }=⟨{\mathcal{A}}_1,{\mathcal{A}}_2⟩$ è dato da:

• Insieme degli stati $Q_{\cap }=Q_1\times Q_2$
• Alfabeto $I_{\cup }=I_1\cup I_2$
• Funzione di transizione ${\delta }_{\cup }(⟨q_1,q_2⟩,i)=⟨{\delta }_1(q_1,i),{\delta }_2(q_2,i)⟩$
• Insieme degli stati finali $F_{\cap }=F_1\times F_2$

Inoltre si ha che:

$$L({\mathcal{A}}_{\cap })=L({\mathcal{A}}_1)\cap L({\mathcal{A}}_2)$$

Esempio

Dati due FSA: Si ha nel FSA intersezione che lo stato in rosso non è raggiungibile dallo stato iniziale e quindi può essere eliminato, e che con la costruzione a punto fisso a partire da $⟨s_0,t_0⟩$ non viene neppure aggiunto:

Unione di linguaggi regolari

Note

Formalmente, dati due automi ${\mathcal{A}}_1:(Q_1,I_1,{\delta }_1,q,F_1)$ e ${\mathcal{A}}_2:(Q_2,I_2,{\delta }_2,s,F_2)$, l’automa unione ${\mathcal{A}}_{\cup }=⟨{\mathcal{A}}_1,{\mathcal{A}}_2⟩$ è dato da:

• Insieme degli stati $Q_{\cup }=(Q_1\times Q_2)\cup Q_1\cup Q_2$
• Alfabeto $I_{\cup }=I_1\cup I_2$
• Funzione di transizione ${\delta }_{\cup }(⟨q_1,q_2⟩,i)=\{\begin{array}{l}⟨{\delta }_1(q_1,i),{\delta }_2(q_2,i)⟩\text{se esistono }{\delta }_1(q_1,i)\text{ e }{\delta }_2(q_2,i)\\ {\delta }_1(q_1,i)\text{ oppure }{\delta }_2(q_2,i)\text{ altrimenti}\end{array}$
• Insieme degli stati finali $F_{\cup }=(F_1\times F_2)\cup F_1\cup F_2$

In alternativa è possibile applicare la legge di De Morgan:

$$L_1\cup L_2=\neg (\neg L_1\cap \neg L_2)$$

Complemento di linguaggi regolari

Note

Si ha che in ogni FSA esiste uno stato non accettante implicito, detto stato di errore. Aggiunto quello è possibile scambiare gli stati finali $F$ e gli stati non finali $Q\setminus F$.