Beskryf die proses om 'n ekwivalente deterministiese FSM te konstrueer gegewe 'n nie-deterministiese FSM.
Die proses om 'n ekwivalente deterministiese eindige toestand masjien (FSM) uit 'n nie-deterministiese FSM te konstrueer behels verskeie stappe wat daarop gemik is om die nie-deterministiese gedrag in 'n deterministiese een te transformeer. Hierdie transformasie is van kardinale belang in die veld van rekenaarkompleksiteitsteorie aangesien dit die ontleding en vergelyking van verskillende FSM'e moontlik maak op grond van hul rekenkrag en kompleksiteit.
Om mee te begin, laat ons 'n nie-deterministiese FSM definieer. 'n Nie-deterministiese FSM is 'n wiskundige model wat bestaan uit 'n stel toestande, 'n stel insetsimbole, 'n oorgangsfunksie, 'n begintoestand en 'n stel aanvaardende toestande. Die oorgangsfunksie karteer 'n toestand en 'n invoersimbool na 'n stel moontlike volgende toestande. Boonop kan die nie-deterministiese FSM veelvuldige oorgange vir dieselfde invoersimbool vanaf dieselfde toestand hê, wat lei tot verskillende stelle moontlike volgende toestande.
Die konstruksie van 'n ekwivalente deterministiese FSM vanaf 'n nie-deterministiese FSM kan bereik word deur die volgende stappe:
Stap 1: Bepaal die stel toestande vir die deterministiese FSM. Elke toestand in die deterministiese FSM stem ooreen met 'n stel toestande in die nie-deterministiese FSM. Die drywingstelkonstruksie word gebruik om alle moontlike kombinasies van toestande in die nie-deterministiese FSM te genereer. Elke kombinasie verteenwoordig 'n toestand in die deterministiese FSM.
Stap 2: Identifiseer die aanvanklike toestand van die deterministiese FSM. Die aanvanklike toestand van die deterministiese FSM is die stel toestande in die nie-deterministiese FSM wat die aanvanklike toestand van die nie-deterministiese FSM bevat.
Stap 3: Definieer die oorgangsfunksie van die deterministiese FSM. Vir elke toestand in die deterministiese FSM en elke invoersimbool, bepaal die stel toestande in die nie-deterministiese FSM wat bereik kan word vanaf enige toestand in die huidige stel toestande deur die gegewe invoersimbool te gebruik. Hierdie stel toestande word die volgende toestand in die deterministiese FSM.
Stap 4: Bepaal die stel aanvaardende toestande vir die deterministiese FSM. 'n Toestand in die deterministiese FSM word as aanvaarbaar beskou as dit ten minste een aanvaardende toestand van die nie-deterministiese FSM bevat.
Deur hierdie stappe te volg, kan ons 'n ekwivalente deterministiese FSM uit 'n nie-deterministiese FSM konstrueer. Die gevolglike deterministiese FSM sal 'n enkele oorgang vir elke invoersimbool van elke toestand hê, wat die nie-deterministiese gedrag van die oorspronklike FSM uitskakel. Dit maak voorsiening vir 'n meer sistematiese ontleding en vergelyking van FSM'e gebaseer op hul berekeningskompleksiteit en krag.
Om hierdie proses te illustreer, kom ons kyk na 'n voorbeeld. Gestel ons het 'n nie-deterministiese FSM met drie toestande (A, B, C), twee invoersimbole (0, 1) en die volgende oorgange:
– A, 0 -> {A, B}
– A, 1 -> {A}
– B, 0 -> {C}
– B, 1 -> {B}
– C, 0 -> {C}
– C, 1 -> {A}
Stap 1: Die drywingstelkonstruksie genereer die volgende toestande vir die deterministiese FSM: {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B , C}.
Stap 2: Die aanvanklike toestand van die deterministiese FSM is {A}.
Stap 3: Die oorgangsfunksie van die deterministiese FSM is soos volg:
– {A}, 0 -> {A, B}
– {A}, 1 -> {A}
– {B}, 0 -> {C}
– {B}, 1 -> {B}
– {C}, 0 -> {C}
– {C}, 1 -> {A}
– {A, B}, 0 -> {A, B, C}
– {A, B}, 1 -> {A, B}
– {A, C}, 0 -> {A, C}
– {A, C}, 1 -> {A}
– {B, C}, 0 -> {C}
– {B, C}, 1 -> {B}
– {A, B, C}, 0 -> {A, B, C}
– {A, B, C}, 1 -> {A, B}
Stap 4: Die aanvaardende toestande van die deterministiese FSM is {A, B, C}.
Die gevolglike deterministiese FSM is nou volledig gedefinieer en kan ontleed en vergelyk word met ander FSM'e deur gebruik te maak van berekeningskompleksiteitsteorie.
Die konstruksie van 'n ekwivalente deterministiese FSM uit 'n nie-deterministiese FSM behels die bepaling van die stel toestande, die identifisering van die aanvanklike toestand, die definisie van die oorgangsfunksie en die bepaling van die stel aanvaardende toestande. Hierdie transformasie maak voorsiening vir die ontleding en vergelyking van FSM'e gebaseer op hul rekenkrag en kompleksiteit.
Ander onlangse vrae en antwoorde t.o.v EITC/IS/CCTF Computational Complexity Theory Fundamentals:
- Is daar 'n teenstrydigheid tussen die definisie van NP as 'n klas besluiteprobleme met polinoom-tyd-verifieerders en die feit dat probleme in die klas P ook polinoom-tyd-verifieerders het?
- Is verifieerder vir klas P polinoom?
- Kan 'n Nondeterministic Finite Automaton (NFA) gebruik word om die toestandsoorgange en aksies in 'n firewall-konfigurasie voor te stel?
- Is die gebruik van drie bande in 'n multiband TN gelykstaande aan enkelbandtyd t2(vierkant) of t3(kubus)? Met ander woorde is die tydskompleksiteit direk verwant aan die aantal bande?
- As die waarde in die vastepuntdefinisie die limiet van die herhaalde toepassing van die funksie is, kan ons dit steeds 'n vaste punt noem? In die voorbeeld wat gewys word as ons in plaas van 4->4 4->3.9, 3.9->3.99, 3.99->3.999 het, … is 4 steeds die vaste punt?
- As ons twee TM'e het wat 'n beslisbare taal beskryf, is die ekwivalensievraag nog onbeslisbaar?
- In die geval van die opsporing van die begin van die band, kan ons begin deur 'n nuwe band T1=$T te gebruik in plaas daarvan om na regs te skuif?
- Hoe groot is die stapel van 'n PDA en wat bepaal die grootte en diepte daarvan?
- Is daar huidige metodes om Tipe-0 te herken? Verwag ons dat kwantumrekenaars dit haalbaar sal maak?
- Hoekom is LR(k) en LL(k) nie ekwivalent nie?
Sien meer vrae en antwoorde in EITC/IS/CCTF Computational Complexity Theory Fundamentals