Linguaggio regolare

Un linguaggio $L\subseteq \Sigma^*$ è regolare se esiste un DFA $A=\lang Q, \Sigma, \delta, q_0, F\rang$ (sullo stesso alfabeto $\Sigma$ su cui è definito $L$) tale che $L(A)=L$.

I linguaggi regolari hanno un ruolo importantissimo in informatica, e in particolare sono alla base di molti strumenti pratici.

Definizioni alternative

Ci sono molto altri modi, tutti equivalenti, di definire i linguaggi regolari:

• altri dispositivi, oltre ai DFA, riconoscono i linguaggi regolari (ad esempio, NFA e $\epsilon$-NFA);
• esistono formalismi che permettono di definire i linguaggi regolari mediante un processo di generazione, invece che di riconoscimento, delle stringhe di un linguaggio (ad esempio, le espressioni regolari e le grammatiche di tipo 3)

Esempi

Introduzione agli NFA

Si consideri il seguente diagramma di transizione:

Esso non rispetta la definizione di DFA, perchè:

• lo stato $q_0$ ha due transizioni uscenti etichettate 1, quindi non si può individuare un singolo valore da assegnare alla funzione $\delta (q_0, 1)$;
• lo stato $q_1$ non ha nessuna transizione uscente etichettata 1, ovvero nessun valore da assegnare a $\delta (q_1, 1);$
• non ci sono transizioni uscenti da $q_3$ (quindi, ancora, non si riescono a determinare i valori della funzione di transizione).

Si supponga di voler ammettere questo tipo di dispositivo. Come si può dare a esso un senso, interpretando le situazioni “problematiche” appena descritte? La soluzione è sviluppare non una singola computazione, ma tutte le possibili computazioni dell’automa, stabilendo che:

• Quando uno stato ha più transizioni uscenti etichettate con lo stesso simbolo, ciò significa che ci sono più modi di proseguire la computazione. Ad esempio, se nello stato $q_0$ il simbolo di input è 1, la computazione può proseguire applicando la mossa $q_0 \xrightarrow{1} q_0$ oppure la mossa $q_0 \xrightarrow 1 q_1$.
• Quando invece uno stato non ha una transizione uscente etichettata con un deterinato simbolo, se si ha tale simbolo in input la computazione risulta “bloccata” (non ha modo di procedere). Ad esempio, la computazione è bloccata se nello stato $q_1$ si ha il simbolo di input 1.

Sviluppare tutte le possibili computazioni dell’automa significa non ottenere più una sequenza lineare di mosse, ma piuttosto un albero di computazione. Ad esempio, le possibili computazioni sulla stringa $w=11101$ sono rappresentate dall’albero.