Jazyk LPřijmeSámSebe1/2
39/45
Myšlenka: LPřijmeSámSebe je
jazyk nad abecedou {0, 1}, který obsahuje
řetězec d(M), právě
tehdy když DTS M přijímá d(M).
Definice:
LPřijmeSámSebe = {d(M): M je DTS, d(M) Î L(M)}
Illustrace:
TS M
Zakódování TS M:
d(M) = 1110…1
• Přijímá
TS M řetězec d(M) = 1110…1
?
D
1
…
TS M
1
1
0
…
1
…
d(M)
d(M) Î LPřijmeSámSebe
d(M) Ï LPřijmeSámSebe
ANO
NE