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

План:

1 Інші способи опису
2 Детермінованість
3 Автомати й регулярні мови
4 Спеціалізовані мови програмування

Введення

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

Існують різні варіанти завдання кінцевого автомата. Наприклад, кінцевий автомат може бути заданий за допомогою п'яти параметрів: $~ M = (Q, \ Sigma, \ delta, q_0, F)$ , Де:

Q - множина станів автомата;
q ₀ - початкове (стартове) стан автомата ( $q_0 \ in Q$ );
F - множина заключних (або допускають) станів, таких що $F \ subseteq Q$ ;
Σ - допустимий вхідний алфавіт (кінцеве безліч допустимих вхідних символів), з якого формуються рядки, зчитувальні автоматом;
δ - задане відображення множини $Q \ times \ Sigma$ в безліч $\ Mathcal {P} (Q)$ підмножин Q: $\ Delta: Q \ times \ Sigma \ rightarrow \ mathcal {P} (Q)$ (Іноді δ називають функцією переходів автомата).

Автомат починає роботу в стані q _0, зчитуючи по одному символу вхідного рядка. Лічені символ переводить автомат в новий стан з Q відповідно до функції переходів. Якщо після завершення зчитування вхідного слова (ланцюжки символів) автомат виявляється в одному з допускають станів, то слово "приймається" автоматом. У цьому випадку говорять, що воно належить мові даного автомата. В іншому випадку слово "відкидається".

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

1. Інші способи опису

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

2. Детермінованість

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

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

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

Недетермінірованний кінцевий автомат (НКА) є узагальненням детермінованого. Недетермінірованность автоматів досягається двома способами:

Існують переходи, помічені порожній ланцюжком ε	З одного стану виходить кілька переходів, помічених одним і тим же символом

Якщо розглянути випадок, коли автомат заданий наступним чином: $~ M = (Q, \ Sigma, \ delta, S, F)$ , Де:

S - безліч стартових станів автомата, таке що $S \ subseteq Q$ ;

Тоді з'являється третя ознака недетермінізма - наявність декількох початкових (стартових) станів у автомата ~ M .

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

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

3. Автомати й регулярні мови

Для автомата можна визначити мову (безліч слів) в алфавіті Σ, який він представляє - так називаються слова, при введенні яких автомат переходить з початкового стану в один зі станів безлічі F.

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

4. Спеціалізовані мови програмування

Мова послідовних функціональних схем SFC (Sequential Function Chart) - графічна мова програмування широко використовується для програмування промислових логічних контролерів ( ПЛК).

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