Краен автомат

Краен автомат (на английски finite state machine или finite automaton) е изчислителен модел на примитивен компютър, който се състои от няколко състояния и няколко прехода и който може да приеме или да отхвърли подадена му дума.

Пример

Неформално ще опишем краен автомат с помощта на диаграма на състоянията:

Автоматът се състои от състояния, на фигурата те са трите кръгли състояния q₀, q₁ и q₂. Между тези състояния има преходи, това са стрелките. В автомата трябва да има и начално състояние, това е състоянието q₀. Началното състояние често се изобразява така, че към него сочи стрелка, която не излиза от никое състояние. Освен това в автомата обикновено има крайно състояние, него изобразяваме с двойна линия, така че на фигурата това е състоянието q₂.

Така построеният автомат приема някои думи. Въвеждаме в автомата някакви думи и той се опитва да ги приеме. Ако ги приеме, автоматът отговаря ДА, ако не ги приеме, отговаря НЕ. Нашият автомат се опитва да приема думи, съставени от буквите „a, b, c“, така че можем да опитаме да приемем думата „abbc“.

Започваме от началното състояние q₀ и на входа е думата „abbc“. Нататък следваме стрелките.

Обхождаме думата по обичайния начин отляво надясно, т.е. първо вземаме символа „a“. Стрелката за вход „a“ води към състоянието q₁, така че преминаваме там и махаме символа „a“ от думата. На входа остава думата „bbc“:

Стрелката за вход „b“ сочи обратно към възела q₁. Отново махаме първата буква и на входа остава думата „bc“. Пак оставаме в състоянието q₁. Накрая на входа има думата „c“. От състоянието q₁ стрелката за вход „c“ ни праща в състоянието q₂.

Вече сме изчерпали всички букви на входната дума и сме в състоянието q₂, което е крайно. Този краен автомат следователно приема думата „abbc“.

Ако накрая не бяхме в приемащо състояние, автоматът нямаше да приеме думата. Автоматът нямаше да приеме думата и ако в някое състояние нямахме накъде да продължим. Например за вход „ab“ бихме стигнали до състоянието q₁ и там бихме спрели — автоматът не приема такава дума. Ако изпробваме думата „aabbc“, отново нямаме късмет, защото от състоянието q₁ не води стрелка за буквата „a“.

Крайният автомат следователно служи за разпознаване на някакво множество от думи. На практика бихме могли да използваме автомат например за да проверим дали дадена входна дума е валиден имейл.

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

Предишната интуитивна представа за това какво е краен автомат трябва да формализираме, за да можем по-нататък да работим с автомати по-добре.

Казваме, че краен (детерминиран) автомат е петорка ⟨Q, Σ, δ, q₀, F⟩, където

• Q е крайно множество от състояния,
• Σ (главна сигма) е азбука (крайно множество от символи/букви),
• δ: Q × Σ ⟶ Q е преходна функция,
• q₀ ∈ Q е началното състояние,
• F ⊆ Q е множеството на крайните (приемащите) състояния.

Като се върнем към предишния автомат,

можем да кажем, че в множеството на състоянията Q има три състояния Q = {q₀, q₁, q₂}. Азбуката Σ съдържа буквите, от които можем да съставяме думи, които автоматът след това ще приема или отхвърля. Тук това вероятно е азбуката Σ= {a, b, c}, но може да е и произволно надмножество на тази. Началното състояние q₀ е състоянието q₀, при него нищо не се променя. Множеството на крайните състояния в този автомат има само едно състояние F = {q₂}.

Под преходна функция разбираме трите стрелки с буквите. Ако записът δ: Q × Σ ⟶ Q те обърква, той просто означава, че δ е функция (може би по-добре изображение), която приема два параметъра: състояние от Q и буква от Σ. След като извикаме функцията, тя връща ново състояние. Нашата преходна функция бихме могли да зададем с таблица така:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Ако извикаме δ(q₁, c), прилагаме третия ред и функцията отговаря със състоянието q₂ — също като диаграмата. Ако сме в състоянието q₁ и на входа е буквата „c“, стигаме до състоянието q₂. Преди да определим формално какво означава, че автоматът приема дадена дума, ще се опрем на интуитивното разбиране на това понятие и ще разгледаме още няколко примера.

Още примери

1. Построй автомат, който работи над двоичната азбука, т.е. Σ= {0, 1}, и приема само думи, които завършват с единица. Например приема думите 1, 01, 000001, 0101011.

   

   Нашият автомат има две състояния — начално q₀ и крайно q₁. Винаги когато на входа има цифрата 1, преминаваме в крайното състояние q₁ и оставаме в него. Обратно, ако на входа е цифрата 0, преминаваме в неприемащото състояние q₀ и също оставаме в него.

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

   

   Още в първата стъпка автоматът се разделя на два „подавтомата“. Ако думата започва с нула, автоматът влиза в лявата част и вече остава там, ако започва с единица, преминава в дясната част. След това е стандартно: ако сме в лявата част и на входа е 1, преминаваме в крайното състояние и оставаме там. Ако на входа е 0, преминаваме в състоянието q₁, което не е крайно.

   За разлика от предишните автомати, този автомат има няколко крайни състояния, т.е. F = {q₃, q₄}.

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

   

   Този автомат е интересен поради две причини: първата е, че приема празната дума. Можем да опитаме да въведем празната дума в автомата и той я приема, ако началното състояние е и крайно, което при този автомат е изпълнено. Тъй като празната дума е дума, която не съдържа две нули последователно, това е точно както трябва. Другата особеност е, че при този автомат всички състояния са крайни. Единственият случай, в който автоматът не би приел дума, е, ако от някое състояние не води никакъв преход. Това се случва в състоянието q₁, което няма преход за 0, защото тогава думата би съдържала две нули последователно.

