2. Automi e linguaggi regolari

La teoria della computazione studia la creazione di modelli di computazione sotto diversi aspetti, ognuno dei quali ha caratteristiche diverse in base a quello che necessitiamo. Il più semplice è l'automa finito rappresentato da una quintupla $(Q, \sum, \delta. q_0, F)$ dove Q rappresenta un insieme finito che contiene tutti gli stati dell'automa, mentre $\sum$ è l'insieme finito chiamato alfabeto, mentre $\delta$ rappresenta la funzione di transizione: $\delta : Q \times \sum \rightarrow Q$, mentre $q_0 \in Q$ rappresenta lo stato iniziale, infine $F \subseteq Q$ rappresenta l'insieme degli stati accettati. In generale un automa può essere visto come un grafo la cui rappresentazione grafica prende il nome di diagramma di stato, i nodi invece rappresentano gli stati, lo stato da cui parte l'elaborazione prende il nome di stato iniziale, mentre quello in cui termina l'elaborazione viene definito stato di accettazione. I vari link di collegamento tra i nodi prendono il nome di transazione.

Definendo M come automa finito e $w = w_1w_2w_3\dots w_n$ una stringa dove ogni $w_i$ è un elemento dell'alfabeto $\sum$. L'automa M accetta w se esiste una sequenza di stati $r_0,r_1,\dots , r_n$ in Q che rispetta le seguenti condizioni:

• $r_0 = q_0$
• $\delta (r_i,w_{i+1}) = r_{i+1}$, per i=0,...,n-1
• $r_n \in F$

Ciò significa che la macchina inizia dallo stato iniziale per poi passare da uno stato all'altro in base alla funzione di transizione e infine accetta la stringa in input se l'automa termina la sua elaborazione in uno stato accettante. Affermiamo che l'automa M riconosce il linguaggio A se A = ${ w | M accetta w }$. Inoltre possiamo dare la definizione di linguaggio regolare come quel linguaggio per il quale esiste un automa finito che lo riconosce. Progettare un automa per un linguaggio regolare è un processo non sempre facile, il quale richiede molta logica.

Tra i linguaggi possono essere implementate delle operazioni che prendono il nome di operazioni regolari, le quali sono: l'unione, la concatenazione e la star. Definiti due linguaggi A e B, si definisce l'unione come segue: $A \cup B:$ { $x|x \in A \circ x \in B$ }. L'operazione di concatenazione può essere enunciata come:$A \circ B = { xy | x \in A e y \in B }$, mentre l'operazione di star è indicata come: $A^* = { x_1x_2...x_k | k \geq }$. L'operazione star è un'operazione unaria, a differenza delle altre che sono delle operazioni che sono delle operazioni binarie.

Nella teoria della computazione è presente il concetto di non determinismo, il quale ha un grande impatto. In una macchina non deterministica, in un dato stato possono essere seguite diverse strade. Il non determinismo è una generalizzazione del determinismo, quindi ogni automa finito deterministico può essere visto come un automa finito non deterministico. Possiamo indicare un automa deterministico con l'acronimo di DFA, mentre un automa non deterministico possiamo indicarlo con l'acronimo NFA. La differenza sostanziale tra questi due tipi di automi consiste nel fatto che ogni stato di un DFA ha sempre un arco in entrata e un arco di transizione uscente per ogni simbolo dell'alfabeto, a differenza del NFA nel quale uno stato può avere zero, uno o più archi uscenti per ogni simbolo dell'alfabeto. All'interno di un NFA può essere trovato un arco la cui transizione è etichettata con $\epsilon$.

Un NFA ha un modo differente di computare rispetto a un DFA. Quando viene ricevuta una stringa in input, la macchina si divide in più copie di essa per ogni lettera letta e le esegue tutte in parallelo, questo specialmente quando da uno stato si diramano due o più diramazioni. Quando in una o più copie della macchina, la computazione termina in uno stato finale la stringa viene accettata. Quindi il non determinismo viene visto come una specie di computazione parallela dove più processi multipli indipendenti possono essere visti in maniera indipendente.

Se volessimo dare una definizione formale di automa finito non deterministico, esso può essere visto come una quintupla $NFA = (Q,\sum,\delta, q_0, F)$ nella quale Q rappresenta un insieme finito di stati, $\sum$ è l'alfabeto finito di simboli, $\delta : Q \times \sum_{\epsilon} \rightarrow P(Q)$ rappresenta la funzione di transizione, lo stato iniziale è rappresentato da $q_0 \in Q$, infine l'insieme degli stati di accettazione è rappresentato da $F \subseteq Q$. Si può notare come questa definizione risulti simile a quella del DFA, a eccezione del fatto della funzione di transizione che accetta anche il simbolo $\epsilon$.

Gli automi finiti deterministici e gli automi finiti non deterministici riconoscono la stessa classe di linguaggi. Si può dedurre che due macchine sono equivalenti quando riconoscono lo stesso linguaggio. Enunciamo il teorema di equivalenza tra NFA e DFA: "Per ogni automa finito non deterministico esiste un automa finito deterministico equivalente". Questo teorema si può dimostrare costruendo un NFA $N = (Q,\sum,\delta,q_0,F)$ e un DFA $M = (Q',\sum,\delta ',q_0',F')$, entrambi devono riconoscere il linguaggio A. Consideriamo le seguenti proprietà:

Q' = P(Q)

Ogni stato di M è un insieme di stati di N, dato che P(Q) è l'insieme dei sottoinsiemi di Q.

Per $R \in Q'$ e $a \in \sum$, sia $\delta (R,a) =$ {$q \in Q | q \in \delta (r,a)$ per qualche $r \in R$}.

Se R è uno stato di M, esso è anche un insieme di stati di N. Quando M legge un simbolo a nello stato R, mostra dove a porta ogni stato in R . Poichè da ogni stato si può andare in un insieme di stati, prendiamo l'unione di tutti questi insiemi e può essere rappresentata come: $\delta ' (R,a) = \coprod_{r\in R}\delta(r,a)$

$q_0$' = {$q_0$ }

M inizia nello stato corrispondente alla collezione che contiene solo stato iniziale di N

F'=$R \in$ Q' | R contiene uno stato accettante di N

La macchina M accetta se uno dei possibili stati in cui N potrebbe essere a quel punto è uno stato accettante.

Ora dobbiamo prendere in considerazione gli archi $\epsilon$. Per ogni stato R di M, definiamo E(R) come la collezione di stati che possono essere raggiunti dagli elementi di R proseguendo solo con archi $\epsilon$, includendo gli stessi elementi di R. Formalmente, per $R \subseteq Q$ sia: E(R) = { q | q può essere raggiunto da R attraverso 0 o più archi $\epsilon$ }. Successivamente trasformiamo la funzione di transizione di M, nella quale sostituiamo $\delta$(r,a) con E($\delta$(r,a)). Quindi la funzione di transizione diventa $\delta$'(R,a) ={ q $\in$ Q | q $\in$E($\delta$(r,a)) per qualche r $\in$ R }.

Inoltre bisogna modificare lo stato iniziale di M, cambiando quindi $q_0$ in E({$q_0$}). E con questo ultimo passo abbiamo completato la trasformazione del DFA M che simula l'NFA N.