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 ${\displaystyle \Sigma }$ è definito ricorsivamente come segue:

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

Tutti i linguaggi finiti sono regolari. Un altro tipico esempio include il linguaggio che consiste di tutte le stringhe dell'alfabeto ${\displaystyle \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:

• ${\displaystyle {\bar {L}}}$ complemento
• ${\displaystyle L^{*}}$ stella di kleene
• ${\displaystyle L_{1}\circ L_{2}}$ concatenazione
• ${\displaystyle L_{1}\cup L_{2}}$ unione
• ${\displaystyle L_{1}\cap L_{2}}$ intersezione
• ${\displaystyle L_{1}\smallsetminus L_{2}}$ differenza
• ${\displaystyle 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 ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$ è possibile verificare l'inclusione ${\displaystyle 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 ${\displaystyle \Sigma }$ è un alfabeto finito e ${\displaystyle \Sigma ^{*}}$ denota il monoide libero su ${\displaystyle \Sigma }$ consistente di tutte le stringhe su ${\displaystyle \Sigma }$, ${\displaystyle f:\Sigma ^{*}\rightarrow M}$ è un omomorfismo di monoide dove ${\displaystyle M}$ è un monoide finito, e ${\displaystyle S}$ è un sottoinsieme di ${\displaystyle M}$, dove la funzione inversa ${\displaystyle f^{-1}(S)}$ è regolare. Ogni linguaggio regolare si presenta in questa forma.

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

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

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

Bibliografia

• Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.
• (EN) regular language, in Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.
• (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Regular expressions and Languages, in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
• (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, Regular Languages, in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate

• Espressione regolare
• Grammatica regolare
• Automa a stati finiti
• Linguaggio ω-regolare

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su linguaggio regolare

Collegamenti esterni

• Linguaggio regolare, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Grail+, su grailplus.org, University of Western Ontario (archiviato dall'url originale il 18 ottobre 2016).
• (EN) JFLAP, su jflap.org, Università Duke.

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	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 proprio della categoria immediatamente sovrastante.