Перегляд вихідного коду сторінки Скінченний автомат

{{Сирий переклад|en|дата=грудень 2016}}
{{Теорія автоматів}}
'''Скінче́нний автома́т''' ({{lang-en|finite-state machine}}, машина зі скінченною кількістю станів)&nbsp;— особливий різновид [[Абстрактний автомат|автомата]]&nbsp;— абстракції, що використовується для опису шляху зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Його особливістю є [[Скінченна множина|скінченність множини]] станів автомату. Поняття скінченного автомата було запропоновано як [[Математична модель|математичну модель]] технічних приладів дискретної дії, оскільки будь-який такий пристрій (в силу скінченності своїх розмірів) може мати тільки скінченну кількість станів.

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

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

=== Акцептори і розпізнавачі ===
[[Файл:Fsm parsing word nice.svg|thumb|400px|right|СА акцептор: виконує розбір слова «nice»]]

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

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

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

==== Допустимі (або кінцеві) стани{{anchor |Допустимі стани}} ====
[[Файл:DFAexample.svg|thumb|300px|right|Приклад скінченного автомата; цей приклад показує автомат, який визначає чи двійкове число має непарну кількість 0, де <math>S_1</math> це '''допустимий стан'''.]]

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

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

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

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

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

[[Файл:Fsm mealy model door control.svg|thumb|lang=uk|350px|right| СА перетворювач: приклад моделі Мілі]]
;[[Автомат Мілі]]: СА, що використовує вхідні дії та стани, тобто, вихід базується на вході і стані. Використання СА Мілі часто призводить до зменшення кількості станів. Приклад на схемі показує СА Мілі, який має однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані.

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

Більше подробиць по відмінностям і використанню моделей Мура і Мілі із виконаними прикладами можна знайти на [http://www.stateworks.com/active/content/en/technology/technical_notes.php#tn10 «Moore or Mealy model? (Модель Мура або Мілі?)»]

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

Якщо автомат має лише один стан, то, згідно [[Енциклопедія кібернетики|Енциклопедії кібернетики]] він називається ''автоматом без пам'яті'' (({{lang-en|combinatorial finite-state machine}}). Оскільки під час роботи стан такого автомату змінюватись не може, то вихідний символ залежить саме від вхідного символу в поточному такті, і не залежить від символів, які надходили перед тим.

[[Оператор (математика)|Оператор]], який реалізується таким автоматом, виконує перетворення літери за літерою вхідних символів у вихідні. Такі оператори називаються ''операторами істинності''. Вони є, по суті, функціями [[Багатозначна логіка|багатозначної логіки]].{{уточнити}}

== Математична модель ==
Згідно із загальною класифікацією, дані наступні визначення:
* ''детермінований скінченний автомат'' або ''детермінований скінченний автомат акцептор'' є [[Кортеж|п'ятіркою]] <math>(\Sigma, S, s_0, \delta, F)</math>, де:
** <math>\Sigma</math> вхідна [[абетка (інформатика)|абетка]] (скінченний, не порожній набір символів).
** <math>S</math>&nbsp;— скінченний, не порожній набір станів.
** <math>s_0</math>&nbsp;— початковий стан, елемент з <math>S</math>.
** <math>\delta</math>&nbsp;— функція переходу: <math>\delta: S \times \Sigma \rightarrow S</math> (в [[недетермінований скінченний автомат|недетермінованих скінченних автоматах]] це буде <math>\delta: S \times \Sigma \rightarrow \mathcal{P}(S)</math>, тобто, <math>\delta</math> повертає набір станів).
** <math>F</math> набір кінцевих станів, (можливо порожня) підмножина <math>S</math>.

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

* ''скінченний перетворювач'' це шістка <math>(\Sigma, \Gamma, S, s_0, \delta, \omega)</math>, де:
** <math>\Sigma</math>&nbsp;— вхідна абетка (скінченний, не порожній набір символів).
** <math>\Gamma</math>&nbsp;— вихідна абетка (скінченний, не порожній набір символів).
** <math>S</math>&nbsp;— скінченний, не порожній набір станів.
** <math>s_0</math>&nbsp;— початковий стан, елемент з <math>S</math> (в недетермінованих скінченних автоматах, <math>s_0</math> це набір початкових станів).
** <math>\delta</math>&nbsp;— функція переходу: <math>\delta: S \times \Sigma \rightarrow S</math>.
** <math>\omega</math> функція виходу.

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

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

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

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

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

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

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

== Див. також ==
{{Multicol}}
* [[Теорія автоматів]]
* [[Абстрактного автомата граф]]
* [[Автомата таблиця]]
* [[Автомата пам'ять]]
* [[Автомата матриця переходів]]
* [[Регулярний вислів]]
* [[Аналіз автоматів]]
* [[Автоматів суперпозиція]]
* [[Автомат мікропрограмний]]
{{Multicol-break}}
* [[Автомат ініціальний]]
* [[Автомат лінійний]]
* [[Автомат вільний]]
* [[Автомат без пам'яті]]
* [[Автомат частковий]]
* [[Автомат операційний]]
* [[Автомат мінімальний]]
* [[Рідкий скінченний автомат]]
* [[Алгоритми мінімізації скінченних автоматів]]
{{Multicol-end}}

== Джерела ==
{{Недостатньо виносок|дата=вересень 2021}}
* ''Серебряков&nbsp;В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г.'' [http://trpl7.ru/t-books/TRYAP_BOOK_Details.htm Теория и реализация языков программирования]&nbsp;— М.: МЗ-Пресс, 2006 г., 2-е изд.&nbsp;— ISBN 5-94073-094-9
* Теория автоматов / ''Э.&nbsp;А.&nbsp;Якубайтис, В.&nbsp;О.&nbsp;Васюкевич, А.&nbsp;Ю.&nbsp;Гобземис, Н.&nbsp;Е.&nbsp;Зазнова, А.&nbsp;А.&nbsp;Курмит, А.&nbsp;А.&nbsp;Лоренц, А.&nbsp;Ф.&nbsp;Петренко, В.&nbsp;П.&nbsp;Чапенко'' // Теория вероятностей. Математическая статистика. Теоретическая кибернетика.&nbsp;— М.: ВИНИТИ, 1976.&nbsp;— Т. 13.&nbsp;— С. 109—188.&nbsp;— URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
* [http://robot-develop.org/archives/1440#more-1440 Применение конечных автоматов для решения задач автоматизации]
* ''[[Глушков Віктор Михайлович|Глушков В. М.]]'' Синтез цифровых автоматов.&nbsp;— М.: {{нп|Фізматліт|ГИФМЛ|ru|Физматлит}}, 1962.&nbsp;— 476 с.

{{Портал|Математика}}

{{Comp-sci-stub}}
{{Math-stub}}

{{Цифрова електроніка}}
{{ВП-портали|Програмування|Інформаційні технології}}
[[Категорія:Теорія автоматів]]
[[Категорія:Цифрова електроніка]]
[[Категорія:Скінченні автомати| ]]