Pushdown Automata (PDA) - гэта вылічальная мадэль, якая выкарыстоўваецца ў тэарэтычнай інфарматыцы для вывучэння розных аспектаў вылічэнняў. КПК асабліва важныя ў кантэксце тэорыі складанасці вылічэнняў, дзе яны служаць фундаментальным інструментам для разумення вылічальных рэсурсаў, неабходных для вырашэння розных тыпаў задач. У сувязі з гэтым, пытанне аб тым, ці можа КПК вызначыць мову радка паліндрома, паглыбляецца ў магчымасці і абмежаванні гэтай вылічальнай мадэлі.
Каб вырашыць гэтае пытанне, нам спачатку трэба высветліць, што такое паліндромны радок. Паліндром - гэта паслядоўнасць сімвалаў, якая чытаецца аднолькава наперад і назад. Напрыклад, "радар" і "ўзровень" з'яўляюцца прыкладамі паліндромных радкоў. Мова паліндромных радкоў складаецца з усіх магчымых паліндромаў над дадзеным алфавітам. Задача пад рукой - вызначыць, ці можа КПК распазнаць або вызначыць, ці з'яўляецца дадзены ўваходны радок паліндромам.
У кантэксце КПК здольнасць распазнаваць паліндромны радок залежыць ад вылічальнай магутнасці КПК і спецыфічных асаблівасцей паліндромных радкоў. КПК маюць магчымасць маніпуляваць стэкам у дадатак да чытання ўваходных сімвалаў, што дае ім большую вылічальную магутнасць у параўнанні з канечнымі аўтаматамі. Гэтая дадатковая магчымасць дазваляе КПК распазнаваць пэўныя тыпы моў, якія не могуць быць распазнаны толькі канечнымі аўтаматамі.
Калі справа даходзіць да паліндромных радкоў, ключавой уласцівасцю, якую можа выкарыстоўваць КПК, з'яўляецца той факт, што структура паліндрома сіметрычная. Гэтая сіметрыя дазваляе КПК параўноўваць сімвалы ў пачатку і ў канцы ўваходнага радка, выкарыстоўваючы свой стэк для адсочвання сімвалаў паміж імі. Належным чынам выкарыстоўваючы свой стэк для захоўвання і атрымання сімвалаў, КПК можа праверыць, ці з'яўляецца дадзены ўваходны радок паліндромам.
Працэс выяўлення паліндромных радкоў з дапамогай КПК звычайна ўключае ў сябе абыход уваходнага радка з абодвух канцоў адначасова з выкарыстаннем стэка для параўнання сімвалаў. На кожным кроку КПК можа счытваць сімвалы з абодвух канцоў радка ўводу і параўноўваць іх, каб пераканацца, што яны супадаюць. Калі выяўлена неадпаведнасць або калі ўвесь радок апрацаваны, а стэк пусты, КПК можа адхіліць уваходны радок як не паліндром. З іншага боку, калі КПК паспяхова апрацоўвае ўвесь уваходны радок і стэк пусты, уваходны радок прымаецца як паліндром.
КПК сапраўды можа выяўляць мову паліндромных радкоў, выкарыстоўваючы свае магчымасці на аснове стэка для параўнання сімвалаў сіметрычным чынам. Гэты працэс дэманструе вылічальную магутнасць КПК у распазнаванні пэўных тыпаў моў, якія дэманструюць пэўныя структурныя ўласцівасці, такія як паліндромы.
Іншыя апошнія пытанні і адказы адносна Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF:
- Ці заўсёды вырашальная нармальная форма граматыкі Хомскага?
- Ці можна вызначыць рэгулярны выраз з дапамогай рэкурсіі?
- Як прадставіць АБО як FSM?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
- Верыфікатар для класа P паліном?
- Ці можна выкарыстоўваць недэтэрмінаваны канчатковы аўтамат (NFA) для адлюстравання пераходаў станаў і дзеянняў у канфігурацыі брандмаўэра?
- Ці эквівалентна выкарыстанне трох стужак у шматстужачным TN часу t2 (квадрат) або t3 (куб) адной стужкі? Іншымі словамі, ці залежыць часовая складанасць ад колькасці стужак?
- Калі значэнне ў вызначэнні фіксаванай кропкі з'яўляецца мяжой шматразовага прымянення функцыі, ці можам мы назваць яе фіксаванай кропкай? У паказаным прыкладзе, калі замест 4->4 мы маем 4->3.9, 3.9->3.99, 3.99->3.999, … ці застаецца 4 фіксаванай кропкай?
- Калі ў нас ёсць дзве TM, якія апісваюць вырашальную мову, пытанне эквівалентнасці ўсё яшчэ невырашальнае?
- У выпадку выяўлення пачатку стужкі, ці можам мы пачаць з выкарыстання новай стужкі T1=$T замест зруху ўправа?
Больш пытанняў і адказаў глядзіце ў раздзеле "Асновы тэорыі вылічальнай складанасці" EITC/IS/CCTF