Linguaggio ricorsivo
Da Wikipedia, l'enciclopedia libera.
In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili. Esistono due definizioni principali equivalenti per questa classe:
- Un linguaggio ricorsivo è un linguaggio per il quale esiste una macchina di Turing che, data una qualsiasi stringa di input, termina accettando la stringa se essa appartiene al linguaggio, e termina rifiutando la stringa in caso contrario.
- Un linguaggio ricorsivo è un sottoinsieme ricorsivo dell'insieme di tutte le possibili stringhe sull'alfabeto del linguaggio.
Tutti i linguaggi ricorsivi sono ricorsivamente enumerabili. Sono ricorsivi tutti i linguaggi regolari, context-free e context-sensitive. È degno di nota il fatto che questa categoria non abbia un corrispondente diretto nella classificazione di Chomsky.
[modifica] Proprietà di chiusura
L'insieme dei linguaggi ricorsivi è chiuso rispetto alle seguenti operazioni:
- star di Kleene
- omomorfismo
- concatenazione
- unione
- intersezione
- complemento
- (per via di 5 e 6) differenza
[modifica] Voci correlate
- Problema decidibile
- Grammatica context-sensitive
- Linguaggio ricorsivamente enumerabile
| 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 | Context-free | Context-free | 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. | |||
