Linguaggio regolare
Da Wikipedia, l'enciclopedia libera.
Un linguaggio lineare (o linguaggio regolare) è un linguaggio formale (ad esempio un probabile insieme infinito di sequenze finite di simboli da un alfabeto finito) che soddisfa le seguenti proprietà equivalenti:
- può essere accettato da un'automa a stati finiti deterministico
- può essere accettato da un'automa a stati finiti non deterministico
- può essere accettato da un'automa finito alternante
- può essere descritto da un'espressione regolare
- può essere generato da una grammatica regolare
- può essere generato da una grammatica prefissa
- può essere accettato da una macchina di Turing a sola lettura
- può essere definito nella logica di secondo ordine monadico
Indice |
[modifica] Linguaggi lineari basati su un alfabeto
L'insieme dei linguaggi lineari basati su un alfabeto Σ è definito ricorsivamente come segue:
- il linguaggio vuoto Ø è un linguaggio lineare.
- la stringa vuota { ε } è un linguaggio lineare.
- per ogni a ∈ Σ, il linguaggio Singleton { a } è un linguaggio lineare.
- se A e B sono linguaggi lineari allora 'A U B, A • B, e A* sono linguaggi lineari.
- nessun altro linguaggio su Σ è lineare.
Tutti i linguaggi finiti sono lineari. Un altro tipico esempio include il linguaggio che consiste di tutte le stringhe dell'alfabeto {a, b} e che contiene un numero pari di a, o il linguaggio consistente di tutte le stringhe nella forma: alcune a seguite da alcune b.
[modifica] Proprietà di chiusura
I risultati operazioni di unione, intersezione e differenza quando applicati a linguaggi lineari sono essi stessi dei linguaggi lineari; il complemento di ogni linguaggio lineare basato sul proprio alfabeto è lo stesso un linguaggio lineare. Invertire ogni stringa in un linguaggio lineare produce un altro linguaggio lineare. Il concatenamento di due linguaggi lineari (nel senso di concatenare ogni stringa del primo linguaggio con ogni stringa del secondo) produce a sua volta un linguaggio lineare. L'operazione di mischiare, quando applicata a due linguaggi lineari, produce un altro linguaggio lineare. Il quoziente destro e il quoziente sinistro di un linguaggio lineare con un arbitrario linguaggio è lineare.
[modifica] Decidere quando un linguaggio è lineare
Per collocare un linguaggio lineare nella gerarchia di Chomsky, si sa che ogni linguaggio lineare è context-free. L'opposto non è vero: per esempio il linguaggio che consiste di tutte le stringhe aventi lo stesso numero di a e b è context free ma non regolare. Per dimostrare che un linguaggio come il precedente non è lineare, si può usare il teorema di Myhill-Nerode o il pumping lemma.
Ci sono due approcci algebrici puri per definire i linguaggi lineari. Se Σ è un alfabeto finito e Σ* denota il monoide libero su Σ consistente di tutte le stringhe su Σ f : Σ* → M è un omomorfismo di monoide dove M è un monoide finito, e S è un sottoinsieme di M, dove l'insieme f −1(S) è regolare. Ogni linguaggio lineare si presenta in questa forma.
Se L è un sottoinsieme di Σ*, si può definire una relazione equivalente ~ in Σ* come segue: u ~ v è definita nel senso :uw ∈ L se e solo se vw ∈ L per tutti i w ∈ Σ* Il linguaggio L è lineare se e solo se il numero di classi equivalenti di ~ è finito; in questo caso, questo numero è uguale al numero degli stati del minimo automa deterministico finito che accetti L.
[modifica] Fonti esterne
- Dipartimento di informatica University of Western Ontario: Grail+, http://www.csd.uwo.ca/Research/grail/. Un programma per manipolare le espressioni regolari, le macchine a stati finiti e i linguaggi finiti. Libero per usi non commerciali
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Libero dal contesto | Libero dal contesto | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
