Скінченний автомат

Існує дві різних групи автоматів: Акцептори/Розпізнавачі і Перетворювачі (Трансдуктори).

Акцептори і розпізнавачі

СА акцептор: виконує розбір слова «nice»

Акцептори і розпізнавачі (також виявлювачі послідовностей) дають двійковий результат, відповідаючи так або ні на питання чи вхідні дані приймаються автоматом. Всі стани автомата можуть бути або приймаючими або ні. Якщо поточний стан автомата є приймаючим, значить послідовність подана на вхід приймається. Як правило, на вхід подаються символи (літери); дії не використовуються. Приклад на зображенні показує автомат, який приймає слово «nice». В цьому автоматі єдиний допустимий стан це 7.

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

Допустимі (або кінцеві) стани

Приклад скінченного автомата; цей приклад показує автомат, який визначає чи двійкове число має непарну кількість 0, де ${\displaystyle S_{1}}$ це допустимий стан.

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

Приклад допустимого стану з'являється в діаграмі праворуч: a детермінований скінченний автомат (ДСА), що визначає чи двійковий вхідний рядок містить парну кількість 0.

S₁ (який є початковим станом) показує стан в якому парна кількість 0 була введена. Цей автомат опиниться в допустимому стані, якщо двійковий рядок містить парну кількість 0 (включно з рядком, що не містить 0 взагалі). Приклади рядків розпізнаваних цим ДСА це порожній рядок, 1, 11, 11…, 00, 010, 1010, 10110, і подібні …

Перетворювачі (Трансдуктори)

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

Автомат Мура

СА використовує тільки вхідні дії, тобто, вихід базується тільки на стані. Перевагою моделі Мура є спрощення поведінки. Уявімо двері підйомника. Автомат розпізнає дві команди: «відчинити» і «зачинити», які викликають зміну стану. Вхідна дія (E:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) про ситуацію: «двері відчинені» або «двері зачинені».

СА перетворювач: приклад моделі Мілі

Автомат Мілі

СА, що використовує вхідні дії та стани, тобто, вихід базується на вході і стані. Використання СА Мілі часто призводить до зменшення кількості станів. Приклад на схемі показує СА Мілі, який має однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані.

На практиці часто використовується суміш моделей.

Більше подробиць по відмінностям і використанню моделей Мура і Мілі із виконаними прикладами можна знайти на «Moore or Mealy model? (Модель Мура або Мілі?)»

Згідно із загальною класифікацією, дані наступні визначення:

• детермінований скінченний автомат або детермінований скінченний автомат акцептор є п'ятіркою ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$, де:
  • ${\displaystyle \Sigma }$ вхідна абетка (скінченний, не порожній набір символів).
  • ${\displaystyle S}$ — скінченний, не порожній набір станів.
  • ${\displaystyle s_{0}}$ — початковий стан, елемент з ${\displaystyle S}$.
  • ${\displaystyle \delta }$ — функція переходу: ${\displaystyle \delta :S\times \Sigma \rightarrow S}$ (в недетермінованих скінченних автоматах це буде ${\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}$, тобто, ${\displaystyle \delta }$ повертає набір станів).
  • ${\displaystyle F}$ набір кінцевих станів, (можливо порожня) підмножина ${\displaystyle S}$.

Для обох детермінованих і недетермінованих СА, зручно дозволити ${\displaystyle \delta }$ бути неповною функцією, тобто ${\displaystyle \delta (q,x)}$ не має бути визначеною для кожної комбінації ${\displaystyle q\in S}$ і ${\displaystyle x\in \Sigma }$. Якщо СА ${\displaystyle M}$ перебуває в стані ${\displaystyle q}$, наступний символ ${\displaystyle x}$ і ${\displaystyle \delta (q,x)}$ не визначена, тоді ${\displaystyle M}$ може повідомити про помилку (тобто відхілити ввід).

• скінченний перетворювач це шістка ${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$, де:
  • ${\displaystyle \Sigma }$ — вхідна абетка (скінченний, не порожній набір символів).
  • ${\displaystyle \Gamma }$ — вихідна абетка (скінченний, не порожній набір символів).
  • ${\displaystyle S}$ — скінченний, не порожній набір станів.
  • ${\displaystyle s_{0}}$ — початковий стан, елемент з ${\displaystyle S}$ (в недетермінованих скінченних автоматах, ${\displaystyle s_{0}}$ це набір початкових станів).
  • ${\displaystyle \delta }$ — функція переходу: ${\displaystyle \delta :S\times \Sigma \rightarrow S}$.
  • ${\displaystyle \omega }$ функція виходу.

Якщо функція виходу є функцією стану і вхідної абетки(${\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }$) таке визначення відповідає моделі Мілі, і може бути виконана як автомат Мілі. Якщо функція виходу залежить тільки від стану (${\displaystyle \omega :S\rightarrow \Gamma }$) тоді таке визначення відповідає моделі Мура, і може бути виконана як автомат Мура. Скінченний автомат без функції виходу відомий як напівавтомат або як модель станів і переходів.

• Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 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 с.