www.wikidata.uk-ua.nina.az

Детермінізація НДСкА Детермінізація недетермінованого скінченного автомата полягає в перетворенні недетермінованого скін

Детермінізація НДСкА

Детермінізація недетермінованого скінченного автомата — полягає в перетворенні недетермінованого скінченного автомату на еквівалентний (тобто такий, що розпізнає таку ж формальну мову) детермінований скінченний автомат.

Еквівалентність НСА та ДСА Редагувати

Мову яка задана НСА можна задати і ДСА.

Позначимо наш НСА як , і будемо шукати ДСА .

Варто зауважити, що D набагато складніший за N, бо в найгіршому випадку . Це викликано тим, що стану D відповідає певна підмножина , а їх як відомо (див. булеан).

Правда в більшості випадків станів D набагато менше.

Покажемо еквівалентність конструктивно. Початковий стан D є просто множиною, що складається з одного елемента — початкового стану N. Вхідні алфавіти збігаються.

(детермінований автомат з стану який позначається множиною, робить перехід в стан який позначається множиною, яка є об'єднанням всіх множин в які переходить недетермінований з кожного свого поточного стану).

Булеанівська конструкція Редагувати

Булеанівська конструкція (англ. powerset construction, subset construction) — стандартний метод детермінізації НСА який базується на вищеописаному доведенні еквівалентності.

Імітація НСА Редагувати

Підхід використовний багатьма текстовими редакторами полягає в тому, щоб утворити НСА з регулярного виразу і, тоді імітувати НСА на ходу через використання чогось на кшталт булеанівської конструкції (англ. subset construction).

Алгоритм імітації НСА Редагувати

Вхід: Вхідний рядок завершується символом завершення файлу — eof. НСА з початковим станом , допустимими станами і функцією переходів move.

Вихід: Відповідь так, якщо приймає ; інакше ні.

Метод: Алгоритм тримає набір поточних станів , які наразі були досягнуті читанням рядка. Якщо  — наступний вхідний символ, читаємо функцією nextchar(), тоді спочатку обчислюємо move(S, c) і потім замикаємо цю множину за допомогою ε-closure(). 

1: S = ε-closure(s0); 2: c = nextchar(); 3: while ( c != eof ) { 4: S = ε-closure (move(S, c)) ; 5: c = nextchar(); 6: } 7: if ( S ∩ F != 0 ) return "yes"; 8: else return "no";

Швидкодія імітації НСА Редагувати

За умови обережного втілення, алгоритм може бути дуже швидким. Використана ідея може бути застосована в подібних алгоритмах пошуку на графах. Потрібні структури даних:

  1. Два стеки, кожен з яких містить набір станів НСА. Один з цих стеків, старі стани, містить значення в правій частині 4 рядка. Другий — нові стани. Під час проходу циклу нові стани переносятся в старі.
  2. Булевий масив alreadyOn, наповнений станами НСА, щоб позначити, які з них нові. Допоки масив і стек містять одні й ті самі дані, набагато швидше працювати з масивом ніж зі стеком. Провадимо обидві структури лише з огляду на швидкодію.
  3. Двомірний масив move[s, a], що містить таблицю переходів НСА. Записи в цій таблиці, які є наборами станів, представлені зв'язними списками.

Для втілення рядка (1), ми маємо встановити кожний запис масиву alreadyOn у FALSE, тоді для кожного стану s в c-closure(so), заштовхнути s у стек oldStates і встановити alreadyOn[s] в TRUE. Ця дія зі станом s, а також реалізація рядку (4), спрощується за допомогою функції яку ми назвемо addState(s). Ця функція заштовхує стан s у newStates, встановлює alreadyOn[s] у TRUE, і викликає себе рекурсивно на всіх станах у move[s, ε] для подальшого обчислення ε-closure(s). Однак, щоб уникнути подвійної роботи, ми маємо бути обачними і ніколи не викликати addState для стану, який уже в стеці newStates. 

 9: addState(s) { 10: push s onto newStates; 11: alreadyOn[s] = TRUE; 12: for ( t on move[s, ε] ) 13: if ( !alreadyOn(t) ) 14: addState(t) ; 15: }

Рядок (4) здійснимо через пошук усіх станів s у oldStates. Спочатку знайдемо множину станів move[s, c], де c — це наступний символ на вході, і для кожного з цих станів, який ще не в newStates, ми застосуємо addState до нього. 

16: for ( s on oldstates ) { 17: for ( t on move[s, c] ) 18: if ( !alreadyOn[t] ) 19: addState(t) ; 20: pop s from oldstates; 21: } 
22: for ( s on newstates ) { 23: pop s from newstates; 24: push s onto oldstates; 25: alreadyOn[s] = FALSE; 26: }

Якщо прийняти, що НСА має n станів і m переходів. Вірно втілений 4 рядок має складність O(n+m). Для вхідних даних довжини k загальна робота становить O(k(n+m)).

Обробка вхідних даних довжини k за допомогою ДСА вимагає O(k) часу. Очевидно, що отримати результат за допомогою ДСА набагато швидше ніж за допомогою НСА, але кількість станів у ДСА може бути настільки великою, що виділення пам'яті під таблицю переходів може стати неефективним. Хоча випадки з таким вибухом станів на практиці рідкісні. Імітація НСА може використовуватись такими застосунками як grep, де кожного разу пошук може відбуватись за новими параметрами. Тоді як у, наприклад, лексичних аналізаторах, де одні й ті самі регулярні вирази використовуються постійно, в пригоді стають ДСА.

Література Редагувати

Див. також Редагувати


Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (лютий 2017)
Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Determinizaciya nedeterminovanogo skinchennogo avtomata polyagaye v peretvorenni nedeterminovanogo skinchennogo avtomatu na ekvivalentnij tobto takij sho rozpiznaye taku zh formalnu movu determinovanij skinchennij avtomat Zmist 1 Ekvivalentnist NSA ta DSA 2 Buleanivska konstrukciya 3 Imitaciya NSA 3 1 Algoritm imitaciyi NSA 3 2 Shvidkodiya imitaciyi NSA 4 Literatura 5 Div takozhEkvivalentnist NSA ta DSA RedaguvatiMovu yaka zadana NSA mozhna zadati i DSA Poznachimo nash NSA yak N Q N S d N q 0 F N displaystyle N Q N Sigma delta N q 0 F N nbsp i budemo shukati DSA D Q D S d D q 0 F D displaystyle D Q D Sigma delta D q 0 F D nbsp Varto zauvazhiti sho D nabagato skladnishij za N bo v najgirshomu vipadku Q D 2 Q N displaystyle Q D 2 Q N nbsp Ce viklikano tim sho stanu D vidpovidaye pevna pidmnozhina Q N displaystyle Q N nbsp a yih yak vidomo 2 Q N displaystyle 2 Q N nbsp div bulean Pravda v bilshosti vipadkiv staniv D nabagato menshe Pokazhemo ekvivalentnist konstruktivno Pochatkovij stan D ye prosto mnozhinoyu sho skladayetsya z odnogo elementa pochatkovogo stanu N Vhidni alfaviti zbigayutsya F D S Q N S F N displaystyle F D S subset Q N S cap F N neq emptyset nbsp S Q N a S d D S a p S d N p a displaystyle forall S subset Q N forall a in Sigma delta D S a bigcup p in S delta N p a nbsp determinovanij avtomat z stanu yakij poznachayetsya mnozhinoyu robit perehid v stan yakij poznachayetsya mnozhinoyu yaka ye ob yednannyam vsih mnozhin v yaki perehodit nedeterminovanij z kozhnogo svogo potochnogo stanu Buleanivska konstrukciya RedaguvatiBuleanivska konstrukciya angl powerset construction subset construction standartnij metod determinizaciyi NSA yakij bazuyetsya na visheopisanomu dovedenni ekvivalentnosti Imitaciya NSA RedaguvatiPidhid vikoristovnij bagatma tekstovimi redaktorami polyagaye v tomu shob utvoriti NSA z regulyarnogo virazu i todi imituvati NSA na hodu cherez vikoristannya chogos na kshtalt buleanivskoyi konstrukciyi angl subset construction Algoritm imitaciyi NSA Redaguvati Vhid Vhidnij ryadok x displaystyle x nbsp zavershuyetsya simvolom zavershennya fajlu eof NSA N displaystyle N nbsp z pochatkovim stanom s 0 displaystyle s 0 nbsp dopustimimi stanami F displaystyle F nbsp i funkciyeyu perehodiv move Vihid Vidpovid tak yaksho M displaystyle M nbsp prijmaye x displaystyle x nbsp inakshe ni Metod Algoritm trimaye nabir potochnih staniv S displaystyle S nbsp yaki narazi buli dosyagnuti chitannyam ryadka Yaksho c displaystyle c nbsp nastupnij vhidnij simvol chitayemo funkciyeyu nextchar todi spochatku obchislyuyemo move S c i potim zamikayemo cyu mnozhinu za dopomogoyu e closure 1 S e closure s0 2 c nextchar 3 while c eof 4 S e closure move S c 5 c nextchar 6 7 if S F 0 return yes 8 else return no Shvidkodiya imitaciyi NSA Redaguvati Za umovi oberezhnogo vtilennya algoritm mozhe buti duzhe shvidkim Vikoristana ideya mozhe buti zastosovana v podibnih algoritmah poshuku na grafah Potribni strukturi danih Dva steki kozhen z yakih mistit nabir staniv NSA Odin z cih stekiv stari stani mistit znachennya S displaystyle S nbsp v pravij chastini 4 ryadka Drugij novi stani Pid chas prohodu ciklu novi stani perenosyatsya v stari Bulevij masiv alreadyOn napovnenij stanami NSA shob poznachiti yaki z nih novi Dopoki masiv i stek mistyat odni j ti sami dani nabagato shvidshe pracyuvati z masivom nizh zi stekom Provadimo obidvi strukturi lishe z oglyadu na shvidkodiyu Dvomirnij masiv move s a sho mistit tablicyu perehodiv NSA Zapisi v cij tablici yaki ye naborami staniv predstavleni zv yaznimi spiskami Dlya vtilennya ryadka 1 mi mayemo vstanoviti kozhnij zapis masivu alreadyOn u FALSE todi dlya kozhnogo stanu s v c closure so zashtovhnuti s u stek oldStates i vstanoviti alreadyOn s v TRUE Cya diya zi stanom s a takozh realizaciya ryadku 4 sproshuyetsya za dopomogoyu funkciyi yaku mi nazvemo addState s Cya funkciya zashtovhuye stan s u newStates vstanovlyuye alreadyOn s u TRUE i viklikaye sebe rekursivno na vsih stanah u move s e dlya podalshogo obchislennya e closure s Odnak shob uniknuti podvijnoyi roboti mi mayemo buti obachnimi i nikoli ne viklikati addState dlya stanu yakij uzhe v steci newStates 9 addState s 10 push s onto newStates 11 alreadyOn s TRUE 12 for t on move s e 13 if alreadyOn t 14 addState t 15 Ryadok 4 zdijsnimo cherez poshuk usih staniv s u oldStates Spochatku znajdemo mnozhinu staniv move s c de c ce nastupnij simvol na vhodi i dlya kozhnogo z cih staniv yakij she ne v newStates mi zastosuyemo addState do nogo 16 for s on oldstates 17 for t on move s c 18 if alreadyOn t 19 addState t 20 pop s from oldstates 21 22 for s on newstates 23 pop s from newstates 24 push s onto oldstates 25 alreadyOn s FALSE 26 Yaksho prijnyati sho NSA maye n staniv i m perehodiv Virno vtilenij 4 ryadok maye skladnist O n m Dlya vhidnih danih dovzhini k zagalna robota stanovit O k n m Obrobka vhidnih danih dovzhini k za dopomogoyu DSA vimagaye O k chasu Ochevidno sho otrimati rezultat za dopomogoyu DSA nabagato shvidshe nizh za dopomogoyu NSA ale kilkist staniv u DSA mozhe buti nastilki velikoyu sho vidilennya pam yati pid tablicyu perehodiv mozhe stati neefektivnim Hocha vipadki z takim vibuhom staniv na praktici ridkisni Imitaciya NSA mozhe vikoristovuvatis takimi zastosunkami yak grep de kozhnogo razu poshuk mozhe vidbuvatis za novimi parametrami Todi yak u napriklad leksichnih analizatorah de odni j ti sami regulyarni virazi vikoristovuyutsya postijno v prigodi stayut DSA Literatura RedaguvatiHopcroft John E Motwani Rajeev Ullman Jeffrey D 2001 Introduction to Automata Theory Languages and Computation vid 2 Addison Wesley Compilers Principles Techniques and Tools second edition Alfred V Aho Ravi Sethi and Jeffrey D Ullman Rozdil 3 7 Div takozh RedaguvatiMinimizaciya DSkA Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lyutij 2017 nbsp Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Determinizaciya NDSkA amp oldid 39175056