Детерминист ба детерминистик бус төгсгөлийн төлөвийн машинуудын гол ялгаа нь юу вэ?
Тооцооллын нарийн төвөгтэй байдлын онолын салбарт ашигладаг тодорхойгүй төгсгөлийн төлөвийн машин (DFSM) ба тодорхойгүй төгсгөлийн төлөвийн машин (NFSM) нь хоёр төрлийн төгсгөлийн төлөвийн машин (FSMs) юм. Хэдийгээр FSM хоёулаа ижил төстэй шинж чанартай бөгөөд янз бүрийн тооцооллын процессыг загварчлахад ашиглаж болох боловч тэдгээр нь зан төлөв, шилжилтийн шинж чанараараа ялгаатай байдаг.
DFSM ба NFSM хоёрын гол ялгаа нь муж улс хоорондын шилжилтийг зохицуулах аргад оршдог. DFSM-д нэг төлөвөөс нөгөөд шилжих шилжилтийг одоогийн төлөв болон оролтын тэмдэгээр онцгойлон тодорхойлдог. Энэ нь өгөгдсөн төлөв болон оролтын тэмдгийн хувьд зөвхөн нэг дараагийн төлөв байж болно гэсэн үг юм. Өөрөөр хэлбэл, DFSM нь детерминистик аргаар ажилладаг бөгөөд дараагийн төлөв нь одоогийн төлөв болон оролтоор тодорхойлогддог.
Нөгөөтэйгүүр, NFSM нь тухайн төлөв болон оролтын тэмдэгтийн дараагийн боломжит олон төлөвийг зөвшөөрдөг. Энэ нь NFSM-ийн шилжилтийн функц нь дараагийн төлөвт олон хүчинтэй сонголттой байж болно гэсэн үг юм. Өөрөөр хэлбэл, NFSM нь тодорхой бус байдлаар ажилладаг бөгөөд дараагийн төлөв нь одоогийн төлөв болон оролтоор тодорхойлогддоггүй. Үүний оронд NFSM нь нэг буюу хэд хэдэн төлөвт нэгэн зэрэг шилжиж, тооцооллын олон боломжит замыг бий болгож чадна.
Энэ ялгааг харуулахын тулд жишээг авч үзье. Бидэнд 0-ээр төгссөн 1 ба 1-ийн мөрүүдийг хүлээн зөвшөөрдөг энгийн хэлийг загварчилсан NFSM болон DFSM байна гэж бодъё. NFSM нь S0 ба S1 гэсэн хоёр төлөвтэй. DFSM нь мөн Q0 ба Q1 гэсэн хоёр төлөвтэй.
NFSM-ийн хувьд S0 төлөв болон оролтын тэмдэг 0-д шилжих функц нь дараагийн хоёр төлөвтэй байж болно: S0 ба S1. Энэ нь NFSM нь S0 төлөвт байх ба 0 оролтын тэмдгийг хүлээн авах үед S0 эсвэл S1 төлөв рүү шилжиж болно гэсэн үг юм. Нөгөө талаас, S0 төлөв болон оролтын тэмдэг 1-д шилжих функц нь зөвхөн нэг боломжтой дараагийн төлөвтэй байна: S1. Энэ нь NFSM нь S0 төлөвт байх ба оролтын тэмдэг 1-ийг хүлээн авах үед энэ нь үргэлж S1 төлөвт шилжинэ гэсэн үг юм.
Үүний эсрэгээр, DFSM нь одоогийн төлөв болон оролтын тэмдгийн хослол бүрийн хувьд өвөрмөц дараагийн төлөвтэй байдаг. Жишээлбэл, DFSM нь Q0 төлөвт байх ба оролтын тэмдэг 0-г хүлээн авах үед энэ нь үргэлж Q0 төлөвт шилжинэ. Үүний нэгэн адил, DFSM нь Q0 төлөвт байх ба оролтын тэмдэг 1-ийг хүлээн авах үед энэ нь үргэлж Q1 төлөвт шилжинэ.
Детерминист ба детерминистик бус төгсгөлийн төлөвийн машинуудын гол ялгаа нь тэдгээрийн шилжилтийн шинж чанарт оршдог. Детерминист төгсгөлийн төлөвийн машин (DFSM) нь одоогийн төлөв ба оролтын тэмдгийн хослол бүрт дараагийн өвөрмөц төлөвтэй байдаг бол тодорхойгүй хязгаарлагдмал төлөвийн машин (NFSM) нь одоогийн төлөв ба оролтын тэмдгийн өгөгдсөн хослолын хувьд дараагийн боломжит олон төлөвийг зөвшөөрдөг.
Сүүлийн үеийн бусад асуулт, хариулт EITC/IS/CCTF Тооцооллын нарийн төвөгтэй байдлын онолын үндэс:
- Детерминистик бус PDA-уудыг авч үзвэл мужуудын суперпозиция нь тодорхойлолтоор боломжтой юм. Гэсэн хэдий ч детерминистик бус PDA нь зөвхөн нэг стектэй байдаг бөгөөд энэ нь нэгэн зэрэг олон төлөвт байж болохгүй. Энэ яаж боломжтой вэ?
- Сүлжээний урсгалд дүн шинжилгээ хийх, аюулгүй байдлын болзошгүй зөрчлийг илтгэх хэв маягийг тодорхойлоход ашигладаг PDA-ийн жишээ юу вэ?
- Нэг хэл нөгөө хэлээсээ илүү хүчтэй гэдэг нь юу гэсэн үг вэ?
- Контекст мэдрэмтгий хэлүүдийг Тьюрингийн машин таних боломжтой юу?
- U = 0^n1^n (n>=0) хэл яагаад тогтмол бус байна вэ?
- Тэгш тооны '1' тэмдэгт бүхий хоёртын мөрийг таних FSM-г хэрхэн тодорхойлж, 1011 оролтын мөрийг боловсруулахад юу болдгийг харуулах вэ?
- Нотертерминизм нь шилжилтийн функцэд хэрхэн нөлөөлдөг вэ?
- Энгийн хэлүүд нь хязгаарлагдмал төрийн машинуудтай тэнцэх үү?
- PSPACE анги нь EXPSPACE ангитай тэнцэхгүй байна уу?
- Алгоритмын хувьд тооцоолж болох асуудал нь Тьюрингийн машинаар тооцоолж болох асуудал мөн үү?