WikiZero - Кінцевий автомат

1. Спеціалізовані мови програмування [ правити | правити код ]
2. Розробка моделей з використанням кінцевих автоматів [ правити | правити код ]
3. Що може «робити» кінцевий автомат і послідовних машина? [ правити | правити код ]

open wikipedia design.

Кінцевий автомат - абстрактний автомат , Число можливих внутрішніх станів якого звичайно .

Існують різні способи завдання алгоритму функціонування кінцевого автомата. Наприклад, кінцевий автомат може бути заданий у вигляді впорядкованої п'ятірки елементів деяких множин :

M = (V, Q, q 0, F, δ) {\ displaystyle M = (V, Q, q_ {0}, F, \ delta)} ,

де

• V {\ displaystyle V} - вхідний алфавіт (кінцеве безліч вхідних символів), з якого формуються вхідні слова, які сприймаються кінцевим автоматом;
• Q {\ displaystyle Q} - безліч внутрішніх станів;
• q 0 {\ displaystyle q_ {0}} - початковий стан (q 0 ∈ Q) {\ displaystyle (q_ {0} \ in Q)} ;
• F {\ displaystyle F} - безліч заключних, або кінцевих станів (F ⊂ Q) {\ displaystyle (F \ subset Q)} ;
• δ {\ displaystyle \ delta} - функція переходів, певна як відображення δ: Q × (V ∪ {ε}) → Q {\ displaystyle \ delta \ colon Q \ times (V \ cup \ {\ varepsilon \}) \ rightarrow Q} , Таке, що δ (q, a) = {r: q → ar} {\ displaystyle \ delta (q, a) = \ {r \ colon q \, \, {\ underset {a} {\ to}} \, \, r \}} , Тобто значення функції переходів на впорядкованої парі (стан, вхідний символ або порожній ланцюжок) є безліч всіх станів, в які з даного стану можливий перехід з даного вхідного символу або порожній ланцюжку (ε).

Прийнято вважати, що кінцевий автомат починає роботу в стані q 0 {\ displaystyle q_ {0}} , Послідовно зчитуючи по одному символу вхідного слова (ланцюжки вхідних символів). Лічені символ переводить автомат в новий стан відповідно до функції переходів.

Читаючи вхідні ланцюжок символів x {\ displaystyle x} і роблячи переходи зі стану в стан, автомат після прочитання останнього символу вхідного слова виявиться в деякому стані q '{\ displaystyle q'} .

Якщо цей стан є заключним, то кажуть, що автомат допустив слово x {\ displaystyle x} .

Кінцеві автомати широко використовуються на практиці, наприклад, в синтаксичних і лексичних аналізаторах , тестуванні програмного забезпечення на основі моделей .

1. діаграма станів (або іноді граф переходів) - графічне представлення безлічі станів і функції переходів. Являє собою розмічений орієнтований граф , Вершини якого - стану КА, дуги - переходи з одного стану в інший, а мітки дуг - символи, за якими здійснюється перехід з одного стану в інший. Якщо перехід зі стану q1 в q2 може бути здійснений по одному з декількох символів, то всі вони повинні бути надписані над дугою діаграми.
2. Таблиця переходів - табличне представлення функції δ. Зазвичай в такій таблиці кожному рядку відповідає один стан, а одну - один допустимий вхідний символ. В осередку на перетині рядка і стовпця записується стан, в яке повинен перейти автомат, якщо в даному стані він вважав даний вхідний символ.

Кінцеві автомати підрозділяються на детерміновані і недетерміновані.

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

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

• Недетермінований автомат з порожніми переходами

• Недетермінований автомат з переходами з одного стану поміченими одним і тим же символом

Якщо розглянути випадок, коли автомат заданий наступним чином: M = (V, Q, S, F, δ) {\ displaystyle M = (V, Q, S, F, \ delta)} , Де S {\ displaystyle S} - безліч початкових станів автомата, таке, що S ⊆ V {\ displaystyle S \ subseteq V} , То з'являється третя ознака недетермінованости - наявність декількох початкових (стартових) станів у автомата M {\ displaystyle M} .

