www.wikidata.uk-ua.nina.az

Скінченний автомат Скінче нний автома т англ finite state machine автомат зі скінченною множиною станів модель що викори

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

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

Скінчений автоматАвтомат з магазинною пам'яттюМашина ТюрінгаТеорія автоматів
Класи автоматів (Клацання на кожному шарі скеровує до статті на відповідну тему)

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

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

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

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

Скінченний автомат акцептор: приймає слово «nice»

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

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

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

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

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

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

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

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

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

Перетворювачі (Трансдуктори) ред.

Перетворювачі продукують вихід або виконують інші дії, на основі символу на вході і/або на станах. Вони використовуються для керування і в галузі математичної лінгвістики. Тут вирізняють два типи:

скінченний автомат перетворювач: приклад моделі Мілі

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

Детермінованість ред.

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

Якщо автомат має лише один стан, то, згідно Енциклопедії кібернетики він називається автоматом без пам'яті ((англ. 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, але не реалізовані в скінченному автоматі.

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

Примітки ред.

  1. Moore or Mealy model: that's the question. www.stateworks.com. Процитовано 8 вересня 2023. 
Ця стаття містить перелік посилань, але походження окремих тверджень залишається незрозумілим через брак внутрішньотекстових джерел-виносок. Будь ласка, допоможіть поліпшити цю статтю, перетворивши джерела з переліку посилань на джерела-виноски у самому тексті статті. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. (вересень 2021)

Посилання ред.

Українською ред.

  • Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.

Іншими мовами ред.


Це незавершена стаття з інформатики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 Zmist 1 Klasifikaciya 1 1 Akceptori i rozpiznavachi 1 1 1 Pochatkovij stan 1 1 2 Dopustimi abo kincevi stani 1 2 Peretvoryuvachi Transduktori 1 3 Determinovanist 2 Matematichna model 2 1 Avtomatni operatori 3 Div takozh 4 Primitki 5 Posilannya 5 1 Ukrayinskoyu 5 2 Inshimi movamiKlasifikaciya red Isnuye dvi riznih grupi avtomativ Akceptori Rozpiznavachi i Peretvoryuvachi Transduktori Akceptori i rozpiznavachi red nbsp 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 red Pochatkovij stan zazvichaj poznachayetsya strilkoyu zvidkis Dopustimi abo kincevi stani red nbsp Priklad skinchennogo avtomata cej priklad pokazuye avtomat yakij viznachaye chi dvijkove chislo maye parnu kilkist 0 de S1 displaystyle S 1 nbsp 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 red 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 nbsp 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 1 Determinovanist red 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 model red Zgidno 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 nbsp de S displaystyle Sigma nbsp vhidna abetka skinchennij ne porozhnij nabir simvoliv S displaystyle S nbsp skinchennij ne porozhnij nabir staniv s0 displaystyle s 0 nbsp pochatkovij stan element z S displaystyle S nbsp d displaystyle delta nbsp funkciya perehodu d S S S displaystyle delta S times Sigma rightarrow S nbsp v nedeterminovanih skinchennih avtomatah ce bude d S S P S displaystyle delta S times Sigma rightarrow mathcal P S nbsp tobto d displaystyle delta nbsp povertaye nabir staniv F displaystyle F nbsp nabir kincevih staniv mozhlivo porozhnya pidmnozhina S displaystyle S nbsp Dlya oboh determinovanih i nedeterminovanih SA zruchno dozvoliti d displaystyle delta nbsp buti nepovnoyu funkciyeyu tobto d q x displaystyle delta q x nbsp ne maye buti viznachenoyu dlya kozhnoyi kombinaciyi q S displaystyle q in S nbsp i x S displaystyle x in Sigma nbsp Yaksho SA M displaystyle M nbsp perebuvaye v stani q displaystyle q nbsp nastupnij simvol x displaystyle x nbsp i d q x displaystyle delta q x nbsp ne viznachena todi M displaystyle M nbsp 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 nbsp de S displaystyle Sigma nbsp vhidna abetka skinchennij ne porozhnij nabir simvoliv G displaystyle Gamma nbsp vihidna abetka skinchennij ne porozhnij nabir simvoliv S displaystyle S nbsp skinchennij ne porozhnij nabir staniv s0 displaystyle s 0 nbsp pochatkovij stan element z S displaystyle S nbsp v nedeterminovanih skinchennih avtomatah s0 displaystyle s 0 nbsp ce nabir pochatkovih staniv d displaystyle delta nbsp funkciya perehodu d S S S displaystyle delta S times Sigma rightarrow S nbsp w displaystyle omega nbsp funkciya vihodu Yaksho funkciya vihodu ye funkciyeyu stanu i vhidnoyi abetki w S S G displaystyle omega S times Sigma rightarrow Gamma nbsp 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 nbsp 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 red 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 takozh red Teoriya 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 avtomativPrimitki red Moore 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 Posilannya red Ukrayinskoyu red Gavrilkiv V M Formalni movi ta algoritmichni modeli I F Golinej 2023 180 s Inshimi movami red Serebryakov V A Galochkin M P Gonchar D R Furugyan M G Teoriya i realizaciya yazykov programmirovaniya Arhivovano 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 Arhivovano 12 veresnya 2021 u Wayback Machine Glushkov V M Sintez cifrovyh avtomatov M GIFML ru 1962 476 s nbsp Portal Matematika nbsp Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Skinchennij avtomat amp oldid 41384121