Езици, Автомати, Изчислимост Тема 2

Недетерминирани крайни автомати
Представяне на всеки недетерминиран автомат с детерминиран

Недетирминиран Краен Автомат

НКА е машина с краен брой състояния, където за всяко едно от тях е позволено съществуването на повече от един преход с даден символ. Това го различава от детерминирания краен автомат (ДКА), където следващият ход е точно определен и единствен.
Естествено, с НКА може една и съща дума да се прочете по много начини. Ако поне един от тях я "приема"(както в ДКА се приема дума), то НКА приема думата. Както може би е очевидно, НКА "познава" кой е верният път до думата.
Основното предимство на тези автомати е, че в почти всички случаи НКА е много по-лесен за рисуване на картинка, отколкото ДКА. Да, сериозно.

Дефиниция:
Недетерминистичен краен автомат се описва от петорката $(K, \Sigma, \Delta, s, F)$ където

$K$ е крайно множество от състояния
$\Sigma$ е азбука
$s$ е начално състояние
$F$ е множество от финални състояния
$\Delta$ е функция на прехода, приемаща по един елемент от $K$ и от $\Sigma$ и връщаща подмножество на $K$.

Единствената разлика е, че в някой момент с дадена буква може да се отиде не в едно, а в потенциално няколко състояния.

Всяка тройка $(K, (\Sigma \cup \{ \varepsilon \} ), K)$ описва преход в НКА М.
Конфигурация в М отново наричаме $(K, \Sigma ^*)$. Релацията между конфигурациите $\vdash _M$ се определея по следния начин: $(q,w)\vdash _M (q',w') < = > u \in \Sigma \cup \{ \varepsilon \} :\,w = uw'\,\,\& \& \,\,(q,u,q') \in \Delta$ Тук, разбира се, релацията $\vdash_M$ не е нужно да бъде функция(т.е. детерминирана).
Както и при ДКА, $\vdash^* _M$ е рефлексивното и транзитивно затваряне на $\vdash _M$ и даден вход $w \in \Sigma^*$ бива приет от М тогава и само тогава когато $\exists q \in F:(s,w)\vdash ^* _M (q,e)$ .
И накрая, L(M) е множеството от всички изрази които биват приети от автомата.


Подобни недетерминирани конструкции не бива да се свързват в моделите на съвремените компютри. Те са просто едно полезно обобщение на крайните автомати. Още повече, НКА и ДКА са еквивалентни. Както ще видим по-долу - и двата вида автомати разпознават едни и същи езици.
За да бъде доказано това, трябва да се мине през 2 стъпки:

  1. Всеки ДКА може да се представи като НКА
  2. Всеки НКА може да се представи като ДКА

Естествено, първата стъпка е тривиална, защото всеки детерминиран автомат вече е и недетерминиран автомат(естествено, с нулева възможност за избор във всеки един момент, но какво пък толкоз).

Представяне на недетерминиран краен автомат с детерминиран

Теорема: За всеки недетерминиран краен автомат съществува еквивалентен детерминиран краен автомат.

Даден е НКА $А = (Q,\Sigma ,\Delta ,s,F)$. Търсим еквивалентен ДКА.
Това става по-лесно с картинка. Нарисувай си един автомат, ще почакам. Например, автомат, който разпознава думи с 2 поредни a-та, или с aba в тях.
Тръгваме си по състоянията и гледаме от къде до къде може да се отиде. Ако сме в състояние q0, и от него съществува $\epsilon$-преход към q1 (т.е. преход без да се използва буква от входния низ, безплатен преход), то казваме, че сме в състояние (q0, q1) - реално създаваме ново(в него все едно можем да сме в кое да е от двете първоначални). Това се генерализира и за повече от две състояния. Всяко състояние на автомата е от вида (q0, q1, … qn). Очевидно би трябвало да бъде, тогава, че повече от $2^{|Q|}$ състояния няма как да има. Този автомат вече е детерминиран (Например, ако от q0 можем да отидем в q1, q3 или q5, то сега вече ще ходим в (q1, q3, q5)).

Ще докажем, че разпознава същия език.
Да разгледаме $A' = (2^{|Q|},\Sigma ,\Delta' ,\left\{s\right\}, F' )$.
Състоянията са мааааалко повече.
Азбуката си е същата.
Функцията на прехода е променена, естествено, по начин, който би трябвало да е очевиден.
Началното състояние си е същото. Забележка: Възможно е в началното състояние да има епсилон-преходи към някакви други. Дали променяме {s}, или правим още магии с епсилони - историята мълчи(но, да, променяме го към каквото множество от състояния се получава. И пак си е начално).
Едно състояние се брои за крайно, ако в първоначалния автомат A е било крайно, или ако е комбинация от няколко състояния от A - поне едното от които е било крайно.

Формалното доказателство за това е малко дълго, а и не точно интуитивно. Може някой ден и то да бъде качено, но не мразиш ли онези доказателства, които четеш по 30 минути, а после пак нищо не разбираш?
Та, един НКА(да го наречем A) може да "прочете" една дума по много начини. Стига поне по един да завърши в крайно състояние, думата е приета. Тоест, за да се види дали една дума е от L(A), трябва да се проверят всички възможни нейни прочити. Детерминираният автомат A', който построихме, прави точно това. Прочита думата по всички възможни начини. Едновременно.
Накрая стига до състояние, което е множество от състоянията, в които може да е A след завършване на изпълнението. Ако поне едно от тях е крайно - тази част вече я говорихме, нали?

[[TODO: Картинка :)]]

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License