Idea intuitiva

Gli NFA con $\epsilon$-mosse, o $\epsilon$-NFA, sono un’estensione del modello degli NFA in cui sono ammesse transizioni sulla stringa vuota $\epsilon$. In altre parole, un automa di questo tipo può effettuare delle mosse (transizioni) spontaneamente, senza consumare alcun simbolo di input, e si usa la stringa vuota $\epsilon$ come simbolo per etichettare le transizioni che possono avvenire spontaneamente.

A scopo illustrativo, si consideri il linguaggio dei numeri decimali in notaizone anglosassone, che sono composti da:

  1. un segno + o - opzionale
  2. una prima sequenza di cifre decimali
  3. un punto
  4. una seconda sequenza di cifre decimali

Una delle due sequenza di cifre può essere vuota, ma non entrambe. Alcune stringhe di questo linguaggio sono:

$$ 3.14\ \ \ +125. \ \ \ -125.0\ \ \ .010\ \ \ +.010 $$

Un $\epsilon$-NFA che riconosce questo linguaggio è il seguente:

Untitled

Per riconoscere, ad esempio, la stringa 3.14, questo automa:

  1. parte, come sempre, dallo stato iniziale $q_0$
  2. arriva in $q_1$ seguendo la transizione etichettata con $\epsilon$, $q_0\xrightarrow \epsilon q_1$, cioè senza consumare alcun simbolo di input
  3. consuma il simbolo tre seguendo il cappio $q_1 \xrightarrow 3 q_1$
  4. consuma ilpunto seguendo la transizione da $q_1$ a $q_2$
  5. passa a $q_3$ consumando il simbolo 1
  6. arriva in $q_3$ sfruttando il cappio $q_3 \xrightarrow 4 q_3$
  7. giunge nello stato finale $q_5$ mediante un’altra $\epsilon$-mossa, cioè senza consumare nulla (tanto è vero che tutti i simboli della stringa in input sono già stati consumati)

In questo percorso di computazione, il ruolo della prima $\epsilon$-mossa è stato quello di esprimere l’”opzionalità” del simbolo + o -.