Якія тры ўмовы павінны быць выкананы, каб мова была рэгулярнай у адпаведнасці з лемай пра накачку?
Лема накачкі з'яўляецца фундаментальным інструментам у галіне тэорыі складанасці вылічэнняў, які дазваляе нам вызначыць, ці з'яўляецца мова рэгулярнай ці не. Згодна з лемай пра накачку, каб мова была рэгулярнай, павінны выконвацца тры ўмовы. Гэтыя ўмовы наступныя:
1. Умова даўжыні: першая ўмова абвяшчае, што для любога радка ў мове, які з'яўляецца дастаткова доўгім, існуе раскладанне радка на тры часткі, u, v і w, такое, што даўжыня v большая за нуль і меншы або роўны пастаяннаму значэнню, і канкатэнацыя u, v і w усё яшчэ існуе ў мове. Іншымі словамі, мова павінна ўтрымліваць радкі, якія можна падзяліць на тры часткі, дзе сярэдняя частка можа паўтарацца любую колькасць разоў, а выніковы радок усё яшчэ знаходзіцца ў мове.
2. Умова прапампоўкі: другая ўмова абвяшчае, што для любога радка ў мове, які задавальняе ўмове даўжыні, можна "прапампаваць" сярэднюю частку радка любую колькасць разоў і ўсё роўна атрымаць радок, які знаходзіцца ў мове. Гэта азначае, што пры паўтарэнні сярэдняй часткі атрыманы радок усё роўна павінен належаць мове.
3. Умова сяброўства: Трэцяя ўмова абвяшчае, што для любога радка ў мове, які задавальняе ўмовам даўжыні і запампоўкі, павінна існаваць даўжыня запампоўкі, пазначаная як p, такая, што любы радок, даўжэйшы за p, можа быць запампаваны. Гэта азначае, што для радкоў, большых за даўжыню накачкі, заўсёды можна знайсці раскладанне і паўтарыць сярэднюю частку, каб атрымаць радок, які ўсё яшчэ знаходзіцца ў мове.
Каб праілюстраваць гэтыя ўмовы, давайце разгледзім прыклад. Дапусцім, у нас ёсць мова L = {0^n1^n | n ≥ 0}, які складаецца з радкоў 0, за якімі ідзе такая ж колькасць 1. Мы можам прымяніць лему прапампоўкі, каб вызначыць, ці з'яўляецца гэтая мова рэгулярнай.
1. Умова даўжыні: выкажам здагадку, што даўжыня накачкі р. Разгледзім радок s = 0^p1^p. Мы можам раскласці гэты радок на тры часткі: u = 0^k, v = 0^l і w = 1^p, дзе k + l ≤ p і l > 0. Паколькі v змяшчае толькі нулі, запампоўка v прывядзе да радок, які змяшчае больш 0, чым 0, што парушае мову L. Такім чынам, умова даўжыні не выконваецца.
Паколькі ўмова даўжыні не выконваецца, можна зрабіць выснову, што мова L = {0^n1^n | n ≥ 0} не з'яўляецца рэгулярным згодна з лемай пра накачку.
Тры ўмовы, якія павінны быць выкананы для таго, каб мова была рэгулярнай у адпаведнасці з лемай прапампоўкі, - гэта ўмова даўжыні, умова прапампоўкі і ўмова членства. Гэтыя ўмовы забяспечваюць магутны інструмент для вызначэння рэгулярнасці моў у галіне тэорыі вылічальнай складанасці.
Іншыя апошнія пытанні і адказы адносна Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF:
- Якія асноўныя матэматычныя азначэнні, абазначэнні і ўводзіны неабходныя для разумення фармалізму тэорыі вылічальнай складанасці?
- Чаму тэорыя вылічальнай складанасці важная для разумення асноў крыптаграфіі і кібербяспекі?
- Якая роля рэкурсійнай тэарэмы ў дэманстрацыі невырашальнасці ATM?
- Разглядаючы КПК, які можа чытаць паліндромы, не маглі б вы падрабязна апісаць эвалюцыю стэка, калі ўвод з'яўляецца, па-першае, паліндромам, а па-другое, не паліндромам?
- Разглядаючы недэтэрмінаваныя КПК, суперпазіцыя станаў магчымая па азначэнні. Аднак недэтэрмінаваныя КПК маюць толькі адзін стэк, які не можа знаходзіцца ў некалькіх станах адначасова. Як такое магчыма?
- Што з'яўляецца прыкладам КПК, якія выкарыстоўваюцца для аналізу сеткавага трафіку і ідэнтыфікацыі шаблонаў, якія паказваюць на магчымыя парушэнні бяспекі?
- Што значыць, што адна мова больш магутная за іншую?
- Ці пазнаюцца кантэкстна-залежныя мовы машынай Цьюрынга?
- Чаму мова U = 0^n1^n (n>=0) нерэгулярная?
- Як вызначыць FSM, які распазнае двайковыя радкі з цотнай колькасцю сімвалаў «1», і паказаць, што з ім адбываецца пры апрацоўцы ўваходнага радка 1011?
Больш пытанняў і адказаў глядзіце ў раздзеле "Асновы тэорыі вылічальнай складанасці" EITC/IS/CCTF