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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Автомат скінченний)
Перейти до: навігація, пошук

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

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

Класифікація[ред.ред. код]

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

Акцептори і розпізнавачі[ред.ред. код]

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

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

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

Початковий стан[ред.ред. код]

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

Допустимі (або кінцеві) стани[ред.ред. код]

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

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

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

S1 (який є початковим станом) показує стан в якому парна кількість 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 \isin S and x \isin \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, але не реалізовані в скінченному автоматі.

Див. також[ред.ред. код]