Граф переходів кінцевого автомата

КА часто представляють у вигляді діаграми або графа переходів автомата. Граф переходів КА - це спрямований граф, вершини якого позначені сим ¬ волами станів КА, і в якому є дуга (p, q) p.qeQ. позначений символом aeV, якщо в КА визначена 5 (а, р) і qe8 (a, p).Початковий і кінцевий стани автомата на графі станів позначаються спеціальним чином (в даному посо ¬ біі початковий стан - додаткової пунктирною лінією, кінцеве со ¬ стояння - додаткової суцільною лінією).

Розглянемо кінцевий автомат: M ({HABS}. {Ab}, 5.H. {S}); 5: 8 (Hb) = B. 8 (В.а) = А, 8 (A, b) = {B, S}. На рис. 3.2 наведено приклад графа станів для цього КА.

Рис. 3.2. Граф переходів недетермінірованного кінцевого автомата

Для моделювання роботи КА його зручно привести до повністю певного виду, щоб виключити ситуації, з яких немає переходів по вхідним символам. Для цього в КА додають ще один стан, який можна умовно назвати «помилка».На цей стан замикають всі невизначені переходи, а все пере ¬ ходи з самого стану «помилка» замикають на нього ж. Якщо перетворити подібним чином розглянутий вище автомат М, то отри ¬ чім повністю певний автомат: M ({H, AB, ES}. {Ab} .5. Н. {S}): 8: 8 (Н, а) = Е , 8 (Hb) = B. 8 (В.а)-А, 5 (Bb) = E. 8 (А, а) = {Е}. 8 (Ab) = {BS}. 8 (Е, а) = {Е}. 8 (Eb) = {E}. 5 (Sa) = {E}. 8 (Sb) = {E}. Стан E якраз відповідає стану «помилка». Граф переходів цього КА представлений на рис. 3.3.

Рис.3.3. Граф переходів повністю певного медетермінірованого кінцевого автомата

Детерміновані і недетерміновані кінцеві автомати

Визначення детермінованого кінцевого автомата

Кінцевий автомат M (Q_, V, 5, q0, F) називають детермінованим кінцевим авто ¬ матом (ДКА), якщо в кожному з його станів 'для будь-якого вхідного символу функція переходу містить не більше одного стану VaeV, VqeQj або 5 (a, q) - {г} reft або 5 (a, q) - 0.

В іншому випадку кінцевий автомат називають Недетермінірованним.

З цього визначення видно, що автомати, представлені раніше на рис. 3.2 і

3.3 Є недетерміновані ка.

ДКА може бути заданий у вигляді п'ятірки:

М (й V, 8, q0, F),

де

Q, - кінцеве безліч станів автомата;V - кінцева множина допустимих вхідних символів, 5 - функція переходів, що відображає V * Q в безліч Q; 5 (a, q) - г, аеV, q, reOj q0 - початковий стан автомата Q, qoeOj F - непорожня множина кінцевих станів автомата , FQQ, F * 0.Якщо функція переходів ДКА визначена для кожного стану автомата, то авто ¬ мат називається повністю певним ДКА: VaeV * VqeO; або 3S (a, q) - г, r <sQ, Доказано, что для любого КА можно построить эквивалентный ему ДКА.Моду ¬ ліровать роботу ДКА істотно простіше, ніж роботу довільної КА, поет ¬ му довільний КА прагнуть перетворити на ДКА. При побудові комп ¬ лятори найчастіше використовують повністю певний ДКА.

Перетворення кінцевого автомата до детермінованому увазі

Алгоритм перетворення довільного КА M (Q> V, 6, q0, F) в еквівалентну їй ДКА M '(Q,,, V, 5', q, 0, F) полягає в наступному:

1. Безліч станів Q, 'автомата М' будується з комбінацій всіх перебуваючи ¬ ний безлічі О, автомата М.Якщо qi, q2, -, q ", п> 0 - стану автомата М, V0 <i <nq, eQ, то всього буде 2" -1 станів автомата М '. Позначимо їх так: [q "q2 qj, 0 < m <п.

