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 $\empty$ è un linguaggio regolare.
• la stringa vuota ${ \epsilon }$ è un linguaggio regolare.
• per ogni carattere $a \isin \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^{*} \rarr 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 \isin L \iff vw \isin L \mbox{ per ogni } w \isin \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$.

Bibliografia

• regular language in Academic Press Dictionary of Science and Technology (in inglese), Oxford, Elsevier Science & Technology, 1992.
• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman, Regular expressions and Languages in Introduction to Automata Theory, Languages, and Computation (in inglese), Addison Wesley, 15 luglio 2006. 978-0321462251
• Martin Davis; Ron Sigal; Elaine J. Weyuker, Regular Languages in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (in inglese), Morgan Kaufmann, 17 febbraio 1994. 978-0122063824

Voci correlate

• Espressione regolare
• Grammatica regolare
• Automa a stati finiti

Collegamenti esterni

• Grail+, University of Western Ontario
• JFLAP, Università Duke

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica