Недетерминиран краен автомат

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

Пример

Погледни следната диаграма на автомат:

Какво е странното в нея? Че от възела q₀ водят две ребра за символа 0. Ако се опитаме да приемем думата 001, би изглеждало, че автоматът няма да знае дали да остане в състоянието q₀, или да последва прехода към q₁. Такъв автомат би бил недетерминиран.

Детерминизмът в този смисъл означава, че във всяка ситуация е ясно какво ще направи автоматът, няма място за нееднозначност. Детерминираният автомат има за всяко състояние и всеки символ само един преход. Недетерминизмът означава нееднозначност — от едно състояние за един и същ символ могат да водят например три прехода.

И как тогава автоматът взема решение? Недетерминираният автомат винаги избира (понякога казваме също „налучква“) онзи преход, който води до приемане на думата, ако това е възможно.

Ако въведем в автомата думата 001, автоматът има следните възможности да се справи с нея:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

плюс възможностите, при които не прочита цялата дума. В първия клон оставаше постоянно в състоянието q₀, което със сигурност може, правилата за преходите го позволяват. Във втория клон се осмели да премине в следващите състояния и накрая стигна до състоянието q₂, което е крайно. В този клон автоматът би приел думата. Недетерминираният автомат винаги автоматично избира онзи клон, в който приема думата, ако такъв клон съществува.

Как успява автоматично да избере „благоприятния“ клон? Можем да си го представим така, че недетерминираният автомат обхожда всички възможни клонове и ако намери клон, в който приема думата, тогава приема думата. Как би могъл да обходи всички клонове? Просто в момента, когато е в състояние, от което за текущия символ водят n ребра, автоматът копира себе си n пъти и всяко копие тръгва по различен път. По този начин постепенно обхождаме всички възможности.

Дървовидно представяне на изчислението на автомата

Леко ще променим предишния автомат:

Недетерминизмът остава в първото състояние. Предишният автомат приемаше всички думи, които завършват на 01. Този променен автомат приема всички думи, които съдържат поддумата 01. Така че приема например думата 101 или 0101. Всички клонове на изчислението лесно можем да визуализираме с помощта на дърво, например за думата 01010 дървото би могло да изглежда така:

В началото сме в началното състояние q₀. На входа имаме думата 01010, първият непрочетен знак е 0. От състоянието q₀ водят два прехода за символа 0, към състоянията q₀ и q₁. Дървото в този възел ще има два наследника: q₀ и q₁. После четем символа 1. Там няма никаква нееднозначност, преминаваме в състоянията q₀ и q₂. После четем знака 0, в левия клон отново възниква нееднозначност, разделяме изчислението на още два клона. В единия отново оставаме в q₀, а в другия отиваме в q₁. И така нататък.

Забележи, че общо два клона завършват в състоянието q₂, в крайно състояние. Има два клона на изчислението, по които автоматът може да приеме дадената дума. Този автомат следователно би приел думата 01010. Можем да опитаме да построим подобно дърво за думата 1000.

Изчислението или остава в състоянието q₀, или преминава в състоянието q₁, но оттам вече няма накъде да върви, защото на входа са останали само нули, а състоянието q₁ има преход само за символа 1. Нито един клон на изчислението не завършва в крайно състояние, така че автоматът не приема думата 1000.

ε-преходи

В недетерминираните автомати можем освен това да използваме и ε-преходи (епсилон преходи). Това са преходи, които можем да извършим, какъвто и да е символът на входа, и то без да прочитаме някакъв символ от думата. Как бихме могли да запишем недетерминиран автомат, който приема празната дума, всички думи, състоящи се само от единици, и думите от вида (10)ⁿ, т.е. 10, 1010, …?

Разделихме автомата на два „подавтомата“. Горният се грижи да разпознава думите, състоящи се от 1, долният се грижи за думите от вида (10)ⁿ. Ще опитаме да приемем думата 111. В началото автоматът се намира в състоянието q₀ и на входа има думата 111. Тъй като има на разположение ε-преходи, може да реши да премине в състоянието q₁ или q₂ според това, което му е удобно. Виждаме, че ще му е удобно да премине в състоянието q₁. Автоматът преминава там. При това на входа все още има думата 111! Едва в този момент започва да чете символи от думата и да преминава от състоянието q₁ отново в q₁, докато прочете цялата дума и я приеме.

Ако опитаме да приемем 1010, автоматът в началото би преминал в състоянието q₂ и едва оттам би започнал да обработва символите и отново би приел думата.

За думата 1100 автоматът може да прави каквото си иска, той няма как да приеме такава дума.

ε-преходите и недетерминизмът ни облекчават работата в много отношения, например доказателството, че обединението на регулярни езици е отново регулярен език, може да се напише с ε-преходи много по-просто, отколкото в случая на детерминирани крайни автомати. В това доказателство имахме примери за тези автомати

и след това построихме краен детерминиран автомат, който приемаше обединението на двата езика. С ε-преходи можем да построим такъв автомат така:

Просто добавяме ново начално състояние, от него водят два ε-прехода към първоначалните начални състояния на първоначалните автомати и това е всичко. Автоматът недетерминирано решава дали ще се опита да приеме думата с единия, или с другия „подавтомат“.

Определение на недетерминиран автомат

Вече показахме с какво се различават детерминираният и недетерминираният краен автомат, остава само да го формализираме. Детерминирания краен автомат определихме като петорка ⟨Q, Σ, δ, q₀, F⟩, където Q е множеството на състоянията, Σ е азбуката, δ е преходната функция, q₀ е началното състояние и F е множеството на крайните състояния. Единственото, което се променя в определението на недетерминираните автомати, е определението на преходната функция.

В детерминираната версия функцията при извикване δ(q, w) можеше да върне само едно състояние, докато в недетерминираната версия може да върне няколко състояния — ако за един символ са дефинирани няколко прехода. Тъй като трябва да определим и ε-преходите, означаваме множеството Σ ∪ {ε} като множеството Σ_ε, т.е. Σ_ε = Σ ∪ {ε}. Функцията δ следователно определяме като

$δ : Q \times Σ_{ε} \to 2^{Q}$

Това 2^Q означава степенното множество, множеството на всички подмножества на множеството Q. Формализирането на изчислението е много подобно на това при крайните автомати. Конфигурацията на автомата е отново двойка ⟨q, w⟩ ∈ Q × Σ^∗. Стъпката на изчислението ↦ е релация върху множеството на конфигурациите, такава че

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

тогава и само тогава, когато q_j ∈ δ(q_i, w₀). В това условие беше най-голямата разлика. В детерминираните автомати това условие записвахме като q_j = δ(q_i, w₀), защото функцията δ връщаше винаги едно състояние. Недетерминираната версия на преходната функция връща множество от състояния, затова там стои символът ∈. Рефлексивното и транзитивното затваряне на релацията отново ще означаваме с ↦ ^∗. Казваме, че автоматът приема думата w тогава и само тогава, когато съществува q_f ∈ F, такова че

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Източници

Глави: Краен автомат, Тотален автомат, Недетерминиран краен автомат, Симулация на недетерминиран автомат, Преобразуване на НКА в ДКА

« Предишна: Тотален автомат

Следваща: Симулация на недетерминиран автомат »