Decidibilità ed enumerabilità Flashcards
(10 cards)
Cos’è un linguaggio formale?
Un linguaggio formale su un alfabeto $Sigma$ è un sottoinsieme delle parole su $Sigma$, ovvero $L subseteq Sigma^*$.
Un linguaggio quando si dice enumerabile?
Un linguaggio L si dice enumerabile quando esiste un algoritmo M che, partendo da un input vuoto, genera in tempo finito ciascuna stringa di L.
Un linguaggio quando si dice decidibile?
Un linguaggio L si dice decidibile quando esiste un algoritmo M che, su un input $w in Sigma^*$, in tempo finito dice se $w in L$ o no.
Una funzione quando si dice computabile?
Una funzione $F:L_1 o L_2$ si dice computabile quando esiste un algoritmo M che, dato $w_1 in L_1$, calcola $w_2 in L_2$ in tempo finito.
L decidibile implica enumerabile
Se L è decidibile, allora L è numerabile.
Dimostrazione: eseguendo l’algoritmo di decisione M su tutte le stringhe $w in Sigma^*$. Diagonalizzazione di Cantor ricorsiva
Cosa implica L enumerabile?
L enumerabile non implica necessariamente che L sia decidibile.
Se anche il complementare è enumerabile allora si
Considerando il complemento $L^c = {w in Sigma^*, w notin L}$.
Qual è la funzione caratteristica di un sottoinsieme?
$Sigma^* to {0,1}$
La funzione caratteristica di un sottoinsieme è una funzione che indica l’appartenenza degli elementi al sottoinsieme.
Cosa implica L decidibile riguardo alla funzione caratteristica?
Se L è decidibile, <-> la funzione caratteristica $chi_L$ è computabile.
Un linguaggio quando si dice semidecidibile?
Un linguaggio $L subseteq Sigma^$ si dice semidecidibile quando esiste un algoritmo M tale che, per ogni $w in Sigma^$, se $w in L$, $M(w)$ termina comunicando l’appartenenza, altrimenti non si sa.
Cosa implica L enumerabile riguardo alla semidecidibilità?
enumerabile <-> semidecidibile
->) M algoritmo di enumerazione, creo semidecisione: preso w enumera fino a trovarlo o loop
<-) metto tutte le stringhe, un carattere alla volta secondo cantor percorro. quando una stringa termina lo aggiunge. in questo modo enumera tutte le stringhe
