Linguaggio regolare

Cos'è un linguaggio regolare

Dato un alfabeto Σ, un linguaggio regolare è un sottoinsieme Σ* ottenuto con operazioni di unione, concatenazione e stella di Kleen sui linguaggi 0, {ε} e {σ}. Dove σ indica ogni simbolo dell'alfabeto Σ.

La classe dei linguaggi naturali coincide con la classe dei linguaggi accettati da un automa a stati finiti deterministico DFA e non deterministico NFA.

I linguaggi naturali possono essere descritti in modo algebrico tramite le espressioni regolari.

Nota. I linguaggi regolari sono un sottoinsieme dei linguaggi ricorsivamente enumerabili. Sono l'intersezione tra i linguaggi liberi dal contesto e i linguaggi di Petri.

E così via.