Linguaggio ricorsivo

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:

  1. 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.
  2. 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, liberi dal contesto e dipendenti dal contesto. È degno di nota il fatto che questa categoria non abbia un corrispondente diretto nella classificazione di Chomsky.

Proprietà di chiusura

L'insieme dei linguaggi ricorsivi è chiuso rispetto alle seguenti operazioni:

  1. star di Kleene
  2. omomorfismo (purché non si utilizzi la stringa vuota ε)
  3. concatenazione
  4. unione
  5. intersezione
  6. complemento
  7. (per via di 5 e 6) differenza

Voci correlate

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 sovrastante.