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

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

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

Класифікація

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

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

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

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

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

Початковий стан

Початковий стан зазвичай показується зі стрілкою «звідкись».

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

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

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

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

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

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

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

Автомат Мура

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

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

Автомат Мілі

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

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

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

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

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

Математична модель

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

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

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

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

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

Автоматні оператори

Означення: Відповідність, яка відображає вхідні ланцюжки a автомата M у вихідні ланцюжки w називають автоматним відображенням, а також автоматним оператором M. Якщо результат застосування цього оператора до ланцюжка a - вихідний ланцюжок w,

то це позначають M(a) = w. Кількість символів у ланцюжку a, як завжди, називають довжиною ланцюжка a та позначають |a| чи l(a).

Автоматне відображення має дві властивості:

1. Ланцюжки a та w = M(a) мають однакову довжину: |a| = |w| (збереження довжини).

2. Якщо a = a1a2 й M(a1a2) = w1w2, де |a1| = |w1|, то M(a1) = w1, тобто образ відрізка довжиною l дорівнює відрізку образу з такою самою довжиною.

Властивість 2 означає, що автоматні оператори - це оператори без випередження, тобто такі, котрі, обробляючи ланцюжок зліва направо, “не підглядають уперед”: i-та буква вихідного ланцюжка залежить тільки від перших i букв вхідного ланцюжка. Приклад оператора з випередженням - той, який ланцюжку a = x1x2…xk ставить у відповідність ланцюжок xk…x1x2, перша буква вихідного ланцюжка тут дорівнює останній букві вхідного ланцюжка. Зазначимо, що ці дві властивості - це не достатні умови автоматності відображення: існують відображення, які задовольняють умови 1 і 2, але не реалізовані в скінченному автоматі.

Див. також

Теорія автоматів Абстрактного автомата граф Автомата таблиця Автомата пам'ять Автомата матриця переходів Регулярний вислів Аналіз автоматів

Автоматів суперпозиція Автомат мікропрограмний Автомат ініціальний Автомат лінійний Автомат вільний Автомат без пам'яті Автомат частковий Автомат операційний Автомат мінімальний Рідкий скінченний автомат