Mis on peamine erinevus deterministlike ja mittedeterministlike lõplike olekumasinate vahel?
Deterministlik lõpliku oleku masin (DFSM) ja mittedeterministlik lõpliku oleku masin (NFSM) on kahte tüüpi lõpliku oleku masinaid (FSM), mida kasutatakse arvutusliku keerukuse teoorias. Kuigi mõlemal FSM-il on sarnased omadused ja neid saab kasutada erinevate arvutusprotsesside modelleerimiseks, erinevad nad oma käitumise ja üleminekute olemuse poolest.
Peamine erinevus DFSM-i ja NFSM-i vahel seisneb selles, kuidas nad käitlevad olekutevahelisi üleminekuid. DFSM-is määrab ülemineku ühest olekust teise üheselt praegune olek ja sisendsümbol. See tähendab, et antud oleku ja sisendsümboli puhul saab olla ainult üks võimalik järgmine olek. Teisisõnu, DFSM töötab deterministlikul viisil, kus järgmise oleku määrab üheselt praegune olek ja sisend.
Teisest küljest võimaldab NFSM antud oleku ja sisendsümboli jaoks mitut võimalikku järgmist olekut. See tähendab, et NFSM-i üleminekufunktsioonil võib järgmise oleku jaoks olla mitu kehtivat valikut. Teisisõnu, NFSM töötab mittedeterministlikul viisil, kus järgmine olek ei ole praeguse oleku ja sisendiga üheselt määratud. Selle asemel võib NFSM lülituda üheaegselt ühte või mitmesse olekusse, luues mitu võimalikku arvutusviisi.
Selle erinevuse illustreerimiseks vaatleme näidet. Oletame, et meil on NFSM ja DFSM, mis mõlemad modelleerivad lihtsat keelt, mis aktsepteerib 0-de ja 1-de stringe, mis lõppevad 1-ga. NFSM-il on kaks olekut: S0 ja S1. DFSM-il on ka kaks olekut: Q0 ja Q1.
NFSM-i puhul võib oleku S0 ja sisendsümboli 0 üleminekufunktsioonil olla kaks võimalikku järgmist olekut: S0 ja S1. See tähendab, et kui NFSM on olekus S0 ja võtab vastu sisendsümboli 0, võib see minna üle kas olekusse S0 või olekusse S1. Teisest küljest on oleku S0 ja sisendsümboli 1 üleminekufunktsioonil ainult üks võimalik järgmine olek: S1. See tähendab, et kui NFSM on olekus S0 ja võtab vastu sisendsümboli 1, läheb see alati üle olekusse S1.
Seevastu DFSM-il on iga praeguse oleku ja sisendsümboli kombinatsiooni jaoks kordumatu järgmine olek. Näiteks kui DFSM on olekus Q0 ja võtab vastu sisendsümboli 0, läheb see alati üle olekusse Q0. Samamoodi, kui DFSM on olekus Q0 ja võtab vastu sisendsümboli 1, läheb see alati üle olekusse Q1.
Peamine erinevus deterministlike ja mittedeterministlike lõplike olekumasinate vahel seisneb nende üleminekute olemuses. Deterministlikul lõpliku oleku masinal (DFSM) on iga praeguse oleku ja sisendsümboli kombinatsiooni jaoks kordumatu järgmine olek, samas kui mittedeterministlik lõpliku oleku masin (NFSM) võimaldab praeguse oleku ja sisendsümboli antud kombinatsiooni jaoks mitut võimalikku järgmist olekut.
Muud hiljutised küsimused ja vastused selle kohta EITC/IS/CCTF arvutusliku keerukuse teooria alused:
- Palun kirjeldage vastuses näidet, kus on FSM-i tuvastav binaarne string isegi 1 sümboliga." …sisendstring "1011", FSM ei jõua lõppolekusse ja jääb pärast kolme esimese sümboli töötlemist S0-sse kinni."
- Kuidas mõjutab mittedeterminism üleminekufunktsiooni?
- Kas tavakeeled on samaväärsed lõplike olekumasinatega?
- Kas klass PSPACE ei ole võrdne klassiga EXPSPACE?
- Kas algoritmiliselt arvutatav probleem on Church-Turingi teesi kohaselt Turingi masinaga arvutatav probleem?
- Mis on konkatenatsiooni all olevate tavakeelte sulgemisomadus? Kuidas kombineeritakse lõplikke olekumasinaid, et esindada kahe masina poolt tunnustatud keelte ühendust?
- Kas iga suvalist probleemi saab väljendada keelena?
- Kas P keerukusklass on PSPACE klassi alamhulk?
- Kas igal mitme lindiga Turingi masinal on samaväärne ühelindiga Turingi masin?
- Millised on predikaatide väljundid?
Vaadake rohkem küsimusi ja vastuseid EITC/IS/CCTF-i arvutusliku keerukuse teooria põhialustest