Теорема про детермінізації стверджує, що для будь-якого кінцевого автомата може бути побудований еквівалентний йому детермінований кінцевий автомат (два кінцевих автомата називають еквівалентними, якщо їх мови збігаються). Однак оскільки кількість станів в еквівалентному ДКА в гіршому випадку зростає експоненціально з ростом кількості станів вихідного НКА, на практиці подібна детермінізації не завжди можлива. Крім того, кінцеві автомати з виходом в загальному випадку не піддаються детермінізації.

В силу останніх двох зауважень, незважаючи на велику складність недетермінірованних кінцевих автоматів, для завдань, пов'язаних з обробкою тексту, переважно застосовуються саме НКА.

Для кінцевого автомата можна визначити мову (безліч слів) в алфавіті V {\ displaystyle V} , Який він допускає - так називаються слова, читання яких переводить автомат з початкового стану в одне із заключних станів.

теорема Кліні стверджує, що мова є регулярним тоді і тільки тоді, коли він допускається деяким кінцевим автоматом, використовуваним в цій мові.

Спеціалізовані мови програмування [ правити | правити код ]

В SFC програма описується в вигляді схематичної послідовності кроків, об'єднаних переходами.

Розробка моделей з використанням кінцевих автоматів [ правити | правити код ]

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

Що може «робити» кінцевий автомат і послідовних машина? [ правити | правити код ]

Відповідь дається в різних термінах залежно від того, чи є автомат (відповідно П-машина) автономним чи ні [1] . Автономний кінцевий автомат, починаючи з деякого такту, може лише генерувати періодичну послідовність станів х (відповідно П-машина - послідовність вихідних символів y). Якщо ця послідовність складається лише з одного символу, то це означає, що за кінцеве число тактів автомат досягає рівноважного стану. Якщо ж ця послідовність містить кілька символів, це означає, що автомат послідовно проходить стани, які відповідають цим символам, а потім робота автомата необмежено довго періодично повторюється. Більш того, як і вона була періодична послідовність станів кінцевої довжини, завжди може бути побудований автономний кінцевий автомат, який, починаючи вже з другого такту, генерує цю послідовність. Нічого іншого, крім періодичного повторення одного і того ж стану або кінцевої послідовності станів, автономний автомат «робити» не може. Однак у зв'язку з тим, що послідовне виконання заданого циклу операцій типово для багатьох галузей сучасної техніки, динамічні системи, які в прийнятній ідеалізації можна розглядати як автономний автомат, мають широке застосування.

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

Сучасним прикладом служать багато верстати-автомати, автоматичні лінії і системи автоматичного управління циклічними виробництвами. Якщо автомат не автономний, тобто стан входу змінюється від такту до такту, то відповідь на питання, що може «робити» і що не може «робити» кінцевий автомат, можна дати в різних термінах. Наприклад, відповідь можна сформулювати на мові представлення подій. Дійсно, неавтономний кінцевий автомат або послідовних машина лише перетворять вхідні послідовності символів в послідовності станів або вихідних символів, і сказати, що може і що не може «робити» кінцевий автомат, значить з'ясувати, які перетворення послідовностей можливі в кінцевому автоматі, а які неможливі. Але так як кількість станів (відповідно вихідних символів) звичайно, це питання еквівалентний такому питанню: за яких вхідних послідовностях виникає кожне з можливих станів (або кожен з вихідних символів). Цей останній питання в термінах, прийнятих в теорії кінцевих автоматів, формулюється так: які події можуть і які не можуть бути представлені в кінцевому автоматі кожним з можливих станів (або кожним з вихідних символів).