2. Функція переходів 5 'автомата М' будується так: 5, (a, [qi, q2 ,..., qm]) - [r "r2 ,..., rk], де V0 <i ї m 30 <j S k так, що 5 (а, ^) - г}.

3.Позначимо q'0 - [qj.

4. Нехай f "f2 ,..., fi, 1> 0 - кінцеві стани автомата М, V0 <i <1 ^ eF, тоді безліч кінцевих станів F автомата М 'будується з усіх станів, які мають вигляд [..., fj, ...], f, eF.

Доведено, що описаний вище алгоритм будує ДКА, еквівалентний задано ¬ му безпідставного КА.

Після побудови з нового ДКА необхідно видалити всі недосяжні со ¬ стояння.

Стан qeQ.в КА M (QV, 5, q0, F) називається недосяжним, якщо ні при ка ¬ кой вхідний ланцюжку сої V4 неможливий перехід автомата з початкового стану ¬ ня q0 в стан q. Інакше стан називається досяжним.Для роботи алгоритму видалення недосяжних станів використовуються дві множини: безліч досяжних станів R і безліч поточних актив ¬ них станів на кожному кроці алгоритму Р,. Результатом роботи алгоритму яв ¬ ляється повне безліч досяжних станів R.Розглянемо роботу алго ¬ ритму по кроках:

1. R: - {q0}; i: - 0; Р0: - {q0}.

2. Р1 +1: - 0.

3. VaeV, VqeP,: Р, +1: - P, +1 u8 (a, q).

4. Якщо Р, +1 - R = 0, то виконання алгоритму закінчене, інакше R: - RuPl +1, i; = i + 1 і перейти до кроку 3.

Після виконання даного алгоритму з КА можна виключити всі стани, що не входять в побудоване безліч R.,

Розглянемо роботу алгоритму перетворення довільного КА в ДКА на прикладі автомата М ({Н, А, В.S}. {А.Ь}, 5, H, {S}): 8: 5 (H, b) = B, 8 (В.А)-А. 8 (Ab) = {B, S}.Видно,що це недетермінірованний КА (зі стану А можливі два різних ¬ них переходу по символу Ь). Граф переходів для цього автомата був зображений вище на рис. 3.2.

Побудуємо безліч станів еквівалентного ДКА:

Q'-{[Н]. [А]. [В]. [S]. [НА], [НВ], [HS], [АВ], [AS]. [BS]. [НАВ]. [HAS ]. [HBS]. [ABS],HABS]}.

Побудуємо функцію переходів еквівалентного ДКА:

8 '([Н]. Ь) - [В] 8' ([A]. BMBS]

б '([В]. а) - [А]

5 '([HA], b) = [BS]

б '([НВ]. а) - [А]

8 '([НВ]. Ь) - [В]

6 '([HS]. B) = [B]

8ч [АВ]. А) - [А]

S '([AB]. B) = [BS]

6 '([AS]. B) = [BS]

S '([BS]. A) = [A]

6 '([НАВ]. А) = [А]

6 '([HAB]. B) = [BS]

8 '([HAS]. B) - [BS]

8 '([HBS]. B) - [B]

6 '([HBS]. A) = [A]

8 '([ABS]. B) - [BS]

6 '([ABS]. A) = [A]

8 '([HABS]. AKA]

8 '([HABS]. B) - [BS]

Початковий стан еквівалентного ДКА: qO '= [Н]

Безліч кінцевих станів еквівалентного ДКА: F '- {[S], [HS], [AS], [BS]. [HAS]. [HBS]. [ABS], [HABS]}

Після побудови ДКА виключимо недосяжні стану.Безліч дости ¬ жімих станів ДКА буде наступним: R - {[Н]. [В]. [А]. [BS]}. У підсумку, исклю ¬ чив все недосяжні стану, отримаємо ДКА:

M4 {[H]. [B], [A]. [BS]}. {A, b}. [H]. {[BS]}).

8 ([Н]. Ь) - [В]. 8 ([В]. А) - [А]. 8 ([A]. B) - [BS]. 8 ([BS]. A) - [A].

Нічого не змінюючи, переобозначив стану ДКА. Отримаємо:

M '({HBA, S}, {ab}. H, {S}),

8 (Hb)-B. S (B, a) = A. 8 (Ab)-S. 8 (Sa)-A.

Граф переходів отриманого ДКА зображений на рис. 3.4.

Рис. 3.4. Граф переходів детермінованого кінцевого автомата

Цей автомат можна перетворити до повністю певного виду. Полу ¬ чім граф станів, зображений на рис. 3.5 (стан Е - це стан «помилка»).

Мінімізація кінцевих автоматів

Багато КА можна мінімізувати. Мінімізація КА полягає в побудові ¬ нии еквівалентного КА з меншим числом станів. У процесі мінімізації необхідно побудувати автомат з мінімально можливим числом станів, ек ¬ вівалентний даному КА.

