Indietro

ⓘ Linguaggio ricorsivo




                                     

ⓘ 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:

  • 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 dellinsieme di tutte le possibili stringhe sullalfabeto 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.

                                     

1. Proprietà di chiusura

Linsieme dei linguaggi ricorsivi è chiuso rispetto alle seguenti operazioni:

  • complemento
  • per via di 5 e 6 differenza
  • omomorfismo purché non si utilizzi la stringa vuota ε
  • concatenazione
  • intersezione
  • star di Kleene
  • unione