відповідь дається теоремами Кліні . Ця відповідь точний, так як теореми Кліні встановлюють необхідні і достатні умови представимости послідовності подій в автоматі, а саме: виділяються особливі безлічі послідовностей вхідних символів - регулярні безлічі . Факт появи вхідної послідовності з такого безлічі називається відповідним регулярною подією. Теореми Кліні встановлюють, що в кінцевому автоматі можуть бути представлені регулярні події та тільки вони. Таким чином, на мові представлення подій відповідь на питання, що може «робити» кінцевий автомат, дається однозначно: кінцевий автомат може представляти тільки регулярні події. Ряд важливих множин вхідних послідовностей, з якими часто доводиться мати справу на практиці, свідомо регулярні. Так, наприклад, свідомо регулярно безліч, що складається з будь-якого кінцевого числа вхідних послідовностей кінцевої довжини; безліч будь-яких періодичних вхідних послідовностей; безліч нескінченних послідовностей, яке містить задані кінцеві послідовності протягом декількох останніх тактів, і т. д.

У загальному випадку, якщо будь-яким довільним способом задано безліч вхідних послідовностей, то залишається відкритим питання про те, чи регулярно це безліч. Справа в тому, що поняття регулярного безлічі вводиться індуктивно, тобто встановлюється алгоритм побудови будь-яких регулярних множин. Однак, не існує досить ефективного способу розв'язання оберненої задачі, тобто встановлення того, чи є кожне задане безліч регулярним.

Хоча теореми Кліні і відповідають на питання про те, що може робити кінцевий автомат, але відповідають вони на це питання неефективно. Зроблено перші спроби побудови інших мов, на яких відповідь може бути дан ефективно. Ця проблема мови, яка відіграє кардинальну роль в отриманні ефективної відповіді на питання, що може і що не може «робити» кінцевий автомат, має вирішальне значення і для перших етапів синтезу автомата, тобто для відповіді на другий з сформульованих вище питань. Якщо розширити клас динамічних систем, які ми визначили термінами «кінцевий автомат» і «послідовних машина», включенням нескінченної пам'яті (моделлю нескінченної пам'яті може бути, наприклад, нескінченна стрічка для зберігання символів або нескінченне число станів), то для динамічних систем цього більш широкого класу (абстрактні системи цього класу називають машинами Тьюринга ) Відповідь на питання «що вони можуть робити?» Значно простіше - вони можуть реалізувати будь-який наперед заданий алгоритм. При цьому саме поняття алгоритму трактується в сучасній математиці як реалізація обчислення значень будь-якої рекурсивної функції . Настільки однозначний і чітку відповідь на питання «що може робити машина Тьюринга?» Дає можливість покласти поняття про машину Тьюринга в основу визначення поняття алгоритму: алгоритмом називається будь-який процес, який може бути здійснений на кінцевому автоматі, доповненому нескінченної пам'яттю, тобто алгоритмічно повних машинах , на машині Тьюринга, на машині Посту та ін.

1. ↑ Айзерман М. А., Гусєв Л. А., Розоноер Л. І., Смирнова І. М., Таль А. А. Логіка. Автомати. Алгоритми. Держ. изд. фіз.-мат. літератури 1963 556 стр.

• Бєлоусов А. І., Ткачов С. Б. Дискретна математика. - М.: МГТУ, 2006. - С. 460-587. - ISBN 5-7038-2886-4 .
• Джон Хопкрофта, Раджив Мотвани, Джеффрі Ульман. Дискретна математика. - 2-е вид. - Вільямс, 2002. - 528 с. - (Алгоритми і методи. Мистецтво програмування).
• Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теорія і реалізація мов програмування - М .: МЗ-Пресс, 2006 року, 2-е вид. - ISBN 5-94073-094-9
• Теорія автоматів / Е. А. Якубайтіс, В. О. Васюкевіч, А. Ю. Гобземіс, Н. Е. Зазнова, А. А. курми, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теорія імовірності. Математична статистика. Теоретична кібернетика. - М .: ВІНІТІ, 1976. - Т. 13. - С. 109-188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
• Застосування кінцевих автоматів для вирішення завдань автоматизації
• Глушков В. М . Синтез цифрових автоматів. - М .: ГІФМЛ , 1962. - 476 с.