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 (deterministico o non deterministico).
Linguaggi regolari basati su un alfabeto L'insieme dei linguaggi regolari basati su un alfabeto è definito ricorsivamente come segue: il linguaggio vuoto è un linguaggio regolare. il linguaggio contenente la sola stringa vuota è un linguaggio regolare. per ogni carattere , il linguaggio singleton è un linguaggio regolare. se e sono linguaggi regolari allora , , e sono linguaggi regolari. nessun altro linguaggio su è regolare.
Tutti i linguaggi finiti sono regolari. Un altro tipico esempio include il linguaggio che consiste di tutte le stringhe dell'alfabeto 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: complemento stella di kleene concatenazione unione intersezione differenza 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 ed è possibile verificare l'inclusione 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 è un alfabeto finito e denota il monoide libero su consistente di tutte le stringhe su , è un omomorfismo di monoide dove è un monoide finito, e è un sottoinsieme di , dove la funzione inversa è regolare. Ogni linguaggio regolare si presenta in questa forma.
Se è un sottoinsieme di , si può definire una relazione di equivalenza in come segue: è definita
Il linguaggio è regolare se e solo se il numero di classi equivalenti di è finito; in questo caso, questo numero è uguale al numero degli stati del minimo automa a stati finiti deterministico che accetti .
Bibliografia
Voci correlate Espressione regolare Grammatica regolare Automa a stati finiti Linguaggio ω-regolare
Altri progetti
Collegamenti esterni
Categoria:Teoria dei linguaggi formali