Розкладання автоматів і автомат, що розщеплюється - Студопедія
Якщо Hk(Si) = Hk-1(Si). то Hk+u(Si) = Hk-l(Si) для всіх невід'ємних цілих u і, отже, Hk-l(Si) становить безліч всіх станів, пов'язаних з Siланцюгом ребер[12] будь-якої довжини. Визначення цієї множини, що позначається просто H(Si), може бути описано за допомогою наступного алгоритму.
За допомогою аргументів, аналогічних тим, які були використані для алгоритму 2.1, можна показати, що алгоритм 2.2 вимагає не більше n - r ітерацій пункту 2, де n - потужність множини станів S автомата М, а r - потужність множини Si. Таблиця 2.6 ілюструє застосування цього алгоритму автомата ЛЗ, зображеного на рис. 2.5 для Si= , H(1, 4) = .
Автомат або підавтомат, який містить два або більше ізольованих підавтоматів, будемо називати розкладним. Раніше згадувалося, що якщо Siмістить єдиний стан σi, то H(σi) становить безліч всіх станів, з'єднаних з σiза допомогою ланцюгів ребер будь-якої довжини. Отже, якщо H(σi) ≠ S, то H(σi) становить нерозкладний ізольований підавтомат автомата М. Якщо H(σi) = S, то можна зробити висновок, що автомат М нерозкладний. Тепер можна описати метод отримання максимального розкладання автомата, тобто метод розкладання автомата на максимально можливу кількість ізольованих
Алгоритм 2.3. Визначення максимального розкладання заданого автомата М із безліччю станів S.
(1) Нехай S1=S. Покладаємоk=1. (2) Вибираємо будь-який стан Sk, наприклад σik, і визначаємо H(σik). Безліч H(σik) – безліч станівk-го ізольованого підавтомата автоматаM. (3) (а)Якщо H(σi1) H(σi2) . H(σik) ≠ S, то вважаємо, що Sk+1містить стан множини S, які не містяться H(σi1) H(σi2) . H(σik). Збільшуємо k на одиницю та повертаємося до (2). (б) Якщо H(σi1) H(σi2) . H(σik) = S, то підавтомати, що визначаються множинами H(σi1), H(σi2), H(σik) представляють максимальне розкладання автомата M. Зокрема, якщо H(σi1) = S, то автомат M нерозкладний.
Алгоритм 2.3, звичайно, не є обов'язковим, якщо автомат заданий у вигляді графа. Однак він потрібен, коли максимальне розкладання треба провести без використання графа, наприклад, за допомогою цифрової обчислювальної машини.
Два або більше автоматів називаються порівнянними, якщо вони мають однакові вхідні алфавіти. Нехай М1, M2, . MN- порівняльні автомати, що представляютьNрізних систем, і нехайM- автомат, який складається із ізольованих підавтоматів М1, M2, . MN. М називається розщеплюваним автоматом автоматів М1, M2, . MNі позначається так: ∆( М1, M2, . MN). За заданих таблицях переходів М1, M2, . MNтаблиця переходів ∆( М1, M2, . MN) може бути побудована наступним чином. (1) Переозначимо стани автомата Mi, якщо необхідно, так, щоб не було в тому самому автоматі або в двох різних автоматах двох станів, позначених однаково. (2) Запишемо рядки всіх N таблиць послідовно в одну загальну таблицю; ця таблиця є таблицею переходів автомата ∆( М1, M2, . MN). Якщо Miвизначені графами, то граф переходів ∆( М1, M2, . MN) є просто об'єднанням усіх окремих графів, стан яких може бути перенумерований у разі потреби відповідно до зазначеного вищим правилом.
Зрозуміло, що автомат, що розщеплюється ∆( М1, M2, . MN) і, отже, кожен автомат, що міститьряд підавтоматів, визначених як і, як М1, M2, . MN, може розглядатися як «система», яка є автоматом M1 або
автомат М2 або автомат MN. Ця інтерпретація ґрунтується на тому факті, що якщо ∆( М1, M2, . MN) знаходиться в стані σu, що належить підавтомату Mi, то ∆ (М1, M2, . MN) ніколи не може перейти в будь-який стан підавтомату Mj, де j ≠ i, так як Miі Mj- два ізольованих підавтомати. Поведінка автомата ∆( М1, M2, . MN), що знаходиться в стані σu, збігається тому з поведінкою автомата Mi, що знаходиться в стані σu. Отже, автомат ∆( М1, M2, . MN) може бути представлений автоматом М1, або автоматом M2 або автоматом MN, залежно від початкового стану.
Як приклад рис. 2.6 та таблиця 2.7 представляють автомат A4, а рис. 2.7 та таблиця 2.8-автомат A5. Автомат, що розщеплюється, складений з автоматів A4 і A5, ∆ (A4, A5), представлений на рис. 2.8 та у таблиці 2.9.
2.8. Матриця переходів[13]
Матриці переходів є математичною копією графів переходів; вони дозволяють формалізувати ряд операцій, які у графі переходів може бути виконані візуально. Матриці переходів тому мають переваги у тих випадках, коли ці операції не можуть бути виконані людиною-дослідником і, отже, не можуть бути виконані візуально або коли графік переходів настільки складний, що використання візуальної методики марно.
Для автомата М, має n станів, матриця переходів складається з n. рядків та n стовпців і позначається [М]. Нехай 1, σ2, . σn>-множина станів автомата М і нехай позначає дугу графа переходів автомата М,спрямовану від σiдо σj. Елемент (i,j) (тобто вміст клітини, розташованої на перетині i-го рядка і j-го стовпця матриці [М] позначається еijі визначається так:
Для ясності зазвичай позначенняk-го стану σkприписують k-му рядку і k-му стовпцю і називають їх «рядок σk» і «стовпець σk» відповідно. Вираз (2.12) зображує матрицю переходів автомата А1, заданого як графа на рис. 2.2.
Якщо р — потужність вхідного алфавіту автомата М, кожен рядок в [М] повинна містити точно р пар вхід-вихід, причому кожна пара має вхідний символ, відмінний від вхідного символу будь-якої іншої пари. Дуги, що входять у стан σk, є недіагональними елементами[14] стовпця σk; дуги, що виходять зі стану σk, є недіагональними елементами рядка σk; петля стану σkпредставляється діагональним елементом у рядку σkабо
стовпці σk. Отже, якщо σk— стан, що переходить, то всі недіагональні елементи в стовпці σk(але не в рядку σk) дорівнюють нулю; якщо σk-тупиковий стан, то всі недіагональні елементи в рядку σk(але не в стовпці σk) дорівнюють нулю; якщо σk— ізольований стан, то всі недіагональні елементи в рядку σkі стовпці σkдорівнюють нулю.
Якщо Si= i1, σi2, . σir>, то визначена в § 2.6 безліч G1(Si) являє собою об'єднання Siі позначень стовпців, у яких елементи, що належать рядкам σi1, σi2, . σir, не дорівнюють нулю. Визначена в § 2.7 множина HI(Si) являє собою об'єднання Siпозначень стовпців, в яких елементи, що належатьрядкам σi1, σi2, . σir, не рівні нулю, та позначень рядків, у яких елементи, що належать стовпцям σi1, σi2, . σir, не дорівнюють нулю. Наприклад, з матриці [Al] ясно видно, що з автомата A1 G1(l, 2) = і Н1(4, 5)=. Отже, ясно, що матриця переходів є зручним інструментом виконання алгоритмів 2.1, 2.2 і 2.3.
Для того щоб визначити, чи становить безліч S(σi1, σi2, .ir) минущий, тупиковий або ізольований підавтомат автомата М, треба рядки та стовпці матриці [М] переставити так, щоб рядки та стовпці σi1, σi2, . σir зайняли сусідні положення, починаючи з першого рядка та першого стовпця відповідно. Як показано в (2.13), ця перестановка ділить матрицю [М] на чотири підматриці [М11], [М12], [M21], [М22], причому рядками та стовпцями [М11] є рядки та стовпці σi1, σi2, . σir
Позначаючи матрицю, всі елементи якої дорівнюють нулю, через [0], можна дійти невтішного висновку, що Siстановить минущий підавтомат, якщо [M21] = [0], а [М12] ≠ 0, тупиковий підавтомат, якщо [М12] = [0], а [M21] ≠ 0, та ізольований підавтомат, якщо [М12] = [М21] = [0]. (2.14) представлена матриця переходів автомата A3, зображеного на рис. 2.5, в якій рядки та стовпці переставлені так, щоб виділити тупиковий підавтомат, минущий підавтомат та ізольований підавтомат.
Якщо Si становить тупиковий або ізольований підавтомат, то [M12] = [0] і, отже, кожен рядок в [М11] містить все р пар вхід-вихід, де р потужність вхідного алфавіту. Видаливши [M12], [M21] і [М22] з [М], отримаємо матрицю [М11] розміром r r, яку можна трактувати як матрицю, що представляє незалежний автомат М11 з станами r,має той самий вхідний алфавіт, як і М. Звідси випливає той самий висновок, яке було отримано в § 2.6: якщо автомат перебуває у стані, що належить тупиковому чи ізольованому підавтомату, всі стани, які належать цьому підавтомату, і всі дуги, исходящие з цих станів можуть бути виключені.
Чи не знайшли те, що шукали? Скористайтеся пошуком: