Скінче́нний автома́т (англ. finite-state machine, автомат зі скінченною множиною станів) — модель що використовується для опису зміни стану об'єкта в залежності від поточного стану та інформації отриманої ззовні. Поняття скінченного автомата було запропоновано як математичну модель дискретних приладів, оскільки будь-який такий прилад (через скінченність своїх розмірів) може мати тільки скінченну кількість станів.
Скінченні автомати допомагають розв'язувати багато задач, серед яких автоматизація проєктування електронних приладів, проєктування комунікаційних протоколів, синтаксичний аналіз та інші інженерні застосування. В біології і дослідженнях штучного інтелекту, автомати або їх ієрархії іноді використовуються для опису неврологічних систем і в лінгвістиці для опису граматики природних мов.
Класифікація
Існує дві різних групи автоматів: Акцептори/Розпізнавачі і Перетворювачі (Трансдуктори).
Акцептори і розпізнавачі
Акцептори і розпізнавачі (також виявлювачі послідовностей) дають двійковий результат, відповідаючи так або ні на питання чи вхідні дані приймаються автоматом. Всі стани автомата можуть бути або приймаючими або ні. Якщо поточний стан автомата є приймаючим, значить послідовність подана на вхід приймається. Як правило, на вхід подаються символи (літери); дії не виконуються. Приклад на зображенні показує автомат, який приймає слово «nice». В цьому автоматі єдиний допустимий стан це 7.
Автомат також може бути описаний як такий, що визначає мову, яка містить всі слова розпізнавані цим автоматом, але не ті які ним відхиляються; тоді ми кажемо, що ця мова розпізнається автоматом. За визначенням, мови розпізнавані СА це регулярні мови, тобто мова є регулярною якщо існує деякий СА, який розпізнає її.
Початковий стан
Початковий стан зазвичай позначається стрілкою «звідкись».
Допустимі (або кінцеві) стани
Допустимі стани (також відомі як кінцеві стани) це такі, що якщо автомат знаходиться в них це означає, що вхідний рядок, наскільки він опрацьований, належить мові що розпізнається. Зазвичай позначається двома колами.
Приклад допустимого стану з'являється в діаграмі праворуч: a детермінований скінченний автомат (ДСА), що визначає чи двійковий вхідний рядок містить парну кількість 0.
S1 (який є початковим станом) показує стан в якому парна кількість 0 була введена. Цей автомат опиниться в допустимому стані, якщо двійковий рядок містить парну кількість 0 (включно з рядком, що не містить 0 взагалі). Приклади рядків розпізнаваних цим ДСА це порожній рядок, 1, 11, 11…, 00, 010, 1010, 10110, і подібні …
Перетворювачі (Трансдуктори)
Перетворювачі продукують вихід або виконують інші дії, на основі символу на вході і/або на станах. Вони використовуються для керування і в галузі математичної лінгвістики. Тут вирізняють два типи:
- Автомат Мура
- вихід залежить тільки від стану. Перевагою моделі Мура є спрощення поведінки. Уявімо двері підйомника. Автомат розпізнає дві команди: «відчинити» і «зачинити», які викликають зміну стану. Вхідна дія (E:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) про ситуацію: «двері відчинені» або «двері зачинені».
- Автомат Мілі
- вихід залежить від входу і стану. Використання скінченного автомата Мілі часто призводить до зменшення кількості станів. Приклад на схемі показує скінченний автомат Мілі, який має однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані.
На практиці часто використовується суміш моделей.
Детермінованість
Подальша відмінність між Детермінованими (ДСкА) і недетермінованими (НДСкА) автоматами. В детермінованих автоматах, кожен стан має один перехід для кожного входу. В недетермінованих автоматах вхід може призвести до одного, більше ніж одного або жодного переходу для даного стану. Ця різниця важлива на практиці, але не в теорії, через існування алгоритму трансформації будь-якого НДСкА в складніший ДСкА з аналогічною функціональністю.
Якщо автомат має лише один стан, то, згідно Енциклопедії кібернетики він називається автоматом без пам'яті ((англ. combinatorial finite-state machine). Оскільки під час роботи стан такого автомату змінюватись не може, то вихідний символ залежить саме від вхідного символу в поточному такті, і не залежить від символів, які надходили перед тим. Оператор, який реалізується таким автоматом, виконує перетворення літери за літерою вхідних символів у вихідні.
Математична модель
Згідно із загальною класифікацією, дані наступні визначення:
- детермінований скінченний автомат або детермінований скінченний автомат акцептор є п'ятіркою , де:
- вхідна абетка (скінченний, не порожній набір символів).
- — скінченний, не порожній набір станів.
- — початковий стан, елемент з .
- — функція переходу: (в недетермінованих скінченних автоматах це буде , тобто, повертає набір станів).
- набір кінцевих станів, (можливо порожня) підмножина .
Для обох детермінованих і недетермінованих СА, зручно дозволити бути неповною функцією, тобто не має бути визначеною для кожної комбінації і . Якщо СА перебуває в стані , наступний символ і не визначена, тоді може повідомити про помилку (тобто відхілити ввід).
- скінченний перетворювач це шістка , де:
- — вхідна абетка (скінченний, не порожній набір символів).
- — вихідна абетка (скінченний, не порожній набір символів).
- — скінченний, не порожній набір станів.
- — початковий стан, елемент з (в недетермінованих скінченних автоматах, це набір початкових станів).
- — функція переходу: .
- функція виходу.
Якщо функція виходу є функцією стану і вхідної абетки() таке визначення відповідає моделі Мілі, і може бути виконана як автомат Мілі. Якщо функція виходу залежить тільки від стану () тоді таке визначення відповідає моделі Мура, і може бути виконана як автомат Мура. Скінченний автомат без функції виходу відомий як напівавтомат або як модель станів і переходів.
Автоматні оператори
Означення: Відповідність, яка відображає вхідні ланцюжки 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, але не реалізовані в скінченному автоматі.
Див. також
Примітки
- Moore or Mealy model: that's the question. www.stateworks.com. Процитовано 8 вересня 2023.
Ця стаття містить , але походження окремих тверджень через брак . (вересень 2021) |
Посилання
Українською
- Формальні мови та алгоритмічні моделі. — І.-Ф. : Голіней, 2023. — 180 с.
Іншими мовами
- Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования [ 3 січня 2022 у Wayback Machine.] — М.: МЗ-Пресс, 2006 г., 2-е изд. —
- Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109—188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
- Применение конечных автоматов для решения задач автоматизации [ 12 вересня 2021 у Wayback Machine.]
- Глушков В. М. Синтез цифровых автоматов. — М.: [ru], 1962. — 476 с.
Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Skinche nnij avtoma t angl finite state machine avtomat zi skinchennoyu mnozhinoyu staniv model sho vikoristovuyetsya dlya opisu zmini stanu ob yekta v zalezhnosti vid potochnogo stanu ta informaciyi otrimanoyi zzovni Ponyattya skinchennogo avtomata bulo zaproponovano yak matematichnu model diskretnih priladiv oskilki bud yakij takij prilad cherez skinchennist svoyih rozmiriv mozhe mati tilki skinchennu kilkist staniv Klasi avtomativ Klacannya na kozhnomu shari skerovuye do statti na vidpovidnu temu Skinchenni avtomati dopomagayut rozv yazuvati bagato zadach sered yakih avtomatizaciya proyektuvannya elektronnih priladiv proyektuvannya komunikacijnih protokoliv sintaksichnij analiz ta inshi inzhenerni zastosuvannya V biologiyi i doslidzhennyah shtuchnogo intelektu avtomati abo yih iyerarhiyi inodi vikoristovuyutsya dlya opisu nevrologichnih sistem i v lingvistici dlya opisu gramatiki prirodnih mov KlasifikaciyaIsnuye dvi riznih grupi avtomativ Akceptori Rozpiznavachi i Peretvoryuvachi Transduktori Akceptori i rozpiznavachi Skinchennij avtomat akceptor prijmaye slovo nice Akceptori i rozpiznavachi takozh viyavlyuvachi poslidovnostej dayut dvijkovij rezultat vidpovidayuchi tak abo ni na pitannya chi vhidni dani prijmayutsya avtomatom Vsi stani avtomata mozhut buti abo prijmayuchimi abo ni Yaksho potochnij stan avtomata ye prijmayuchim znachit poslidovnist podana na vhid prijmayetsya Yak pravilo na vhid podayutsya simvoli literi diyi ne vikonuyutsya Priklad na zobrazhenni pokazuye avtomat yakij prijmaye slovo nice V comu avtomati yedinij dopustimij stan ce 7 Avtomat takozh mozhe buti opisanij yak takij sho viznachaye movu yaka mistit vsi slova rozpiznavani cim avtomatom ale ne ti yaki nim vidhilyayutsya todi mi kazhemo sho cya mova rozpiznayetsya avtomatom Za viznachennyam movi rozpiznavani SA ce regulyarni movi tobto mova ye regulyarnoyu yaksho isnuye deyakij SA yakij rozpiznaye yiyi Pochatkovij stan Pochatkovij stan zazvichaj poznachayetsya strilkoyu zvidkis Dopustimi abo kincevi stani Priklad skinchennogo avtomata cej priklad pokazuye avtomat yakij viznachaye chi dvijkove chislo maye parnu kilkist 0 de S1 displaystyle S 1 ce dopustimij stan Dopustimi stani takozh vidomi yak kincevi stani ce taki sho yaksho avtomat znahoditsya v nih ce oznachaye sho vhidnij ryadok naskilki vin opracovanij nalezhit movi sho rozpiznayetsya Zazvichaj poznachayetsya dvoma kolami Priklad dopustimogo stanu z yavlyayetsya v diagrami pravoruch a determinovanij skinchennij avtomat DSA sho viznachaye chi dvijkovij vhidnij ryadok mistit parnu kilkist 0 S1 yakij ye pochatkovim stanom pokazuye stan v yakomu parna kilkist 0 bula vvedena Cej avtomat opinitsya v dopustimomu stani yaksho dvijkovij ryadok mistit parnu kilkist 0 vklyuchno z ryadkom sho ne mistit 0 vzagali Prikladi ryadkiv rozpiznavanih cim DSA ce porozhnij ryadok 1 11 11 00 010 1010 10110 i podibni Peretvoryuvachi Transduktori Peretvoryuvachi produkuyut vihid abo vikonuyut inshi diyi na osnovi simvolu na vhodi i abo na stanah Voni vikoristovuyutsya dlya keruvannya i v galuzi matematichnoyi lingvistiki Tut viriznyayut dva tipi Avtomat Mura vihid zalezhit tilki vid stanu Perevagoyu modeli Mura ye sproshennya povedinki Uyavimo dveri pidjomnika Avtomat rozpiznaye dvi komandi vidchiniti i zachiniti yaki viklikayut zminu stanu Vhidna diya E v stani Vidchinyayutsya zmushuye dvigun vidchinyati dveri vhidna diya v stani Zachinyayutsya zmushuye dvigun zachinyati dveri Stani Vidchineno i Zachineno zupinyayut motor koli dveri povnistyu vidchineni abo zachineni Voni povidomlyayut zovnishnij svit napriklad inshi avtomati pro situaciyu dveri vidchineni abo dveri zachineni skinchennij avtomat peretvoryuvach priklad modeli MiliAvtomat Mili vihid zalezhit vid vhodu i stanu Vikoristannya skinchennogo avtomata Mili chasto prizvodit do zmenshennya kilkosti staniv Priklad na shemi pokazuye skinchennij avtomat Mili yakij maye odnakovu povedinku iz prikladom avtomata Mura Prisutni dvi vhidni diyi I zapustiti dvigun dlya zakrittya dverej yaksho prijshla komanda zachiniti i zapustiti motor v inshomu napryamku yaksho dlya vidchinennya dverej yaksho prijshla komanda vidchiniti Promizhni stani Vidchinennya i Zachinennya ne pokazani Na praktici chasto vikoristovuyetsya sumish modelej Determinovanist Podalsha vidminnist mizh Determinovanimi DSkA i nedeterminovanimi NDSkA avtomatami V determinovanih avtomatah kozhen stan maye odin perehid dlya kozhnogo vhodu V nedeterminovanih avtomatah vhid mozhe prizvesti do odnogo bilshe nizh odnogo abo zhodnogo perehodu dlya danogo stanu Cya riznicya vazhliva na praktici ale ne v teoriyi cherez isnuvannya algoritmu transformaciyi bud yakogo NDSkA v skladnishij DSkA z analogichnoyu funkcionalnistyu Yaksho avtomat maye lishe odin stan to zgidno Enciklopediyi kibernetiki vin nazivayetsya avtomatom bez pam yati angl combinatorial finite state machine Oskilki pid chas roboti stan takogo avtomatu zminyuvatis ne mozhe to vihidnij simvol zalezhit same vid vhidnogo simvolu v potochnomu takti i ne zalezhit vid simvoliv yaki nadhodili pered tim Operator yakij realizuyetsya takim avtomatom vikonuye peretvorennya literi za literoyu vhidnih simvoliv u vihidni Matematichna modelZgidno iz zagalnoyu klasifikaciyeyu dani nastupni viznachennya determinovanij skinchennij avtomat abo determinovanij skinchennij avtomat akceptor ye p yatirkoyu S S s0 d F displaystyle Sigma S s 0 delta F de S displaystyle Sigma vhidna abetka skinchennij ne porozhnij nabir simvoliv S displaystyle S skinchennij ne porozhnij nabir staniv s0 displaystyle s 0 pochatkovij stan element z S displaystyle S d displaystyle delta funkciya perehodu d S S S displaystyle delta S times Sigma rightarrow S v nedeterminovanih skinchennih avtomatah ce bude d S S P S displaystyle delta S times Sigma rightarrow mathcal P S tobto d displaystyle delta povertaye nabir staniv F displaystyle F nabir kincevih staniv mozhlivo porozhnya pidmnozhina S displaystyle S Dlya oboh determinovanih i nedeterminovanih SA zruchno dozvoliti d displaystyle delta buti nepovnoyu funkciyeyu tobto d q x displaystyle delta q x ne maye buti viznachenoyu dlya kozhnoyi kombinaciyi q S displaystyle q in S i x S displaystyle x in Sigma Yaksho SA M displaystyle M perebuvaye v stani q displaystyle q nastupnij simvol x displaystyle x i d q x displaystyle delta q x ne viznachena todi M displaystyle M mozhe povidomiti pro pomilku tobto vidhiliti vvid skinchennij peretvoryuvach ce shistka S G S s0 d w displaystyle Sigma Gamma S s 0 delta omega de S displaystyle Sigma vhidna abetka skinchennij ne porozhnij nabir simvoliv G displaystyle Gamma vihidna abetka skinchennij ne porozhnij nabir simvoliv S displaystyle S skinchennij ne porozhnij nabir staniv s0 displaystyle s 0 pochatkovij stan element z S displaystyle S v nedeterminovanih skinchennih avtomatah s0 displaystyle s 0 ce nabir pochatkovih staniv d displaystyle delta funkciya perehodu d S S S displaystyle delta S times Sigma rightarrow S w displaystyle omega funkciya vihodu Yaksho funkciya vihodu ye funkciyeyu stanu i vhidnoyi abetki w S S G displaystyle omega S times Sigma rightarrow Gamma take viznachennya vidpovidaye modeli Mili i mozhe buti vikonana yak avtomat Mili Yaksho funkciya vihodu zalezhit tilki vid stanu w S G displaystyle omega S rightarrow Gamma todi take viznachennya vidpovidaye modeli Mura i mozhe buti vikonana yak avtomat Mura Skinchennij avtomat bez funkciyi vihodu vidomij yak napivavtomat abo yak model staniv i perehodiv Avtomatni operatori Oznachennya Vidpovidnist yaka vidobrazhaye vhidni lancyuzhki a avtomata M u vihidni lancyuzhki w nazivayut avtomatnim vidobrazhennyam a takozh avtomatnim operatoromM Yaksho rezultat zastosuvannya cogo operatora do lancyuzhka a vihidnij lancyuzhok w to ce poznachayut M a w Kilkist simvoliv u lancyuzhku a yak zavzhdi nazivayut dovzhinoyu lancyuzhka a ta poznachayut a chi l a Avtomatne vidobrazhennya maye dvi vlastivosti 1 Lancyuzhki a ta w M a mayut odnakovu dovzhinu a w zberezhennya dovzhini 2 Yaksho a a1a2 j M a1a2 w1w2 de a1 w1 to M a1 w1 tobto obraz vidrizka dovzhinoyu l dorivnyuye vidrizku obrazu z takoyu samoyu dovzhinoyu Vlastivist 2 oznachaye sho avtomatni operatori ce operatori bez viperedzhennya tobto taki kotri obroblyayuchi lancyuzhok zliva napravo ne pidglyadayut upered i ta bukva vihidnogo lancyuzhka zalezhit tilki vid pershih i bukv vhidnogo lancyuzhka Priklad operatora z viperedzhennyam toj yakij lancyuzhku a x1x2 xk stavit u vidpovidnist lancyuzhok xk x1x2 persha bukva vihidnogo lancyuzhka tut dorivnyuye ostannij bukvi vhidnogo lancyuzhka Zaznachimo sho ci dvi vlastivosti ce ne dostatni umovi avtomatnosti vidobrazhennya isnuyut vidobrazhennya yaki zadovolnyayut umovi 1 i 2 ale ne realizovani v skinchennomu avtomati Div takozhTeoriya avtomativ Abstraktnogo avtomata graf Avtomata tablicya Avtomata pam yat Avtomata matricya perehodiv Regulyarnij visliv Analiz avtomativ Avtomativ superpoziciya Avtomat mikroprogramnij Avtomat inicialnij Avtomat linijnij Avtomat vilnij Avtomat bez pam yati Avtomat chastkovij Avtomat operacijnij Avtomat minimalnij Ridkij skinchennij avtomat Algoritmi minimizaciyi skinchennih avtomativPrimitkiMoore or Mealy model that s the question www stateworks com Procitovano 8 veresnya 2023 Cya stattya mistit perelik posilan ale pohodzhennya okremih tverdzhen zalishayetsya nezrozumilim cherez brak vnutrishnotekstovih dzherel vinosok Bud laska dopomozhit polipshiti cyu stattyu peretvorivshi dzherela z pereliku posilan na dzherela vinoski u samomu teksti statti Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki veresen 2021 PosilannyaUkrayinskoyu Formalni movi ta algoritmichni modeli I F Golinej 2023 180 s Inshimi movami Serebryakov V A Galochkin M P Gonchar D R Furugyan M G Teoriya i realizaciya yazykov programmirovaniya 3 sichnya 2022 u Wayback Machine M MZ Press 2006 g 2 e izd ISBN 5 94073 094 9 Teoriya avtomatov E A Yakubajtis V O Vasyukevich A Yu Gobzemis N E Zaznova A A Kurmit A A Lorenc A F Petrenko V P Chapenko Teoriya veroyatnostej Matematicheskaya statistika Teoreticheskaya kibernetika M VINITI 1976 T 13 S 109 188 URL http www mathnet ru php getFT phtml jrnid intv amp paperid 28 amp what fullt amp option lang rus Primenenie konechnyh avtomatov dlya resheniya zadach avtomatizacii 12 veresnya 2021 u Wayback Machine Glushkov V M Sintez cifrovyh avtomatov M ru 1962 476 s Portal Matematika Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi