Поставки
Според теоремата на Клин, секој правилен изразможете да поврзете конечна машина, која е формален модел на алгоритам за препознавање на лексеми означени со даден правилен израз. Во најопшта смисла, државна машина-препознавачот се одредува со конечен сет на карактеристични состојби на влезниот тек и транзиции меѓу нив. Промената на состојбата се јавува кога симболите на влезниот тек се примаат од дадена азбука во согласност со функцијата за транзиција, кој ги одредува можните последователни состојби врз основа на влезниот симбол и моменталната состојба. Меѓу можните состојби се издвојува почетната(почетна) и конечна(дозволувајќи) состојби во кои конечниот автоматски препознавање може да биде, соодветно, на почетокот и завршувањето на обработката на токените на влезниот тек. Ако влезната низа на симболи може да генерира низа од транзиции што може да ја пренесе машината за конечни состојби од почетната состојба во една од конечните состојби, тогаш таа се смета за признава и припаѓа на редовното множество препознаено од него.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Табела 1
| 0 | 1 | |
| П1 | П4 | П2 |
| П2 | П3 | П1 |
| П3 | П2 | П4 |
| П4 | П1 | П3 |
Колоните од табелата за транзиција ги означуваат знаците на влезната азбука, а редовите одговараат на моменталните состојби на DFA. Елементите на секоја линија ги означуваат состојбите на DFA, на која мора да премине од моменталната состојба по добивањето на соодветните знаци од влезната азбука. Конкретно, од првата линија на оваа преодна табела следува дека примањето на симболите 0 и 1 во почетната состојба Q1 го преведува DFAна состојбите Q4 и Q2, соодветно.
Кога препознавате влезна низа користејќи ја табелата за транзиција, лесно е да се следат промените во состојбата на DFAсо цел да се утврди дали една од дозволените состојби е постигната или не. Конкретно, за бинарниот вектор 01001000 со парен број на нули и единици, разгледаниот DFAја генерира следната низа на транзиции, каде што секоја транзиција е означена со симболот на влезната азбука што ја предизвикува:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Оваа низа на транзиции завршува со прифатната состојба Q1, затоа, бинарниот вектор 01001000 припаѓа на редовното множество препознаено од разгледуваната DFAи го задоволува горенаведениот правилен израз.
Како заклучок, треба да се забележи дека сметаниот неформален метод на градење
од вкупниот број на знаци од азбуката на симболите и знаците за работа и заградите во записот r.Основа. Автомати за изрази со должина 1: и се прикажани на следната слика.
Ориз. 5.1.
Забележете дека за секоја од овие три автомати, множеството на конечни состојби се состои од една состојба.
Индукциски чекор. Сега да претпоставиме дека за секој правилен израз на должина = 1, зборот w може да се подели на k подзборови: w=w 1 w 2 ... w k и тоа е тоа. За секој i= 1,... ,k зборот w i го преведува q 0 1 во q f 1 . Тогаш за зборот w на дијаграмот М има патека
Оттука,. Спротивно на тоа, ако некој збор го преведува q 0 во q f , тогаш или постои или се носи со патека што, откако поминала од q 0 до q 0 1 и потоа поминува неколку пати по патеката од q 0 1 до q f 1 и се враќа назад од q f 1 до q 0 1 со -транзиција, на крајот од q f 1 со -транзиција завршува во q f . Затоа таков збор.
Од теоремите 4.2 и 5.1 директно добиваме
Заклучок 5.1. За секој редовен израз, може ефективно да се изгради детерминистичка машина за конечни состојби што го препознава јазикот претставен со тој израз.
Оваа изјава е еден од примерите на теоремите за синтеза: врз основа на описот на задачата (јазикот како регуларен израз), програма (DFA) што ја извршува е ефективно конструирана. Вистина е и обратното - теорема на анализа.
Теорема 5.2.
За секоја детерминистичка (или недетерминистичка) машина за конечни состојби, можно е да се конструира правилен израз кој го претставува јазикот препознаен од таа машина.
Доказот за оваа теорема е доста технички и надвор од опсегот на нашиот курс.
Така, можеме да заклучиме дека класата на крајно автоматски јазици се совпаѓа со класата на редовни јазици. Отсега натаму едноставно ќе го нарекуваме класа на јазици на автомати.
Автоматот M r, кој е конструиран во доказот на теорема 5.1
За понатамошно проучување на својствата на конечните автомати и, особено, за решавање на проблемот со синтезата, важна е следната теорема.
За да се докаже теоремата, потребно е, прво, да се опише алгоритмот за конструирање на детерминистички конечен автомат од првобитниот; второ, да се оправда овој алгоритам со ригорозно докажување дека тој навистина произведува државна машина која е детерминистичка и еквивалентна на оригиналната. Овде го претставуваме само алгоритмот за конструирање на детерминистички автомат.
Трансформацијата на произволен конечен автомат во еквивалентен детерминистички се врши во две фази: прво се отстрануваат лаковите со ознаката \lambda, а потоа се врши самата детерминизација.
1. Отстранување на λ-транзиции (лакови означени со \lambda).
За да се оди од оригиналниот конечен автомат M=(V,Q,q_0,F,\делта) на еквивалентен конечен автомат M"=(V,Q",q_0,F",\делта") без λ-транзиции, е доволно во оригиналот направете ги следните трансформации во графиконот М.
А. Сите состојби, освен почетната, во која влегуваат само лакови со ознаката \lambda, се бришат; со што се дефинира множеството Q" на конечниот автомат М". Јасно е дека Q"\subseteq Q. Во исто време, претпоставуваме дека почетната состојба останува иста.
б.
Множеството лакови на конечниот автомат M" и нивните ознаки (притоа, функцијата на преодот M") се дефинира на следниов начин: за било кои две состојби p,r\in Q",~ p\to_(a)r се јавува ако и само ако a \ во V , и во графикот M важи една од двете работи: или има лак од p до r чија ознака го содржи симболот a, или постои состојба q таква што p\Rightarrow_(\lambda)^( +)q и q\ to_(a)r Во овој случај, темето q, генерално кажано, може да не припаѓа на множеството Q", т.е. може да исчезне при преминување до автоматот М" (сл. 7.11). Ако q\in Q" , тогаш, природно, лакот (q,r) ќе се зачува во М" и симболот a ќе биде еден од симболите кои припаѓаат на ознаката на овој лак (сл. 7.12).
В. Множеството конечни состојби F" на конечниот автомат М" ги содржи сите состојби q\in Q", т.е. состојби на конечниот автомат М кои не се избришани според став a, за што q\Rightarrow_(\lambda)^(\ ast) го држи q_f за некои q_f\in F (т.е. или самата состојба q е конечна состојба на конечниот автомат M, или патека со должина не нула води од него по лаците означени \lambda до една од крајните состојби на конечен автомат М) (сл. 7.13) .
2. Самото определување.
Нека M=(Q,V,q_0,F,\делта) е конечен автомат без λ-транзиции. Дозволете ни да конструираме детерминистички конечен автомат M_1 еквивалентен на M.
Овој конечен автомат е дефиниран на таков начин што неговото множество на состојби е множество од сите подмножества на множеството состојби на конечниот автомат М. Ова значи дека секоја поединечна состојба на конечниот автомат М_1 е дефинирана како одредено подмножество од множеството состојби на конечниот автомат М. Во овој случај, почетната состојба на новата машина за конечни состојби (т.е. M_1) е еднотонско подмножество кое ја содржи почетната состојба на старата машина за конечни состојби (т.е. М), а крајните состојби на новата машина за конечни состојби се сите такви подмножества Q кои содржат барем едно финално теме на оригиналниот конечен автомат М.
Отсега натаму, дозволувајќи одредена слобода на говор, понекогаш состојбите на конечните автомати ќе ги нарекуваме состојби-множества M_1. Меѓутоа, важно е јасно да се разбере дека секое такво множество на состојби е посебна состојба на нов конечен автомат, но не и збир од неговите состојби. Во исто време, за оригиналниот („стар“) конечен автомат М ова е токму множеството на неговите состојби. Фигуративно кажано, секое подмножество на состојби на стариот конечен автомат се „склопува“ во една состојба на новиот конечен автомат*.
*Формално, треба да го дефинираме множеството Q_1 како множество што е во кореспонденција еден-на-еден со множеството 2^Q, но сепак е попогодно за нас да претпоставиме дека Q_1 се совпаѓа со 2^Q - на крајот на краиштата, збир на состојби на конечен автомат може да биде секое непразно конечно множество.
Функцијата на транзиција на новиот конечен автомат е дефинирана на тој начин што од множеството на состојби S со влезниот симбол a, конечниот автомат M_1 оди во множеството на состојби, кое е заедница на сите множества состојби на старото конечно. автомат во кој овој стар конечен автомат поминува со симболот a од секоја состојба множество S. Така, конечниот автомат M_1 е детерминистички по конструкција.
Горенаведениот вербален опис може да се преведе во формули како што следува: градиме конечна машина M_1 така што
M_1=(Q_1,V,\(q_0\),F_1,\делта_1) , каде
\почеток(случаи)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\за сите S\подподелба Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \крај (случаи)
Да забележиме дека меѓу состојбите на новиот конечен автомат постои состојба \varnothing , и, според (7.8), \delta_1(\varnothing,a)=\varnothing за кој било влезен симбол a . Ова значи дека, еднаш во таква состојба, машината за конечни состојби M_1 нема да ја напушти. Општо земено, секоја состојба q на конечен автомат, таква што за кој било влезен симбол a имаме \delta(q,a)=q се нарекува апсорпциона состојба на конечниот автомат. Така, состојбата \varnothing на детерминистичката машина за конечни состојби M_1 апсорбира. Исто така, корисно е да се забележи дека \delta_1(S,a)=\varnothing ако и само ако за секој q\in S (состојби на старата машина за конечни состојби од множеството состојби S ) \delta(q,a)= \varnothing, т.е. во графиконот M, не излегува лак од секоја таква состојба q, означена со симболот a.
Може да се докаже дека конечниот автомат добиен со овој алгоритам е еквивалентен на оригиналниот.
Пример 7.9.
Дозволете ни да го одредиме конечниот автомат прикажан на сл. 7.14.
Еквивалентен конечен автомат без λ-транзиции е прикажан на сл. 7.15. Забележете дека темето q_2 исчезнува, бидејќи во него влегуваат само „празни“ лакови.
За да се одреди добиениот автомат, воопшто не е неопходно да се запишат сите негови 2^3=8 состојби, од кои многу не се достапни од почетната состојба \(q_0\) . За да добиеме состојби кои се достапни од \(q_0\), и само нив, ќе го користиме таканаречениот метод на влечење.
Во почетниот конечен автомат (без празни лакови) ги дефинираме сите множества на состојби кои се достапни од почетната, т.е. за секој влезен симбол a го наоѓаме множеството \delta(q_0,a) . Секој таков сет во новиот автомат е состојба директно достапна од почетната.
За секое од дефинираните множества на состојби S и секој влезен симбол a, го наоѓаме множеството \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( А) ^ ( .))) . Сите состојби добиени на овој чекор ќе бидат состојби на нов (детерминистички) автомат, достапен од почетното теме по патека со должина 2. Ја повторуваме опишаната постапка додека не се појават нови состојби на множество (вклучувајќи ја и празната!). Може да се покаже дека ова ги произведува сите состојби на конечниот автомат M_1 кои се достапни од почетната состојба \(q_0\) .
За машината за конечни состојби на сл. 7.15 имаме:
\почеток (порамнет)& \delta_1 (\(q_0\),a)=\(q_1\);\qquad \delta_1 (\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1 (\(q_1,q_3\) ,а)= \делта(q_1,а)\чаша \делта(q_3,a)= \(q_1\)\чаша\(q_1\)=\(q_1\);\\ & \делта_1(\(q_1, q_3\),b)= \делта(q_1,б)\чаша \делта(q_3,b)= \(q_1\)\чаша\(q_1\)=\(q_1\). \end (порамнет)
Бидејќи не се појавија нови множества на состојби, процедурата за „влечење“ завршува овде, и го добиваме графикот прикажан на сл. 7.16.
Редовно додавање јазикЕдна од важните теоретски последици на теоремата за детерминизација е следната теорема.
Теорема 7.8.
Комплементот на редовен јазик е редовен јазик.
Според теорема 7.7, за правилен јазик L, може да се конструира детерминистички конечен автомат М кој го признава L. Бидејќи во детерминистички автомат од секое теме за секој влезен симбол е дефинирана транзиција кон точно едно теме, тогаш што и да е синџирот x во азбуката V, постои единствена патека за него во M, почнувајќи од почетната состојба на која се чита синџирот x. Јасно е дека синџирот x е дозволен од автоматот M , односно x\in L(M) , ако и само ако последната состојба на наведената патека е конечна. Следи дека синџирот x\notin L(M) ако и само ако последната состојба на наведената патека не е конечна. Но, ни треба само конечен автомат М" кој признава синџир x ако и само ако тоа не е дозволено од оригиналниот конечен автомат М. Следствено, претворајќи ја секоја конечна состојба на М во нефинална состојба и обратно, добиваме детерминистички автомат кој го признава додавањето на јазикот Л.
Докажаната теорема ни овозможува да изградиме конечен автомат кој не прифаќа одредено множество синџири, користејќи го следниов метод: прво градиме автомат кој прифаќа дадено множество синџири, потоа го одредуваме и одиме во автоматот за собирање како посочено во доказот на теоремата 7.8.
Пример 7.10.
А. Ајде да изградиме конечен автомат кој ги прифаќа сите синџири во азбуката \(0;1\) освен синџирот 101.
Прво, ајде да изградиме конечен автомат кој дозволува единечен ланец 101. Овој автомат е прикажан на сл. 7.17.
Овој автомат е квази-детерминистички, но не и детерминистички, бидејќи не е целосно дефиниран. Дозволете ни да го одредиме и да добиеме детерминистички еквивалентен конечен автомат прикажан на сл. 7.18.
И, конечно, преминувајќи кон додавање (и преименување на состојбите), го добиваме автоматот прикажан на сл. 7.19.
Забележете дека во добиениот автомат сите темиња, освен темето s_3, се конечни.
Забележете исто така дека машината за конечни состојби на Сл. 7.19 ги дозволува сите низи кои содржат појава на низа 101, но не се совпаѓаат со таа низа. Еве, на пример, патеката што носи синџир 1011: s_0,s_1,s_2,s_3,t.
б.
Ајде да изградиме конечен автомат кој ги прифаќа сите синџири во азбуката \(0;1\) освен оние што содржат појава на низата 101. Размислете за јазик L, чијшто синџир содржи појава на низата 101. Може да биде дефинирано на следниов начин:
L=(0+1)^(\ast)101(0+1)^(\ast).
Треба да изградиме автомат кој ќе го надополни јазикот L.
Во овој случај, директно користејќи го правилниот израз, лесно е да се конструира конечен автомат кој го прифаќа јазикот L (сл. 7.20).
Потоа ќе извршиме одредување користејќи го методот „повлече“. Резултатот од определувањето е претставен на сл. 7.21.
За целосно решавање на проблемот, останува само на сл. 7.21 заменете ги улогите на завршните и незавршните темиња (сл. 7.22).
В. Ајде да разговараме за идејата за конструирање на конечен автомат кој ги дозволува оние и само оние синџири во азбуката \(0;1\) кои не започнуваат со синџирот 01 и не завршуваат со синџирот 11 (т.е. форма 01x и синџири од типот y11 не се дозволени, без разлика што имало синџири x,y\in\(0;1\) ).
Во овој случај, комплементот на јазикот за кој е неопходно да се конструира конечен автомат е множеството од сите такви синџири од нули и оние кои започнуваат со синџирот 01 или завршуваат со синџирот 11. Автомат кој го дозволува ова збир на синџирите се конструирани како автомат за комбинирање на 01(0+1)^(\ ast)+(0+1)^(\ast)11 на ист начин како што е опишано во доказот на теоремата на Клин (види теорема 7.6).
Од својството дека класата на регуларни јазици е затворена во однос на комплементот (види теорема 7.8) веднаш следува дека оваа класа е затворена во однос на пресекот, теоретската множество и симетричната разлика.
Заклучок 7.3.
За кои било два редовни јазици L_1 и L_2, следниве изјави се точни:
1) пресекот на L_1\cap L_2 е правилен;
2) разликата L_1\setminus L_2 е правилна;
3) симетричната разлика L_1\вартриаголник L_2 е правилна.
Прво, добиените резултати ни овозможуваат да тврдиме дека класата на регуларни јазици во однос на операциите на унија, пресек и собирање е Булова алгебра, во која единицата е универзален јазик, а нулата е празниот јазик. Второ, овие алгебарски својства на семејството на редовни јазици ни овозможуваат да го решиме важниот проблем за препознавање на еквивалентноста на два произволни конечни автомати.
Според дефиницијата 7.10, машините со конечни состојби се еквивалентни ако јазиците што ги прифаќаат се исти. Затоа, за да се потврди еквивалентноста на автоматите M_1 и M_2, доволно е да се докаже дека симетричната разлика на јазиците L(M_1) и L(M_2) е празна. За да го направите ова, за возврат, доволно е да се конструира автомат кој ја признава оваа разлика и да се осигура дека јазикот што го признава е празен. Општо земено, проблемот со препознавањето дека јазикот на државната машина е празен се нарекува проблем со празнината на државната машина. За да се реши овој проблем, доволно е да се најде множеството на конечни состојби на автоматот што се достапни од почетната состојба. Бидејќи машината за конечни состојби е насочен граф, овој проблем може да се реши, на пример, со користење на пребарување на широчина. Јазикот дозволен од машина за конечни состојби е празен ако и само ако сетот на конечни состојби достапни од почетната состојба е празен. Во пракса, се претпочита да се препознае еквивалентноста на конечните автомати користејќи алгоритам за минимизирање, но сега е важно за нас да нагласиме дека основната можност за решавање на проблемот со еквивалентноста произлегува од теоремата 7.7 и нејзините алгебарски последици.
ДКА е посебен случај на НКА. Во него:
нема состојба со ε-транзиции;
за секоја состојба S и влезен симбол a, има најмногу еден лак кој произлегува од S и е означен како a.
DFA има само максимум една транзиција за кој било влезен симбол од секоја држава. Ако табела се користи за претставување на функцијата за транзиција на DFA, тогаш секој запис ќе содржи само една состојба. Така, лесно е да се провери дали дадена DFA прифаќа одредена линија, бидејќи има само една патека од почетната состојба, која е означена со оваа линија.
Слика 3 го прикажува преодниот график на DFA што го прифаќа истиот јазик (a|b) * a(a|b)(a|b) како NFA на слика 1.
Слика 3. DFA дозволувајќи ја низата (a|b) * a(a|b)(a|b).
Детерминистички конечен автомат М кој го прифаќа дадениот јазик:
M = ((1, 2, 3, 4, 5, 6, 7, 8), (а, б), D, 1, (3, 5, 6, 8))
Преодната функција D е дефинирана на следниов начин:
1. За ε NKA ја има следната форма (0 – почетна состојба, 1 – конечна состојба):
2. За вклучен во даден NKA јазик:
3. Нека N(s) и N(t) се NFA за правилни изрази s и t.
За правилниот израз s|t, композитниот NFA ја има следната форма:
б. За правилниот израз st NKA:
Со. За изразот s*, NFA има форма:
г. За изразот во загради (и), NFA N(s) се користи како во точка а.
Секоја нова држава добива индивидуално име. Конструкцијата на NFA N(r) ги има следните својства:
N(r) има број на состојби кои не го надминуваат бројот на симболи за повеќе од 2 пати.
N(r) има точно една почетна и една завршна состојба. Конечната состојба нема појдовни транзиции.
Секоја состојба N(r) има или 1 премин за симбол од азбуката (), или не повеќе од 2 излезни ε-транзиции.
Конвертирање на nka во dka.NFA на слика 1 има 2 премини од состојбата 0 за симболот a: наведува 0 и 1. Таквата транзиција е двосмислена, како преминот во ε. Моделирањето на такви сателити со помош на компјутерска програма е многу потешко. Дефиницијата за изводливост вели дека мора да има некоја патека од почетната состојба до крајната состојба, но кога има повеќе патеки за иста влезна низа, сите тие мора да се земат предвид за да се најде патека до конечната состојба или да се открие дека таму не е таков пат.
Во табелата за транзиција NKA, секој запис одговара на многу состојби, но во табелата за транзиција DKA има само една. Суштината на трансформацијата е дека секоја DFA состојба одговара на збир на NFA состојби. DFA ги користи своите состојби за да ги следи сите можни состојби во кои може да се наоѓа NFA откако ќе го прочита следниот влезен симбол. Односно, по читањето на влезниот тек, DFA е во состојба што претставува одреден сет на состојби на NFA, достапни од почетната по патеката што одговара на влезната низа. Бројот на такви DFA состојби може значително да го надмине бројот на NFA состојби (експоненцијална зависност), но во пракса тоа е исклучително ретко, а понекогаш има уште помалку состојби во DFA отколку во NFA.
Ајде да разгледаме таква трансформација користејќи конкретен пример. Слика 4 покажува друга NFA што го дозволува јазикот (a|b) * a(a|b)(a|b) (како на сликите 1 и 3).
Слика 4. NFA што дозволува јазик (a|b) * a(a|b)(a|b)
Преминот од состојба 13 во состојба 14 прикажан на сликата може да се претстави слично како и преминот од 8-та во 13-та состојба.
Ајде да изградиме DFA за овој јазик. Почетната состојба на еквивалентниот DFA е состојбата A = (0, 1, 2, 4, 7), односно оние состојби кои може да се достигнат од 0 со ε.
Азбуката на влезниот симбол е (a, b). Од почетната состојба А, може да се пресмета состојбата достапна со a. Да ја наречеме оваа состојба B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).
Помеѓу состојбите во А, само состојбата 4 има транзиција долж b во состојба 5, така што DFA има премин долж b од A во состојба C = (1, 2, 4, 5, 6, 7).
Ако го продолжиме овој процес со состојбите B и C, сите групи на состојби на NFA ќе бидат означени. Така ќе имаме множества на состојби:
A = (0, 1, 2, 4, 7)
B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)
C = (1, 2, 4, 5, 6, 7)
D = (10, 12, 13, 14)
Состојбата А е почетна состојба, а состојбите B, D, E се конечни.
Целосната табела за транзиција е прикажана подолу.
Подолу на Слика 5 е самиот DFA за овој јазик.
Слика 5. Јазик што прифаќа DFA (a|b) * a(a|b)(a|b)
Список на користена литература:
Pentus A. E., Pentus M. R. – Теорија на формалните јазици
A. Aho, R. Sethi, D. Ullman - Компајлери: принципи, технологии, алатки.
Редовните изрази (RE) се многу погодна форма за пишување таканаречени редовни или автоматски јазици. Затоа, RT се користат како влезен јазик во многу системи кои обработуваат синџири. Ајде да погледнеме примери на такви системи:
- Оперативниот систем Unix grep или слични команди бараат низи што може да се најдат во веб-прелистувачите или системите за форматирање текст. Во такви системи, RF се користат за да се опишат шемите што корисникот ги бара во датотеката. Различни пребарувачи го претвораат пребарувачот или во детерминистичка машина за конечни состојби (DFA) или во недетерминистичка машина за конечни состојби (NFA) и ја применуваат оваа машина на датотеката што се пребарува.
- Генератори на лексички анализатори. Лексичките анализатори се компонента на компајлерот тие ја разградуваат изворната програма на логички единици (токени), кои можат да се состојат од еден или повеќе знаци и да имаат специфично значење. Генераторот на лексички анализатор добива формални описи на лексеми, кои во суштина се RV, и создава DFA што препознава која од лексемите се појавува во нејзиниот влез.
- RV во програмските јазици.
Во оваа статија, прво ќе се запознаеме со машините со конечни состојби и нивните типови (DFA и NFA), а потоа ќе разгледаме пример за конструирање на минимален DFA користејќи регуларен израз.
Машини за конечни состојби Машината за конечни состојби (FA) е конвертор кој ви овозможува да поврзете влез со соодветен излез, а овој излез може да зависи не само од тековниот влез, туку и од она што се случило претходно, од историјата на операцијата на машината за конечни состојби. Дури и човечкото однесување, а не само вештачките системи, може да се опише со помош на вселенски летала. На пример, вашата реакција на фактот дека вашиот сосед слуша гласна музика навечер ќе биде една по првиот ваков инцидент и сосема поинаква по неколку такви инциденти. Може да има бесконечен број на таква праисторија, се поставува прашањето: каква меморија треба да има леталото за да се однесува различно за секоја праисторија; Јасно е дека е невозможно да се складираат бесконечен број на задни приказни. Затоа, автоматскиот вид ги разложува сите можни праистории во класи на еквивалентност. Две истории се еквивалентни ако имаат исто влијание врз однесувањето на машината во иднина. Класата на еквивалентност на која автоматот ја доделил својата тековна историја се нарекува и внатрешна состојба на автоматот.Да разгледаме пример за работа на примитивно вселенско летало:
Ова вселенско летало се состои од:
- лента претставена со влезниот синџир.
- уред за читање.
- контролен блок кој содржи листа на правила за транзиција.
Читателот може да се движи во една насока, обично од лево кон десно, со што ги чита знаците на влезната низа. За секое такво движење може да брои по еден симбол. Следно, знакот за читање се пренесува до контролната единица. Контролната единица ја менува состојбата на машината врз основа на правилата за транзиција. Ако списокот со правила за транзиција не содржи правило за симболот за читање, тогаш машината „умира“.
Сега да ги погледнеме начините на кои може да се специфицира CA. Тие можат да бидат наведени во форма на графикони или во форма на контролни табели. Во форма на график, CA е наведен на следниов начин:
- темињата на графикот одговараат на состојбите на леталото.
- насочените рабови одговараат на преодните функции (до секој таков раб е означен симболот по кој се врши преминот).
- теме со раб што влегува во него што не остава повеќе од една состојба одговара на почетната состојба.
- крајните состојби на леталото се означени со дебел преглед.
Во форма на контролна табела, вака:
- состојбите на леталото се наоѓаат во редовите на табелата.
- знаците на препознаениот јазик се во колони.
- на раскрсницата се означува состојба до која може да се дојде од дадена состојба со користење на даден симбол.
Пример за CA во форма на график и во форма на контролна табела ќе биде претставен подолу.
ДКА и НКАГлавната разлика помеѓу DKA и NKA е тоа што DKA може да биде само во една состојба за време на работата, додека NKA може да биде во неколку состојби во исто време. Како пример за работата на NCA, може да се наведе идејата на американскиот физичар Хју Еверет дека секој настан го дели светот на неколку светови, во секој од нив овој настан заврши на свој начин. На пример, во еден свет Хитлер победи во Втората светска војна, во друг, Њутн отиде во бизнис наместо со физика и откривањето на законите на класичната механика мораше да се одложи за 50 години за да се извлечат какви било заклучоци од работата на автоматот, сите „светови“ треба да се проучат. Откако ќе се прочита целиот влезен синџир, претпоставуваме дека NFA го прифаќа овој синџир ако ја завршила операцијата во прифатлива состојба во барем еден од многуте „светови“. Соодветно на тоа, автоматот го отфрла синџирот ако тој заврши во неприфатлива состојба во секој „свет“. DKA го прифаќа синџирот ова е очигледно ако, по читањето на целиот влезен синџир, се најде во состојба на прифаќање.
Во повеќето случаи, многу е полесно да се изгради NKV отколку DKA. Но, и покрај ова, користењето на NKA за моделирање не е добра идеја. За среќа, за секоја NFA е можно да се конструира DFA што го прифаќа истиот влезен јазик. Во оваа статија нема да претставиме алгоритам за конструирање на DFA користејќи NFA, туку ќе го разгледаме овој алгоритам врз основа на илустративниот пример подолу.
Конструирање минимална DFA користејќи регуларен изразЗа почеток, еве список на RT операции што се користат во овој напис, по приоритет:
- повторување (затворање на Kleene), користејќи го симболот "*"
- конкатенацијата се одредува со помош на празно место или празна низа (на пример: ab)
- приклучување со помош на симболот "|".
Ајде да погледнеме пример каде е даден регуларен израз:
Xy* (x | y*) |
ab (x | y*) |
(x | a*) (x | y*)
Неопходно е да се конструира минимална DFA користејќи регуларен израз и да се демонстрира препознавање на точни и неточни синџири.
За почеток, да го поедноставиме овој RV, користејќи го десниот дистрибутивен закон за конкатенација во однос на унијата, го добиваме следниот RV:
(xy* | ab | (x | a*)) (x | y*)
Сега градиме автомат врз основа на овој RV:
Според правилото за конвертирање на конкатенација (нема да ги дадеме правилата за претворање на PB во KA, бидејќи тие се сосема очигледни), го добиваме следниот автомат:
И на крајот го применуваме правилото за трансформација на затворање и добиваме εNKA. Овде е неопходно да се направи резервација дека εNKA е NKA што содржи ε-транзиции. За возврат, ε-транзиција е транзиција во која машината не го зема предвид влезниот синџир или, со други зборови, премин по празен симбол.
Се ослободуваме од ε-транзиции („ѕвездичката“ ги означува конечните состојби):
Во оваа NFA, состојбите s3 и s5 се еквивалентни, бидејќи δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Преименувајте ги состојбите s6 -> s5 и s7 -> s6:
Ние градиме DKA според NKA:
Во овој DFA, состојбите p1 и p5 се еквивалентни, бидејќи
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Преименувајте ги состојбите p6 -> p5 и p7 -> p6:
Оваа машина е минимална DKA.
Нека δ е преодна функција, тогаш ја означуваме продолжената преодна функција конструирана од δ со δ’, а ω е влезниот синџир.
Да претпоставиме дека влезот е синџир ω = aaax, очекуваме дека машината ќе биде во една од условите за прифаќање.
δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
P4 е валидна конечна состојба, така што синџирот aaax е точен за оваа машина.
Сега да претпоставиме дека ω = xyyb:
δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅
Овде гледаме дека ако го дадеме симболот b на влезот на автоматот кога тој е во состојба p1, тогаш овој автомат ќе умре, затоа ланецот xyyb е неточен.
P. S. Оваа статија го дискутираше алгоритмот за конструирање на DFA користејќи RT, но има попогодни алгоритми, особено за програмирање, но ова е тема за друга статија...