《情报科学部Decidability.ppt》由会员分享，可在线阅读，更多相关《情报科学部Decidability.ppt（20页珍藏版）》请在三一办公上搜索。
1、Decidability,http:/cis.k.hosei.ac.jp/yukita/,2,Acceptance Problems,3,Theorem 4.1 ADFA is a decidable language.,4,Theorem 4.2 ANFA is a decidable language.,5,Theorem 4.3 AREX is a decidable language.,6,Other Problems,7,Theorem 4.4 EDFA is a decidable language.,8,Theorem 4.5 EQDFA is a decidable langu
2、age.,9,Theorem 4.6 ACFG is a decidable language.,10,Problem 2.19,11,Recognizer and DeciderFirst sight difference in Th.4.6,Enumerate all possible derivations and check one by one if it coincides with the string.The number of tests may be infinite.In this case we obtain a recognizer.The recognizer ma
3、y loop.If we know the number of tests is finite,we have a decider.The decider never loops.,12,Theorem 4.7 ECFG is a decidable language.,13,Theorem 4.8 Every context-free language is decidable.,14,Preparation to Theorem 4.9 ATM is Turing-recognizable.,15,Q is countable.Diagonalization.,1/1,1/2,1/3,1/
4、4,1/5,2/1,2/2,2/3,2/4,2/5,3/1,3/2,3/3,3/4,3/5,4/1,4/2,4/3,4/4,4/5,5/1,5/2,5/3,5/4,5/5,16,Theorem 4.14 R is uncountable.,17,Corollary 4.15 Some languages are not Turing-recognizable.,18,Theorem 4.9 ATM is undecidable.,19,Theorem 4.16 A language is decidable if and only if it is both Turing-recognizable and co-Turing-recognizable.,20,Corollary 4.17,
