Кінцевий автомат - це
Кінцевий автомат - абстрактний автомат без вихідного потоку, число можливих станів якого звичайно. Результат роботи автомата визначається по його кінцевого стану.
Існують різні варіанти завдання кінцевого автомата. Наприклад, кінцевий автомат може бути заданий за допомогою п'яти параметрів:, де:
- Q - безліч станів автомата;
- q0 - початкова (стартове) стан автомата ();
- F - безліч заключних (або допускають) станів, таких що;
- Σ - допустимий вхідний алфавіт (кінцеве безліч допустимих вхідних символів), з якого формуються рядки, зчитувальні автоматом;
- δ - заданий відображення безлічі в безліч підмножин Q: (іноді δ називають функцією переходів автомата).
Автомат починає роботу в стані q0. зчитуючи по одному символу вхідного рядка. Лічені символ переводить автомат в новий стан з Q відповідно до функції переходів. Якщо по завершенні зчитування вхідного слова (ланцюжки символів) автомат виявляється в одному з допускають станів, то слово «приймається» автоматом. У цьому випадку говорять, що воно належить мові даного автомата. В іншому випадку слово «відкидається».
Інші способи опису
- Діаграма станів (або іноді граф переходів) - графічне представлення безлічі станів і функції переходів. Являє собою навантажений односпрямований граф. вершини якого - стану КА, ребра - переходи з одного стану в інший, а навантаження - символи, при яких здійснюється даний перехід. Якщо перехід зі стану q1 в q2 може бути здійснений при появі одного з декількох символів, то над дугою діаграми (гілкою графа) повинні бути надписані все вони.
- Таблиця переходів - табличне представлення функції δ. Зазвичай в такій таблиці кожному рядку відповідає один стан, а одну - один допустимий вхідний символ. В осередку на перетині рядка і стовпця записується дію, яку повинен виконати автомат, якщо в ситуації, коли він перебував в даному стані на вході він отримав даний символ.
детермінованість
Кінцеві автомати підрозділяються на детерміновані і недетерміновані.
Детермінований кінцевий автомат
- Детермінованим кінцевим автоматом (ДКА) називається такий автомат, в якому для кожної послідовності вхідних символів існує лише один стан, в яке автомат може перейти з поточного.
- Недетермінований кінцевий автомат (НКА) є узагальненням детермінованого. Недетермінірованность автоматів досягається двома способами:
Існують переходи, помічені порожній ланцюжком ε
З одного стану виходить кілька переходів, позначених одним і тим же символом
Якщо розглянути випадок, коли автомат заданий наступним чином:, де:
- S - безліч стартових станів автомата, таке що;
Тоді з'являється третя ознака недетермінізма - наявність декількох початкових (стартових) станів у автомата.
Існує теорема, яка говорить, що «Будь-який недетермінований кінцевий автомат може бути перетворений в детермінований так, щоб їхні мови збігалися» (такі автомати називаються еквівалентними). Однак, оскільки кількість станів в еквівалентному ДКА в гіршому випадку зростає експоненціально з ростом кількості станів вихідного НКА, на практиці подібна детермінізації не завжди можлива. Крім того, кінцеві автомати з виходом в загальному випадку не піддаються детермінізації.
В силу останніх двох зауважень, незважаючи на велику складність недетермінірованних кінцевих автоматів, для завдань, пов'язаних з обробкою тексту, переважно застосовуються саме НКА.
Автомати і регулярні мови
Для автомата можна визначити мову (безліч слів) в алфавіті Σ, який він представляє - так називаються слова, при введенні яких автомат переходить з початкового стану в один зі станів безлічі F.
Теорема Кліні говорить, що клас мов, які представлені кінцевими автоматами, збігається з класом регулярних мов. Крім того, цей клас збігається з класом мов, що задаються регулярними граматиками.
Спеціалізовані мови програмування
- Мова послідовних функціональних схем SFC (Sequential Function Chart) - графічна мова програмування широко використовується для програмування промислових логічних контролерів (ПЛК).
В SFC програма описується в вигляді схематичної послідовності кроків, об'єднаних переходами.
Розробка моделей з використанням кінцевих автоматів
Кінцеві автомати дозволяють побудувати моделі систем паралельної обробки, проте, щоб змінити число паралельних процесів в такій моделі потрібно внести суттєві зміни в саму модель. Крім того, спроба розробки складної моделі на кінцевому автоматі призведе до швидкого зростання числа станів автомата, що в підсумку зробить розробку такої моделі вкрай втомливим заняттям. Як було зазначено вище останню проблему можна вирішити, якщо використовувати недетермінований автомат.
Примітки
Дивитися що таке "Кінцевий автомат" в інших словниках:
Кінцевий автомат - математична модель пристрою з кінцевої пам'яттю. Кінцевий автомат переробляє велику кількість вхідних дискретних сигналів в безліч вихідних сигналів. Розрізняють синхронні і асинхронні кінцеві автомати. За англійськи: Finite state machine Див ... Фінансовий словник
кінцевий автомат - baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. кінцевий автомат, m pranc. automate final, m; automate fini, m; automate terminal, m; ... ... Automatikos terminų žodynas
КІНЦЕВИЙ АВТОМАТ - автомат, у до якого безліч станів, а також безліч вхідних і вихідних сигналів є кінцевими. К. а. може бути моделлю техніч. пристрою (ЕОМ, релейне пристрій) або біол. системи (ідеалізує. нервова система тварини). Важливими ... ... Великий енциклопедичний політехнічний словник
Кінцевий автомат з пам'яттю - кінцевий автомат з пам'яттю математична модель пристрою, поведінка якого залежить як від вхідних умов, так і від попереднього стану. Для опису кінцевого автомата з пам'яттю використовуються мови операторних схем, регулярних ... ... Вікіпедія
Автомат Мура - (автомат другого роду) в теорії обчислень кінцевий автомат, вихідне значення сигналу в якому залежить лише від поточного стану даного автомата, і не залежить безпосередньо, на відміну від автомата Мілі, від вхідних значень. Автомат Мура названий ... Вікіпедія
- Програмування: формальні мови і компілятори. Навчальний посібник для вузів. Малявко А.А. У виданні викладені теоретичні основи апарату визначення лексики (регулярні вирази) і синтаксису (формальні граматики) мов програмування, елементи теорії кінцевих автоматів ... Детальніше Купити за 1200 руб
- Кінцевий автомат. Джессі Рассел. Ця книга буде виготовлена в відповідності з Вашим замовленням за технологією Print-on-Demand. High Quality Content by WIKIPEDIA articles! Кінцевий автомат - абстрактний автомат без вихідного ... Детальніше Купити за тисячі сто сорок сім руб
- Програмування: формальні мови і компілятори. Навчальний посібник для вузів. Малявко А.А. У виданні викладені теоретичні основи апарату визначення лексики (регулярні вирази) і синтаксису (формальні граматики) мов програмування, елементи теорії кінцевих автоматів ... Детальніше Купити за 1090 грн (тільки Україна)