Linguaggio regolare

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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

  • il linguaggio vuoto \empty è un linguaggio regolare.
  • il linguaggio \left \{ \epsilon \right \} contenente la sola stringa vuota è 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Gerarchia-di-Chomsky.jpg

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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 sottostante.
Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica