Ці можам мы вызначыць, ці прымаецца дадзены радок кантэкстна-свабоднай граматыкай? Ці вырашальная гэтая праблема?
Вызначэнне таго, ці прымаецца дадзены радок кантэкстна-свабоднай граматыкай, з'яўляецца фундаментальнай праблемай тэорыі складанасці вылічэнняў. Гэтая праблема падпадае пад больш шырокую катэгорыю вырашальнасці, якая мае справу з вызначэннем таго, ці выконваецца пэўная ўласцівасць для дадзенага ўводу. У выпадку кантэкстна-свабодных граматык праблема прыняцця радкоў сапраўды вырашальная.
Кантэкстна-свабодная граматыка - гэта фармальная сістэма, якая складаецца з набору правіл вытворчасці, якія апісваюць, як ствараць радкі ў мове. Ён вызначаецца картэжам (V, Σ, R, S), дзе V — набор нетэрмінальных сімвалаў, Σ — набор тэрмінальных сімвалаў, R — набор правілаў вытворчасці, а S — пачатковы сімвал. Мова, згенераваная кантэкстна-свабоднай граматыкай, - гэта набор усіх радкоў, якія могуць быць атрыманы з пачатковага сімвала з дапамогай правіл вытворчасці.
Каб вызначыць, ці прымаецца дадзены радок кантэкстна-свабоднай граматыкай, мы можам выкарыстоўваць розныя алгарытмы, такія як алгарытм CYK або алгарытм Эрлі. Гэтыя алгарытмы выкарыстоўваюць метады дынамічнага праграмавання, каб эфектыўна праверыць, ці можа радок быць атрыманы з сімвала пачатку граматыкі.
Алгарытм CYK, напрыклад, будуе табліцу, дзе кожная ячэйка ўяўляе сабой падрадок уваходнага радка і набор нетэрміналаў, якія могуць стварыць гэты падрадок. Шляхам ітэрацыйнага запаўнення табліцы на аснове правіл вытворчасці граматыкі алгарытм вызначае, ці можа пачатковы сімвал стварыць увесь уваходны радок. Калі сімвал пачатку з'яўляецца ў верхняй правай ячэйцы табліцы, значыць, радок прымаецца граматыкай; у адваротным выпадку гэта не так.
Разгледзім наступны прыклад: дапусцім, у нас ёсць кантэкстна-свабодная граматыка з правіламі вытворчасці:
S -> AB
А -> а
B -> b
Калі мы хочам вызначыць, ці прымаецца радок "ab" гэтай граматыкай, мы можам прымяніць алгарытм CYK. Алгарытм будуе табліцу з дзвюма ячэйкамі, па адной для кожнага сімвала ва ўваходным радку. Табліца выглядае наступным чынам:
| 1 | 2 |
—+—+—+
1 | A | S |
—+—+—+
2 | | B |
—+—+—+
Пачынаючы з ніжняга радка, мы бачым, што ячэйка (2,2) утрымлівае нетэрмінал B, які генеруецца правілам вытворчасці B -> b. Падняўшыся ў верхні радок, мы выявім, што ячэйка (1,2) утрымлівае нетэрмінальнае S, якое генеруецца правілам вытворчасці S -> AB. Нарэшце, ячэйка (1,1) змяшчае нетэрмінал A, які спараджаецца правілам вытворчасці A -> a. Паколькі сімвал пачатку S з'яўляецца ў верхняй правай ячэйцы, мы можам зрабіць выснову, што радок "ab" прымаецца граматыкай.
Праблема вызначэння таго, ці прымаецца дадзены радок кантэкстна-свабоднай граматыкай, вырашальная. Такія алгарытмы, як алгарытм CYK або алгарытм Эрлі, можна выкарыстоўваць для эфектыўнай праверкі, ці можа радок быць атрыманы з сімвала пачатку граматыкі. Гэтыя алгарытмы выкарыстоўваюць метады дынамічнага праграмавання для пабудовы табліц і вызначэння прыняцця радка.
Іншыя апошнія пытанні і адказы адносна Рашучасць:
- Ці можа стужка быць абмежавана памерам уваходу (што эквівалентна таму, што галоўка машыны Цьюрынга абмежавана рухацца за межы уваходу TM стужкі)?
- Што гэта значыць для розных варыянтаў машын Цьюрынга быць эквівалентнымі па вылічальных магчымасцях?
- Ці можа распазнавальная па Цьюрынгу мова ўтвараць падмноства вырашальнай мовы?
- Ці вырашальная праблема прыпынку машыны Цьюрынга?
- Калі ў нас ёсць дзве TM, якія апісваюць вырашальную мову, пытанне эквівалентнасці ўсё яшчэ невырашальнае?
- Чым праблема прыняцця для лінейных абмежаваных аўтаматаў адрозніваецца ад праблемы машын Цьюрынга?
- Прывядзіце прыклад задачы, якую можна вырашыць з дапамогай лінейнага абмежаванага аўтамата.
- Растлумачце паняцце вырашальнасці ў кантэксце лінейных абмежаваных аўтаматаў.
- Як памер стужкі ў лінейных абмежаваных аўтаматах уплывае на колькасць розных канфігурацый?
- У чым галоўнае адрозненне паміж лінейнымі абмежаванымі аўтаматамі і машынамі Цьюрынга?
Глядзіце дадатковыя пытанні і адказы ў раздзеле "Вырашальнасць".