Jazyk LNepřijmeSámSebe 1/3
41/45
Myšlenka:  LNepřijmeSámSebe = LPřijmeSámSebe
Definice:
LNepřijmeSámSebe = {0, 1}* – LPřijmeSámSebe
TS M
• 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
Zakódování TS M:
d(M) = 1110…1