Скінченний автомат: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
Немає опису редагування |
||
Рядок 1:
'''Скінче́нний автома́т''', є особливим видом [[автомат]]у — абстракції, що використовується для описання шляху зміни стану об'єкта в залежності від досягнутого стану та інформації отриманої ззовні. Його особливістю є [[Скінченна множина|скінченність множини]] станів автомату. Поняття скінченного автомата було запропоновано в якості [[Математична модель|математичної моделі]] технічних приладів дискретної дії, оскільки будь який такий пристрій (в силу скінченності своїх розмірів) може мати тільки скінченну кількість станів.
Скінченні автомати можуть розв'язувати велику кількість задач, серед яких автоматизація проектування електронних приладів, проектування [[Комунікаційний протокол|комунікаційних протоколів]], [[синтаксичний аналіз]] та інші інженерні застосування. В [[біологія|біології]] і дослідженнях [[штучний інтелект|штучного інтелекту]], автомати або їх ієрархії іноді використовуються для описання [[Неврологія|неврологічних систем]] і в [[лінгвістика|лінгвістиці]] для описання граматики природніх [[мова|мов]].
==Класифікація==
Існує дві різних групи автоматів: Акцептори/Розпізнавачі і Перетворювачі(Трансдуктори).
===Акцептори і розпізнавачі===
[[File:Fsm parsing word nice.svg|thumb|400px|right|СА акцептор: виконує розбір слова "nice"]]
'''Акцептори''' і '''розпізнавачі''' (також '''виювлювачі послідовностей''') продукують двійковий вихід, кажучи або ''так'' або ''ні'' на питання прийняті автоматом вхідні дані чи ні. Всі стани СА можуть бути або допустими або ні. Коли всі вхідні дані оброблені, якщо поточний стан є допустим, значить вхід прийнятий; інакше відхилений. Як правило на вхід подаються символи (літери); дії не використовуються. Приклад на зображенні показує СА який приймає слово «nice». В цьому СА єдиний допустимий стан це 7.
Автомат також може бути описаний як такий, що визначає мову, яка містить всі слова розпізнавані цим автоматом, але не ті які їм відхиляються; тоді ми кажемо, що ця мова ''розпізнається'' автоматом. За визначенням, мови розпізнавані СА це [[регулярні мови]] тобто мова є регулярною якщо існує деякий СА, який розпізнає її.
====Початковий стан====
Початковий стан зазвичаай показується зі стрілкою «звідкісь».
====Допустимі (або кінцеві) стани====
[[Файл: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:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) ситуація: «двері відчинені» або «двері зачинені».
[[File:Fsm mealy model door control.jpg|thumb|350px|right| СА перетворювач: приклад моделі Мілі]]
;[[Автомат Мілі]]: СА, що використовує тільки вхідні дії, тобто, вихід базується на вході і стані. Використання СА Мілі часто призводить до зменшення кількості станів. Приклад на малюнці показує СА Мілі реалізуючий однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані.
На практиці часто використовується суміш моделей.
Більше подробиць по відмінностям і використанню моделей Мура і Мілі із виконанними прикладами можна знайти на [http://www.stateworks.com/active/content/en/technology/technical_notes.php#tn10 "Moore or Mealy model? (Модель Мура або Мілі?)"]
===Детермінованість===
Подальша відмінність між '''Детермінованими''' ([[детермінований скінченний автомат|ДСА]]) і '''недетермінованими''' ([[недетермінований скінченний автомат|НСА]]) автоматами. В детермінованих автоматах, кожен стан має лише один перехід для кожного входу. В недетермінованих автоматах вхід може призвести до одного, більше ніж одного або зовсім без переходу для даного стану. Ця різниця важлива на практиці, але не в теорії, через існування алгоритму трансформації будь-якого НСА в більш складний ДСА з однаковою функціональністю.
==Математична модель==
| |||