Lista dei teoremi

Posted by On Filed under Calcolabilità e linguaggi formali
Teorema Codice (Sipser) Pagina (Sipser) Link alla dimostrazione (Italiano)
La classe di linguaggi regolari è chiuso per l'operazione di unione 1.25 45
La classe di linguaggi regolari è chiuso per l'operazione di concatenazione 1.26 47
Ogni automa finito nondeterministico ha un automa finito deterministico corrispondente 1.39 55
(Corollario) Un linguaggio è regolare se e solo se qualche automa finito nondeterministico lo riconosce 1.40 56
La classe dei linguaggi regolari è chiusa per l'operazione di unione 1.45 59
La classe dei linguaggi regolari è chiusa per l'operazione di concatenazione 1.47 60
La classe dei linguaggi regolari è chiusa per l'operazione di star 1.49 62
Un linguaggio è regolare se e solo se qualche espressione regolare lo descrive 1.54 66
(Lemma) Se un linguaggio è regolare, allora è descritto da un'espressione regolare 1.60 69
Pumping lemma: se A è un linguaggio regolare, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in tre pezzi, s = xyz, che soddisfano le seguenti condizioni:

  1. ∀ i ≥ 0, xyiz ∈ A
  2. |y| > 0
  3. |xy| ≤ p
 1.70 78
Ogni linguaggio senza contesto è generato da una grammatica senza contesto in una forma normale di Chomsky 2.9 107
Un linguaggio è senza contesto se qualche automa pushdown lo riconosce 2.20 115
(Lemma) Se un automa pushdown riconosce qualche linguaggio, allora è senza contesto 2.27 119
(Claim) Se Apq genera x, allora x può portare P da p con stack vuoto a q con stack vuoto 2.30 121
(Claim) Se x può portare P da p con stack vuoto a q con stack vuoto, Apq genera x 2.31 121
Pumping lemma per linguaggi senza contesto: se A è un linguaggio senza contesto, allora c'è un numero p (la lunghezza "pump") per cui, se s è una stringa in A di lunghezza come minimo p, allora s può essere divisa in cinque pezzi, s = uvxyz, che soddisfano le seguenti condizioni:

  1. ∀ i ≥ 0, uvixyiz ∈ A
  2. |vy| > 0
  3. |vxy| ≤ p
 2.34 123
Ogni macchina di Turing multinastro ha un'equivalente macchina di Turing a singolo nastro 3.13 149
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina multinastro di Turing lo riconosce 3.15 150
(Corollario) Un linguaggio è Turing-riconoscibile se e solo se qualche macchina di Turing nondeterministica lo riconosce 3.18 152
(Corollario) Un linguaggio è decidibile se e solo se qualche macchina nondeterministica di Turing lo decide 3.19 152
Un linguaggio è Turing-riconoscibile se e solo se qualche enumeratore lo enumera 3.21 153
ADFA è un linguaggio decidibile 4.1 166
ANFA è un linguaggio decidibile 4.2 167
AREX è un linguaggio decidibile 4.3 168
EDFA è un linguaggio decidibile 4.4 168
EQDFA è un linguaggio decidibile 4.5 169
ACFG è un linguaggio decidibile 4.7 170
ECFG è un linguaggio decidibile 4.8 171
Ogni linguaggio senza contesto è decidibile 4.9 172
ATM è indecidibile 4.11 174
R è incontabile 4.17 177
(Corollario) Alcuni linguaggi non sono Turing-riconoscibili 4.18 178
Un linguiaggio è decidibile se e solo se è Turing-riconoscibile e co-Turing-riconoscibile 4.22 181
(Corollario)
ATM non è Turing-riconoscibile		 4.23 182
HALTTM è indecidibile 5.1 188
ETM è indecidibile 5.2 189
REGULARTM è indecidibile 5.3 191
EQTM è indecidibile 5.4 192
(Lemma) Sia M un LBA con q stati e g simboli nell'alfabeto del nastro. Ci sono esattamente qngn distinte configurazioni di M per un nastro di lunghezza n 5.8 194
ALBA è decidibile 5.9 194