4. Построй автомат над азбуката {-,+,.,0,1,…,9}, който приема само думи, които представляват число. Това означава или цяло число, например 2, 548, 98263, или десетично число, например 5584.48, 3.14 (с точка, както в програмирането), и двете във вариант за отрицателно число със знак минус -2, -548, -3.14 и с изрично записан плюс, т.е. +2, +548, +3.14. Освен това трябва да можем да запишем числото 0.123 само като .123 (без нулата в началото), включително с двата знака. Въвеждаме си помощно означение: вместо да изписваме десет прехода за десетте цифри, ще използваме символа N.

   

5. Построй автомат над двоичната азбука, който приема само думи от вида 0ⁿ1ⁿ, което означава, че думите имат в началото определен брой нули, а след тях следва същият брой единици. Примери за такива думи са 0011, 00001111, 01.

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

Формализиране на изчислението на автомата

Вече определихме формално самия краен автомат. По-нататък трябва да определим и какво всъщност прави такъв автомат, т.е. определяме изчислението на автомата.

Конфигурация на автомата: Казваме, че двойката ⟨q, w⟩ ∈ Q × Σ^∗ е конфигурация на автомата, където q е текущото състояние, в което се намира автоматът, а w е все още непрочетената част от думата. Σ^∗ означава затварянето на азбуката Σ, множеството от всички думи, които могат да се съставят от буквите на азбуката Σ. Част от затварянето е и празната дума, която означаваме с ε.

Ако имаме автомата ⟨Q, Σ, δ, q₀, F⟩ и се опитваме да приемем думата w, автоматът се намира в началната конфигурация ⟨q₀, w⟩. Ако се върнем към автомата

и искаме да приемем думата w = abbc, началната конфигурация ще е ⟨q₀, abbc⟩.

Стъпка на изчислението определяме като релация ↦ между множествата (Q × Σ^∗) × (Q × Σ^∗), т.е. между конфигурациите на автомата. Нека w = w₀w₁… w_n представлява все още непрочетената част от думата w. Тогава казваме, че двойките ⟨q₁, w₀w₁… w_n⟩ и ⟨q₂, w₁… w_n⟩ са в релацията ↦, което записваме като

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

тогава и само тогава, когато δ(q₁, w₀) = q₂. Като се върнем към нашия пример, началната конфигурация е ⟨q₀, abbc⟩. От диаграмата виждаме, че за вход „a“ можем да преминем в състоянието q₁. Така можем да запишем

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

защото е в сила δ(q₀, a) = q₁. По този начин извършихме една стъпка на изчислението — погледнахме в кое състояние трябва да отидем за дадения вход (= първата буква на все още непрочетената част от думата), преминахме там и махнахме първата буква от непрочетената част на думата. Така получихме нова конфигурация.

Рефлексивно и транзитивно затваряне на релацията стъпка на изчислението означаваме с ↦ ^∗. Ако напишем K₁ ↦ ^∗ K₂, където K₁, K₂ са конфигурации на автомата, това означава, че от конфигурацията K₁ можем да стигнем до конфигурацията K₂ чрез няколко стъпки на изчислението, или иначе казано, съществува крайна редица от конфигурации, такава че:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Например в нашия автомат е в сила ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, защото след две стъпки на изчислението остава думата „bc“ и оставаме в състоянието q₁. Т.е. съществува тази редица от конфигурации:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Автоматът приема думата w тогава и само тогава, когато съществува q_f ∈ F, такова че $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Това означава, че автоматът приема думата w тогава и само тогава, когато съществува редица от стъпки на изчислението, такава че в края на тази редица сме прочели цялата дума и се намираме в крайно състояние на автомата. Това, че сме прочели цялата дума, е изразено с това, че в конфигурацията на мястото на думата стои ε, т.е. празната дума. Нашият автомат приема думата abbc, защото съществува тази редица от конфигурации:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

и състоянието q₂ е крайно състояние, q₂ ∈ F.

Език, приеман от автомата, е множеството от всички думи, които автоматът приема. Езика на автомата A ще означаваме с L(A). Следователно L(A) ⊆ Σ^∗ и

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ приема думата }w\}$$

Регулярен език е такъв език, който се приема от някакъв краен автомат.

Два крайни автомата са еквивалентни, ако приемат един и същ език. Т.е. автоматите A₁ и A₂ са еквивалентни, ако L(A₁) = L(A₂).

Източници

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools