Калі мы маем два ці больш прымальных шляхоў у недэтэрмінаванай машыне, які з іх мы выбіраем і якія крытэры мы можам выкарыстоўваць?
У сферы тэорыі складанасці вылічэнняў, у прыватнасці, пры вывучэнні канечных аўтаматаў, канцэпцыя недэтэрмінізму адыгрывае важную ролю.
Недэтэрмінаваныя канечныя аўтаматы (NFSM) - гэта тэарэтычныя мадэлі, якія дазваляюць выкарыстоўваць некалькі прымальных шляхоў у любым зададзеным стане. Аднак пры сутыкненні з такой сітуацыяй узнікае пытанне: які шлях абраць?
Гэты запыт закранае паняцце "прыняцце" ў NFSM і крытэрыі, якія могуць быць выкарыстаны для прыняцця рашэння.
Каб зразумець працэс адбору, давайце спачатку вывучым прыроду недэтэрмінізму ў NFSM. У адрозненне ад дэтэрмінаваных канечных аўтаматаў (DFSM), NFSM не маюць унікальнага пераходу для кожнага магчымага ўваходнага сімвала ў кожным стане. Замест гэтага яны дазваляюць існаваць некалькі пераходаў для аднаго і таго ж сімвала ўводу. Гэтая характарыстыка прыводзіць да магчымасці ісці некалькімі шляхамі з аднаго стану, што патэнцыйна можа прывесці да розных вынікаў.
Сутыкнуўшыся з такой сітуацыяй, NFSM выкарыстоўваюць механізм, які называецца "разгалінаванне", каб даследаваць усе магчымыя шляхі адначасова. Гэта азначае, што машына стварае некалькі копій сябе, кожная з якіх ідзе па розным шляху. У выніку NFSM можна разглядаць як даследаванне дрэвападобнай структуры, дзе кожная галіна ўяўляе іншы шлях вылічэнняў. Гэты метад разгалінавання з'яўляецца фундаментальным пры аналізе NFSM і іх вылічальнай складанасці.
Зараз давайце разгледзім крытэрыі, якія могуць быць выкарыстаны для выбару пэўнага шляху сярод мноства прымальных. Адным з распаўсюджаных падыходаў з'яўляецца разгляд паняцця "прыняцце" ў NFSM. Прыняцце адносіцца да ўмовы, якая вызначае, ці лічыцца машына дадзены ўвод сапраўдным ці не. У NFSM прыняцце можа быць вызначана двума асноўнымі спосабамі: «прыняцце канчатковым станам» і «прыняцце пустым стэкам».
Прыняцце канчатковым станам адбываецца, калі пасля выкарыстання ўсяго ўваходнага радка NFSM трапляе ў стан, пазначаны як канчатковы. Гэты крытэрый прадугледжвае, што машына прымае ўвод, калі існуе хаця б адзін шлях вылічэнняў, які вядзе да канчатковага стану. І наадварот, калі ніякі шлях не вядзе да канчатковага стану, увод адхіляецца.
Прыняцце пустым стэкам, з іншага боку, актуальна, калі NFSM уключае стэк у якасці дадатковага кампанента. У гэтым выпадку прыняцце адбываецца, калі ўваходны радок цалкам апрацаваны і стэк становіцца пустым. Падобна прыняццю канчатковым станам, калі існуе хаця б адзін шлях вылічэнняў, які прыводзіць да пустога стэка, увод прымаецца; у адваротным выпадку ён адхіляецца.
Улічваючы гэтыя крытэрыі, выбар пэўнага шляху сярод некалькіх прымальных у недэтэрмінаванай машыне можа быць вызначаны шляхам расстаноўкі прыярытэтаў умоў прыняцця. Напрыклад, калі прыняцце канчатковым станам з'яўляецца асноўным крытэрыем, машына абярэ шлях, які вядзе да канчатковага стану, незалежна ад іншых патэнцыйных шляхоў. І наадварот, калі прыняцце пустым стэкам з'яўляецца асноўным крытэрыем, машына аддасць прыярытэт шляху, які прыводзіць да пустога стэка.
Важна адзначыць, што выбар шляху ў NFSM не ўплывае на вылічальную магутнасць машыны. Незалежна ад абранага шляху, NFSM усё яшчэ можа распазнаваць той жа набор моў, што і любы іншы NFSM для дадзенага ўводу. Працэс адбору проста вызначае прыняцце або адхіленне ўводу на аснове вызначаных крытэрыяў.
Пры сутыкненні з некалькімі прымальнымі шляхамі ў недэтэрмінаванай машыне выбар шляху можа быць вызначаны шляхам расстаноўкі прыярытэтаў умоў прыняцця, такіх як прыняцце канчатковым станам або прыняцце пустым стэкам. Працэс адбору не ўплывае на вылічальную магутнасць машыны, але ўплывае на тое, прымаецца ці адхіляецца ўвод.
Іншыя апошнія пытанні і адказы адносна Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF:
- Якая роля рэкурсійнай тэарэмы ў дэманстрацыі невырашальнасці ATM?
- Разглядаючы КПК, які можа чытаць паліндромы, не маглі б вы падрабязна апісаць эвалюцыю стэка, калі ўвод з'яўляецца, па-першае, паліндромам, а па-другое, не паліндромам?
- Разглядаючы недэтэрмінаваныя КПК, суперпазіцыя станаў магчымая па азначэнні. Аднак недэтэрмінаваныя КПК маюць толькі адзін стэк, які не можа знаходзіцца ў некалькіх станах адначасова. Як такое магчыма?
- Што з'яўляецца прыкладам КПК, якія выкарыстоўваюцца для аналізу сеткавага трафіку і ідэнтыфікацыі шаблонаў, якія паказваюць на магчымыя парушэнні бяспекі?
- Што значыць, што адна мова больш магутная за іншую?
- Ці пазнаюцца кантэкстна-залежныя мовы машынай Цьюрынга?
- Чаму мова U = 0^n1^n (n>=0) нерэгулярная?
- Як вызначыць FSM, які распазнае двайковыя радкі з цотнай колькасцю сімвалаў «1», і паказаць, што з ім адбываецца пры апрацоўцы ўваходнага радка 1011?
- Як недэтэрмінізм уплывае на пераходную функцыю?
- Ці эквівалентныя звычайныя мовы канчатковым аўтаматам?
Больш пытанняў і адказаў глядзіце ў раздзеле "Асновы тэорыі вылічальнай складанасці" EITC/IS/CCTF