计算理论导引3

计算理论导引与算法复杂性IntroductiontotheTheoryofComputationandAlgorithmComplexities 主讲 刘国华 学院楼 225室 ghliu 助教 辛婷婷 学院楼 153室 xtt moon FTP 222 204 215 3 6BOOLEANLOGIC1 Negation 0 1 1 02 Conjunction0 1 0 1 1 13 Disjunction0 1 14 Exclusiveor0 0 0 0 1 15 Equality0 0 1 1 0 06 Implication1 0 0 1 1 1 0 1 1 0 0 17 DistributivelawP Q R P Q P R P Q R P Q P R CHAPTER1FUNDATION I msorry CHAPTER2COMPUTATIONALMODELS 1 Computation Computationisageneraltermforanytypeofprocess algorithmormeasurement thisoftenincludesbutisnotlimitedtodigitaldata Computationisaprocessfollowingawell definedmodel Computationisalsoamajorsubjectmatterofcomputerscience itinvestigateswhatcanorcannotbedoneinacomputationalmanner CHAPTER2COMPUTATIONALMODELS 1 AUTOMATATURINGMACHINES CHAPTER2COMPUTATIONALMODELS 1 AUTOMATA1FINITEAUTOMATA1 DETERMINISTICFINITEAUTOMATA DFA Example Anautomaticdoor Rulesforopening 1Thedoorisclosing ifsomeoneisstandingonthefrontpad FRONT andnooneisstandingontherearpad REAR thenthedooropens 2Thedoorisopening ifsomeoneisstandingontherearpad REAR thenthedoorkeepsopening 3Thedoorisopening ifsomeoneisstandingonthefrontpadandsomeoneisstandingontherearpad BOTH thenthedoorkeepsopening CHAPTER2COMPUTATIONALMODELS 1 Rulesforclosing 1Thedoorisopening ifnooneisstandingoneitherpad NEITHER thenthedoorcloses 2Thedoorisclosing ifsomeoneisstandingontherearpad REAR thenthedoorkeepsclosing 3Thedoorisclosing ifsomeoneisstandingonthefrontpadandsomeoneisstandingontherearpad BOTH thenthedoorkeepsclosing Howtoimplementthissystem Hardwares twosensors onecomputer only1bitmemory etc Howaboutthesoftware CHAPTER2COMPUTATIONALMODELS 1 satrt t TRUE d 0 t TRUE Y s1 sensor1 s2 sensor2 d 0and s2 1ors1 1ands2 1ors1 0ands2 0 Y d 1and s1 1ors2 1ors1 1ands2 1 N Y d 0ands1 1 N Y d 1 d 1ands1 0ands2 0 Y d 0 N end N N CHAPTER2COMPUTATIONALMODELS 1 CLOSED d 0 OPEN d 1 NEITHER s1 0ands2 0 FORNT s1 1 REAR s2 1 BOTH s1 1ands2 1 NEITHER s1 0ands2 0 FORNT s1 1 REAR s2 1 BOTH s1 1ands2 1 CHAPTER2COMPUTATIONALMODELS 1 CLOSED OPEN NEITHER FORNT REARBOTHNEITHER FORNTREARBOTH CHAPTER2COMPUTATIONALMODELS 1 frontpad rearpad CLOSED OPEN BOTH NEITHER FORNT BOTH REAR CHAPTER2COMPUTATIONALMODELS 1 CLOSED OPEN NEITHER FORNTREARBOTH NEITHER FORNTREARBOTH CHAPTER2COMPUTATIONALMODELS 1 ThestatediagramforDFAM1 1 1 1 01 001 00001 0 1 011 0 01 1 0 01 10 FORMALDEFINITIONOFAFINITEATUOMATONAfiniteautomatonisa5 tuple Q q0 F where1 Qisafinitesetcalledthestates 2 isafinitesetcalledthealphabet 3 Q Qisthetransitionfunction 4 q0 Qisthestartstate and5 F Qisthesetofacceptstates CHAPTER2COMPUTATIONALMODELS 1 ThestatediagramforDFAM1 1 Q q1 q2 q3 2 0 1 3 isdesribedas01q1q1q2q2q3q2q3q2q24 q1isthestartstate and5 F q2 CHAPTER2COMPUTATIONALMODELS 1 L M A LanguageofmachineM wesaythatMrecoginizesA FORMALDEFINITIONOFCOMPUTATIONLetM Q q0 F beafiniteautomatonandletw w1w2 wnbeastringwhereeachwiisamemberofthealphabet ThenMacceptswifasequenceofstatesr0 r1 rninQexistswiththreeconditions 1 r0 q0 2 r0 wi 1 ri 1 fori 0 n 1 and3 rn F Regularlanguage alanguageiscalledaregularlanguageifsomefiniteautomatonrecognizes CHAPTER2COMPUTATIONALMODELS 1 DESIGNINGFINITEAUTOMATA qeven qodd 0 0 1 1 HowtodesignaDFAtorecognizethelanguageofallstringsthatcontainthestring001asasubstring q1 1 q2 q3 0 1 0 1 0 q4 1 0 CHAPTER2COMPUTATIONALMODELS 1 THEREGULAROPERATIONUnion A B x x Aorx B Concatenation A B xy x Aandy B Star A x1x2 xk k 0andeachxi A EXAMPLE A good bad B boy girl A B A B A A B good bad boy girl A B goodboy goodgirl badboy badgirl A good bad goodgood goodbad badbad badgood goodgoodgood goodgoodbad goodbadgood goodbadbad CHAPTER2COMPUTATIONALMODELS 1 THEOREM2 1Theclassofregularlanguagesisclosedundertheunionoperation PROOFIDEA A1 L M1 A2 L M2 A1 A2 L M3 LetM1 Q1 1 q1 F1 M2 Q2 2 q2 F2 thenM3 Q3 3 q3 F3 whereQ3 r1 r2 r1 Q1andr2 Q2 3 r1 r2 a 1 r1 a 2 r2 a q3 q1 q2 F r1 r2