Linguaggio regolare
# Linguaggio regolare

In informatica teorica un linguaggio regolare è un linguaggio formale, ossia costituito da un insieme di stringhe costruite con un alfabeto finito, che è descritto da un'espressione regolare, generato da una grammatica generativa regolare (o di tipo 3, secondo la gerarchia di Chomsky) o accettato da un automa a stati finiti (automa a stati finiti deterministico o automa a stati finiti non deterministico).

## Linguaggi regolari basati su un alfabeto

L'insieme dei linguaggi regolari basati su un alfabeto $\Sigma$ è definito ricorsivamente come segue:

* il linguaggio vuoto $\emptyset$ è un linguaggio regolare.
* il linguaggio $\left\{\epsilon \right\}$ contenente la sola stringa vuota è un linguaggio regolare.
* per ogni carattere $a\in \Sigma$, il linguaggio singleton $\left\{a\right\}$ è un linguaggio regolare.
* se $A$ e $B$ sono linguaggi regolari allora $A\cup B$, $A\circ B$, e $A^{*}$ sono linguaggi regolari.
* nessun altro linguaggio su $\Sigma$ è regolare.

Tutti i linguaggi finiti sono regolari. Un altro tipico esempio include il linguaggio che consiste di tutte le stringhe dell'alfabeto $\left\{a,b\right\}$ e che contiene un numero pari di a, o il linguaggio consistente di tutte le stringhe nella forma: zero o più a seguite da zero o più b.

## Proprietà di chiusura

I linguaggi regolari sono chiusi rispetto alle seguenti operazioni:

* ${\bar {L}}$ complemento
* $L^{*}$ stella di kleene
* $L_{1}\circ L_{2}$ concatenazione
* $L_{1}\cup L_{2}$ unione
* $L_{1}\cap L_{2}$ intersezione
* $L_{1}\smallsetminus L_{2}$ differenza
* $L_{1}^{R}$ riflesso

## Problemi legati ai linguaggi regolari

Nella gerarchia di Chomsky i linguaggi regolari corrispondono ai linguaggi generati da grammatiche di tipo 3. È possibile stabilire se un linguaggio è regolare o meno utilizzando il teorema di Myhill-Nerode. È invece possibile dimostrare che un linguaggio non è regolare utilizzando il pumping lemma per i linguaggi regolari.

Dati due linguaggi regolari $L_{1}$ ed $L_{2}$ è possibile verificare l'inclusione $L_{1}\subseteq L_{2}$ utilizzando le proprietà di chiusura. Per questo motivo è possibile stabilire se due linguaggi regolari sono equivalenti.

## Approccio algebrico

Ci sono due approcci algebrici puri per definire i linguaggi regolari. Se $\Sigma$ è un alfabeto finito e $\Sigma ^{*}$ denota il monoide libero su $\Sigma$ consistente di tutte le stringhe su $\Sigma$, $f:\Sigma ^{*}\rightarrow M$ è un omomorfismo di monoide dove $M$ è un monoide finito, e $S$ è un sottoinsieme di $M$, dove la funzione inversa $f^{-1}(S)$ è regolare. Ogni linguaggio regolare si presenta in questa forma.

Se $L$ è un sottoinsieme di $\Sigma ^{*}$, si può definire una relazione di equivalenza $\sim$ in $\Sigma ^{*}$ come segue: $u\sim v$ è definita

    $uw\in L\iff vw\in L{\mbox{ per ogni }}w\in \Sigma ^{*}$

Il linguaggio $L$ è regolare se e solo se il numero di classi equivalenti di $\sim$ è finito; in questo caso, questo numero è uguale al numero degli stati del minimo automa a stati finiti deterministico che accetti $L$.