Для мінімізації автомата використовується алгоритм побудови еквівалент ¬ них станів КА.Два різних стану в кінцевому автоматі M (QV, 5, q0, F) qeQ і q'eQ називаються п-еквівалентними (n-нерозрізненими), п> Про neNu {0}, якщо, перебуваючи в одному з цих станів і отримавши на вхід яку ланцюжок символів з: coeV * | зі | <п, автомат може перейти в один і той же безліч кінцевих станів.Очевидно, що О-еквівалентними станами автомата M (QV, 5, q0, F) є дві безлічі його станів: F і QF. Безлічі еквівалентних станів автомата називають класами еквівалентності, а всю їх сукупність - безліччю класів еквівалентності R (n), причому R (0) - {FQ-F}.

Розглянемо роботу алгоритму побудови еквівалентних станів по кроках:

1. На першому кроці п: = 0, будуємо R (0).

2. На другому кроці n: = n + 1, будуємо R (n) на основі R (nl): R (n) = {r, (n): {q4eQ: VaeV 5 (а, я, л) сг, (п -1)} VijeN}.To є в класи еквівалентності на кроці п входять ті стани, які за однаковими символам переходять в п-1 екві ¬ валентні стани.

3. Якщо R (n) = R (nl), то робота алгоритму закінчена, інакше необхідно вер ¬ нуться до кроку 2.

Доведено, що алгоритм побудови безлічі класів еквівалентності за ¬ вершиться максимум для n = ш-2,де m - загальна кількість станів авто ¬ мата.

Алгоритм мінімізації КА полягає в наступному:

1. З автомата виключаються всі недосяжні стану.

2. Будуються класи еквівалентності автомата.

3.Класи еквівалентності станів вихідного КА стають станами результуючого мінімізованого КА.

4. Функція переходів результуючого КА очевидним чином будується на основі функції переходів вихідного КА.

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

Розглянемо приклад: заданий автомат M ({ABCD, EFG}. {0.1} .5. A. {D, E}). 5 (А.0) = {У}. 5 (А.1) = {С}. 5 (B.1) = {D}. 5 (С.1) - {Е}. 5 (D.0) = {C}. 5 (D.1) - {E}. 5 (Е.0) = {У}, 5 (E.1) - {D}. 5 (F, 0) = {D}, 5 (F.1) = {G}. 5 (G, 0) = {F}. 5 (G.1) = {F}; необхідно побудувати еквівалент ¬ ний йому мінімальний КА.

Граф переходів цього автомата наведено на рис. 3.6.

Рис. 3.6. Граф переходів кінцевого автомата до його мінімізації

Стани F і G є недосяжними, вони будуть виключені на першому кроці алгоритму. Побудуємо класи еквівалентності автомата:

R (0) = {{ABC}. {D, E}}. п = 0; R (1) = {{A}. {BC}. {DE}}. п-1: R (2) = {{A}. {BC}. {DE}}, п-2.

Позначимо відповідним чином стану отриманого мінімального КА і побудуємо автомат: М ({А.ВС.DE}. {0.1} .5 '. A. {DE}). 5 '(А.0) = {ВС). 5 '(А. 1) - {НД}. 5 '(BC, 1) = {DE}. 5 '(DE, 0) = {BC}, 5' (DE, 1) = {DE}. Граф переходів мінімального КА наведено на рис. 3.7.

Рис. 3.7. Граф переходів кінцевого автомата після його мінімізації

Мінімізація кінцевих автоматів дозволяє при побудові розпізнавачів отримати автомат з мінімально можливим числом станів і, тим самим, в подальшим спростити функціонування розпізнавача.

Регулярні множини та регулярні вирази Визначення регулярного безлічі

Визначимо над множинами ланцюжків символів з алфавіту V операції конка ¬ тенаціі і ітерації наступним чином: PQ-конкатенація PeV * і QeV *: PQ-{pq VpeP, VqeQ}; P * - ітерація PeV *: P * - {p * VpeP} .

Тоді для алфавіту V регулярні безлічі визначаються рекурсивно:

1. 0 - регулярне безліч;

2. {X} - регулярне безліч;

3. {А} - регулярне безліч VaeV;

4. якщо Р і Q - довільні регулярні безлічі, то безлічі PuQ, PQ, і Р * також є регулярними множинами;

5.ніщо інше не є регулярним безліччю.

Фактично регулярні безлічі - це безлічі ланцюжків символів над за ¬ даними алфавітом, побудовані певним чином (з використанням опе ¬ рацій об'єднання,конкатенації і ітерації). Всі регулярні мови є регулярні множини.