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

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

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

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

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

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

СА акцептор: виконує розбір слова "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$ and $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$) тоді таке визначення відповідає моделі Мура, і може бути виконана як автомат Мура. Скінченний автомат без функції виходу відомий як напівавтомат або як модель станів і переходів.

Див. також

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

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