Абстрактна теорія автоматів — напрям в теорії автоматів, який характеризується тим, що при вивченні автоматів не беруть до уваги їх структурні особливості. За такого підходу, внутрішні стани автомата, його вхідні та вихідні сигнали розглядаються як деякі абстрактні символи, які утворюють відповідно алфавіти: Q (внутрішній), X (вхідний), Y (вихідний). X та Y вважаються скінченими алфавітами. Q може бути нескінченним.
Поняття абстрактної теорії автоматів
Детермінований автомат визначається як кортеж M = <Q, X, Y, Φ, Ψ>, де функція переходів Ψ відображає декартів добуток Q×X в Q, а функція виходів Φ відображає Q×X в Y.
Недетермінований автомат визначається аналогічно, але з тою різницею, що як Φ, Ψ допускаються багатозначні функції.
В випадку , під Φ, Ψ слід розуміти матриці перехідних та вихідних імовірностей, тобто функції, які відображають Q×X×Q та Q×X×Y в числовий проміжок (0,1) та мають відповідно смисл Ψ (qi, xj, qs) — імовірність того, що xj переводить стан qi в стан qs, Φ (qi, xj, yr) — імовірність того, що при вхідному символі xj та внутрішньому стані qi буде виданий вихідний символ yr.
Наведені поняття є достатньо загальними і не конструктивні у випадку, коли Q є нескінченним. Більш вузькі класи можуть бути виділені шляхом накладання певних обмежень на компоненти Q, X, Y, Φ, Ψ. Оскільки ці обмеження не формулюються в структурних термінах, то вони стосуються головним чином потужності алфавітів (наприклад, якщо Q скінчений, то і автомат називається скінченним) або загальних властивостей функцій Φ, Ψ.
У випадку виродження, коли той чи інший алфавіт складається з одного символу, зручніше розглядати модифіковані визначення, які отримуються при видаленні вироджених компонент. Наприклад, детермінований автомат без виходу — це трійка <Q, X, Ψ>, де Q, X, Ψ — мають звичайне значення; імовірнісний — це пара <Q, Ψ>, де Ψ — матриця перехідних імовірностей для станів з Q (тобто такий автомат є ланцюгом Маркова).
В абстрактній теорії автоматів вивчаються переважно такі концепції поведінки (див. ), в яких слова, що перетворюються або приймаються, є словами з алфавіту X (вхідні слова), а результатами перетворення або породження є слова в алфавіті Y (вихідні слова). Переважно це — реалізація операторів в автоматі та представлення множин в реальний час.
Враховуючи велику загальність та неконструктивність використовуваних визначень автомата, навіть в випадку детермінованих автоматів, оператори, що реалізуються (тобто множини, що представляються) можуть виявитись неефективними.
В абстрактній теорії автоматів основними конструктивними об'єктами для вивчення є скінченні автомати, а також реалізовані ними оператори та множини, які ними представляються (скінченно-автоматні оператори та множини). В абстрактній теорії автоматів широко застосовуються методи та поняття алгебри, математичної логіки та теорії алгоритмів.
Центральними проблемами абстрактної теорії, які породжені практичними завданнями конструювання та експлуатації обчислювальної техніки та отримали належний теоретичний розвиток, є проблеми синтезу та аналізу, а також пов'язана з ними теорія .
Аналіз та синтез автоматів
Проблема синтезу полягає в пошуку та побудові автомата, виходячи з умов, які накладаються до реалізованого ним оператора або до множини, яка ним представляється. Тут мови.
Крім того, вважається, що шуканий автомат належить до заздалегідь окресленого класу автоматів, які дозволяють конструктивний опис. Формальна мова, засобами якої здійснюється цей опис (мова виконавця), також вважається заданою. Коли мова йде про скінченні автомати, зазвичай, опис автомата полягає в представленні системи його команд шляхом графічного або табличного задання функцій Φ, Ψ (матриць перехідних та вихідних імовірностей, якщо автомат імовірнісний). Побудований в результаті абстрактного синтезу автомат може бути використаний надалі як вихідний матеріал на етапі .
В межах загальної проблеми абстрактного синтезу виникають окремі проблеми:
- Існування. Чи існує оператор, який задовольняє умові, заданій формулою U, та такою, що реалізується в автоматі даного типу?
- Одиничність. Чи одиничний такий оператор?
- Конструкція. Для якого-небудь оператора, який задовольняє умові U, побудувати автомат, який його реалізує та вказати відповідне налаштування: початковий стан, завершальні стани, а в випадку імовірнісного автомата — дозволений рівень надійності.
- Мінімізація. Побудований автомат M привести за допомогою еквівалентних перетворень до еквівалентного автомата, який задовольняє деяким критеріям оптимальності. Наприклад, в випадку скінченних автоматів — мінімізація кількості станів шляхом склеювання нерозрізнених та видалення недосяжних станів.
Розв'язання цих проблем реалізується в формі алгоритмів, які за заданою формулою U надають відповіді на запитання 1-2 та здійснюють необхідні конструкції та перетворення для проблем 3-4. Відповідна теорія істотно залежить від мов, які застосовуються замовником. Як мови виконавця зазвичай розглядаються різні класи автоматних діаграм. При обранні мови замовника природно слід керуватись такими двома (антагоністичними) вимогами: виразність мови, тобто зручність (для замовника) викладення в ньому умов, яким повинна задовольняти поведінка автомата, простота алгоритмів, які розв'язують проблему синтезу в цілому та окремі її завдання (аналогія в програмуванні — виразність вхідної мови та простота транслятора). Ця ситуація докладно вивчена в застосуванні до скінченних автоматів. З точки зору простоти алгоритмів найкращими є алгебраїчні мови (див. Регулярні події та вирази). Виразнішими є мови, які базовані на застосуванні фрагментів логіки предикатів (див. ), але й алгоритми синтезу для них стають громіздкішими.
Проблема аналізу є оберненою до проблеми синтезу: за завданим автоматом потрібно описати його поведінку засобами мови замовника. В певному сенсі аналіз та синтез можна розглядати як переклади з однієї мови на іншу, при цьому переклад, який відповідає аналізові, переважно легший.
Розроблено багато алгоритмів синтезу та аналізу, головним чином для скінченних детермінованих автоматів. Як складова частина алгоритму синтезу детермінованого автомату в нього зазвичай входить побудова недетермінованого автомата з наступним його перетворенням в еквівалентний йому детермінований автомат. Розробка алгоритмів абстрактного синтезу з застосуванням логічних мов виявилась пов'язаною з деякими алгоритмічними проблемами математичної логіки та сприяла їх вирішенню.
Алгоритми синтезу скінченних автоматів
При вирішенні завдання необхідно, з одного боку, фіксувати деякий мову, пристосовану для конструктивного опису подій, а з іншого боку — обмежитися цілком певним класом автоматів, що допускають будь-якої конструктивний спосіб завдання. Тому обмежимося лише кінцевими автоматами і регулярними подіями. Обидва ці класу об'єктів допускають конструктивний опис: перший - мовою таблиць переходів і виходів, а другий — мовою регулярних виразів алгебри подій. Таке обмеження цілком достатньо для практичних цілей, тому що цифрові автомати, з якими доводиться мати справу на практиці, завжди кінцеві.
Основний алгоритм синтезу скінчених автоматів
Нехай потрібно побудувати алгоритм, який дозволяв би за будь-якого кінцевого безлічі М регулярних подій, заданих своїми регулярними виразами, знаходити таблицю переходів і виходів кінцевого цілком певного автомата Мілі та зазначену таблицю переходів кінцевого цілком певного А таких, що всі події множини M представляються як в автоматі Мілі, так і в автоматі Мура деякими множинами їх вихідних сигналів. Перейдемо від подання подій R1, ..., Rp в автоматі Мура множинами станів до подання їх множинами вихідних сигналів. Для цього достатньо як вихідні сигнали взяти різні підмножини заданої множини подій (R1, ..., Rp) і відзначати кожне стан q автомата безліччю тих подій, які містять слова, що переводять автомат з початкового стану в стан q.
Якщо стану, не уявляють жодного із заданих подій, то вони відзначаються порожнім безліччю подій. Такий спосіб відміток станів автомата Мура називається канонічним способом відміток. Якщо вихідні для алгоритму регулярних виразів R1, ..., Rp задані регулярні події є многочленами, то вони полягають у звичайні (не ітераційні) дужки. Ця умова буде називатися умовою правильного запису регулярних виразів.
Місцями в правильно записаному регулярному виразі R над алфавітом
- X = (x1, ..., xn)
домовимося називати спеціально введені знаки розділу (вертикальні лінії), що ставляться між будь-якими двома знаками цього виразу (знаками у виразі R є букви алфавіту Х, символ порожнього слова ε, знак диз'юнкції, ітераційні і звичайні дужки). Крім цих так званих роздільних місць (знаків розділу) вводиться ще два місця - початкове і кінцеве. Перше їх них розташовується зліва від самого лівого знака виразу R, а друге - праворуч від самого правого знака.
Наприклад, R = z ∨ x {y ∨ z}, де R - регулярний вираз. Наведемо цей вираз у правильній формі
- R = (z ∨ x {y ∨ z}).
Проведемо розмітку:
- | (| Z | ∨ | x | {| y | ∨ | z |} |) | (1)
- 1 2 3 4 5 6 7 8 9 10 11.
З виразу (1) видно, що регулярний вираз R має 11 місць.
Розгорнемо дане регулярне вираз в слово, тобто послідовно, буква за буквою, випишемо небудь слово з представленого ним події. При цьому розгортання, будемо здійснювати переходячи від одного місця даного регулярного виразу до іншого і від початкового місця до кінцевого місця. Такі переходи бувають двох видів - безпосередній перехід і перехід через букву основного алфавіту Х, в якому задається репрезентована виразом подія.
Для прикладу розглянемо процеси розгортання розміченого вище вираження R в належать акредитуючій їм події слова z і xyz.
При розгортанні вираження в перше слово необхідно здійснити безпосередній перехід від початкового місця 1 до місця 2, перехід через букву z від місця 2 до місця 3 та безпосередній перехід від 3 до кінцевого місця 11.
При розгортанні вираження в слово xyz порядок переходів буде наступний: безпосередній перехід від місця 1 до місця 4 перехід через букву x - від 4 до 5, безпосередній перехід - від 5 до 6, перехід через букву у - від 6 до 7, безпосередній перехід від 7 до 10, безпосередній перехід від 10 до 8, перехід через букву z - від 8 до 9, безпосередній перехід від 9 до 10 і безпосередній перехід від 10 до 11.
Нехай R - регулярний вираз, q = xi1 xi2 ... xik довільне слово у вхідному алфавіті події, репрезентованої виразом R.
Домовимося, що місце α у вираженні R пов'язано словом q з місцем β в тому ж вираженні, якщо від місця α до місця β можна перейти за допомогою чергування будь-якого числа безпосередніх переходів і переходів через букви xi1, xi2, ..., ск слова q, взятих по одному разу в тому порядку, в якому вони входять в слово. Ця умова означає, що місце β q-слід за місцем α щоразу, коли α пов'язане з місцем β словом q.
Також домовимося говорити, що місце β підпорядковане місцем α, якщо від місця α до місцем β можна перейти за допомогою одних лише безпосередніх переходів, тобто якщо місце α пов'язане з місцем β порожнім словом ε.
Правила побудови основного алгоритму синтезу скінчених автоматів
- Задані регулярні події (число яких передбачається кінцевим) представляються правильно записаними регулярними виразами R1, ..., Rp. Все місця (як основні, так і не основні) в цих виразах позначаються вертикальними рисками (лініями).
- Кожному основним місцем у виразах приписується як індекс невід'ємне ціле число. При цьому всім початковим місцям приписується один і той же індекс (нуль). Що ж до інших основних місць, то вони нумеруються в довільному порядку натуральними числами 1, 2, ... Всі введені тут індекси називаються основними. Основні індекси підписуються під вертикальними рисами відповідних їм (основних) місць і підкреслюються знизу загальною для кожного з виразів горизонтальною розділовою рисою.
- Індекс (основний) кожного основного місця α поширюється як неосновний індекс на всі місця (як основні, так і неосновні), підлеглі місцю α, але відмінні від нього самого.
Джерела
- Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
- «Синтез цифровых автоматов», Н. Г. Захаров, В. Н. Рогов, Ульяновск 2003.
Див. також
Цю статтю треба для відповідності Вікіпедії. (грудень 2013) |
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Abstraktna teoriya avtomativ napryam v teoriyi avtomativ yakij harakterizuyetsya tim sho pri vivchenni avtomativ ne berut do uvagi yih strukturni osoblivosti Za takogo pidhodu vnutrishni stani avtomata jogo vhidni ta vihidni signali rozglyadayutsya yak deyaki abstraktni simvoli yaki utvoryuyut vidpovidno alfaviti Q vnutrishnij X vhidnij Y vihidnij X ta Y vvazhayutsya skinchenimi alfavitami Q mozhe buti neskinchennim Ponyattya abstraktnoyi teoriyi avtomativDeterminovanij avtomat viznachayetsya yak kortezh M lt Q X Y F PS gt de funkciya perehodiv PS vidobrazhaye dekartiv dobutok Q X v Q a funkciya vihodiv F vidobrazhaye Q X v Y Nedeterminovanij avtomat viznachayetsya analogichno ale z toyu rizniceyu sho yak F PS dopuskayutsya bagatoznachni funkciyi V vipadku pid F PS slid rozumiti matrici perehidnih ta vihidnih imovirnostej tobto funkciyi yaki vidobrazhayut Q X Q ta Q X Y v chislovij promizhok 0 1 ta mayut vidpovidno smisl PS qi xj qs imovirnist togo sho xj perevodit stan qi v stan qs F qi xj yr imovirnist togo sho pri vhidnomu simvoli xj ta vnutrishnomu stani qi bude vidanij vihidnij simvol yr Navedeni ponyattya ye dostatno zagalnimi i ne konstruktivni u vipadku koli Q ye neskinchennim Bilsh vuzki klasi mozhut buti vidileni shlyahom nakladannya pevnih obmezhen na komponenti Q X Y F PS Oskilki ci obmezhennya ne formulyuyutsya v strukturnih terminah to voni stosuyutsya golovnim chinom potuzhnosti alfavitiv napriklad yaksho Q skinchenij to i avtomat nazivayetsya skinchennim abo zagalnih vlastivostej funkcij F PS U vipadku virodzhennya koli toj chi inshij alfavit skladayetsya z odnogo simvolu zruchnishe rozglyadati modifikovani viznachennya yaki otrimuyutsya pri vidalenni virodzhenih komponent Napriklad determinovanij avtomat bez vihodu ce trijka lt Q X PS gt de Q X PS mayut zvichajne znachennya imovirnisnij ce para lt Q PS gt de PS matricya perehidnih imovirnostej dlya staniv z Q tobto takij avtomat ye lancyugom Markova V abstraktnij teoriyi avtomativ vivchayutsya perevazhno taki koncepciyi povedinki div v yakih slova sho peretvoryuyutsya abo prijmayutsya ye slovami z alfavitu X vhidni slova a rezultatami peretvorennya abo porodzhennya ye slova v alfaviti Y vihidni slova Perevazhno ce realizaciya operatoriv v avtomati ta predstavlennya mnozhin v realnij chas Vrahovuyuchi veliku zagalnist ta nekonstruktivnist vikoristovuvanih viznachen avtomata navit v vipadku determinovanih avtomativ operatori sho realizuyutsya tobto mnozhini sho predstavlyayutsya mozhut viyavitis neefektivnimi V abstraktnij teoriyi avtomativ osnovnimi konstruktivnimi ob yektami dlya vivchennya ye skinchenni avtomati a takozh realizovani nimi operatori ta mnozhini yaki nimi predstavlyayutsya skinchenno avtomatni operatori ta mnozhini V abstraktnij teoriyi avtomativ shiroko zastosovuyutsya metodi ta ponyattya algebri matematichnoyi logiki ta teoriyi algoritmiv Centralnimi problemami abstraktnoyi teoriyi yaki porodzheni praktichnimi zavdannyami konstruyuvannya ta ekspluataciyi obchislyuvalnoyi tehniki ta otrimali nalezhnij teoretichnij rozvitok ye problemi sintezu ta analizu a takozh pov yazana z nimi teoriya Analiz ta sintez avtomativProblema sintezu polyagaye v poshuku ta pobudovi avtomata vihodyachi z umov yaki nakladayutsya do realizovanogo nim operatora abo do mnozhini yaka nim predstavlyayetsya Tut movi Krim togo vvazhayetsya sho shukanij avtomat nalezhit do zazdalegid okreslenogo klasu avtomativ yaki dozvolyayut konstruktivnij opis Formalna mova zasobami yakoyi zdijsnyuyetsya cej opis mova vikonavcya takozh vvazhayetsya zadanoyu Koli mova jde pro skinchenni avtomati zazvichaj opis avtomata polyagaye v predstavlenni sistemi jogo komand shlyahom grafichnogo abo tablichnogo zadannya funkcij F PS matric perehidnih ta vihidnih imovirnostej yaksho avtomat imovirnisnij Pobudovanij v rezultati abstraktnogo sintezu avtomat mozhe buti vikoristanij nadali yak vihidnij material na etapi V mezhah zagalnoyi problemi abstraktnogo sintezu vinikayut okremi problemi Isnuvannya Chi isnuye operator yakij zadovolnyaye umovi zadanij formuloyu U ta takoyu sho realizuyetsya v avtomati danogo tipu Odinichnist Chi odinichnij takij operator Konstrukciya Dlya yakogo nebud operatora yakij zadovolnyaye umovi U pobuduvati avtomat yakij jogo realizuye ta vkazati vidpovidne nalashtuvannya pochatkovij stan zavershalni stani a v vipadku imovirnisnogo avtomata dozvolenij riven nadijnosti Minimizaciya Pobudovanij avtomat M privesti za dopomogoyu ekvivalentnih peretvoren do ekvivalentnogo avtomata yakij zadovolnyaye deyakim kriteriyam optimalnosti Napriklad v vipadku skinchennih avtomativ minimizaciya kilkosti staniv shlyahom skleyuvannya nerozriznenih ta vidalennya nedosyazhnih staniv Rozv yazannya cih problem realizuyetsya v formi algoritmiv yaki za zadanoyu formuloyu U nadayut vidpovidi na zapitannya 1 2 ta zdijsnyuyut neobhidni konstrukciyi ta peretvorennya dlya problem 3 4 Vidpovidna teoriya istotno zalezhit vid mov yaki zastosovuyutsya zamovnikom Yak movi vikonavcya zazvichaj rozglyadayutsya rizni klasi avtomatnih diagram Pri obranni movi zamovnika prirodno slid keruvatis takimi dvoma antagonistichnimi vimogami viraznist movi tobto zruchnist dlya zamovnika vikladennya v nomu umov yakim povinna zadovolnyati povedinka avtomata prostota algoritmiv yaki rozv yazuyut problemu sintezu v cilomu ta okremi yiyi zavdannya analogiya v programuvanni viraznist vhidnoyi movi ta prostota translyatora Cya situaciya dokladno vivchena v zastosuvanni do skinchennih avtomativ Z tochki zoru prostoti algoritmiv najkrashimi ye algebrayichni movi div Regulyarni podiyi ta virazi Viraznishimi ye movi yaki bazovani na zastosuvanni fragmentiv logiki predikativ div ale j algoritmi sintezu dlya nih stayut gromizdkishimi Problema analizu ye obernenoyu do problemi sintezu za zavdanim avtomatom potribno opisati jogo povedinku zasobami movi zamovnika V pevnomu sensi analiz ta sintez mozhna rozglyadati yak perekladi z odniyeyi movi na inshu pri comu pereklad yakij vidpovidaye analizovi perevazhno legshij Rozrobleno bagato algoritmiv sintezu ta analizu golovnim chinom dlya skinchennih determinovanih avtomativ Yak skladova chastina algoritmu sintezu determinovanogo avtomatu v nogo zazvichaj vhodit pobudova nedeterminovanogo avtomata z nastupnim jogo peretvorennyam v ekvivalentnij jomu determinovanij avtomat Rozrobka algoritmiv abstraktnogo sintezu z zastosuvannyam logichnih mov viyavilas pov yazanoyu z deyakimi algoritmichnimi problemami matematichnoyi logiki ta spriyala yih virishennyu Algoritmi sintezu skinchennih avtomativPri virishenni zavdannya neobhidno z odnogo boku fiksuvati deyakij movu pristosovanu dlya konstruktivnogo opisu podij a z inshogo boku obmezhitisya cilkom pevnim klasom avtomativ sho dopuskayut bud yakoyi konstruktivnij sposib zavdannya Tomu obmezhimosya lishe kincevimi avtomatami i regulyarnimi podiyami Obidva ci klasu ob yektiv dopuskayut konstruktivnij opis pershij movoyu tablic perehodiv i vihodiv a drugij movoyu regulyarnih viraziv algebri podij Take obmezhennya cilkom dostatno dlya praktichnih cilej tomu sho cifrovi avtomati z yakimi dovoditsya mati spravu na praktici zavzhdi kincevi Osnovnij algoritm sintezu skinchenih avtomativ Nehaj potribno pobuduvati algoritm yakij dozvolyav bi za bud yakogo kincevogo bezlichi M regulyarnih podij zadanih svoyimi regulyarnimi virazami znahoditi tablicyu perehodiv i vihodiv kincevogo cilkom pevnogo avtomata Mili ta zaznachenu tablicyu perehodiv kincevogo cilkom pevnogo A takih sho vsi podiyi mnozhini M predstavlyayutsya yak v avtomati Mili tak i v avtomati Mura deyakimi mnozhinami yih vihidnih signaliv Perejdemo vid podannya podij R1 Rp v avtomati Mura mnozhinami staniv do podannya yih mnozhinami vihidnih signaliv Dlya cogo dostatno yak vihidni signali vzyati rizni pidmnozhini zadanoyi mnozhini podij R1 Rp i vidznachati kozhne stan q avtomata bezlichchyu tih podij yaki mistyat slova sho perevodyat avtomat z pochatkovogo stanu v stan q Yaksho stanu ne uyavlyayut zhodnogo iz zadanih podij to voni vidznachayutsya porozhnim bezlichchyu podij Takij sposib vidmitok staniv avtomata Mura nazivayetsya kanonichnim sposobom vidmitok Yaksho vihidni dlya algoritmu regulyarnih viraziv R1 Rp zadani regulyarni podiyi ye mnogochlenami to voni polyagayut u zvichajni ne iteracijni duzhki Cya umova bude nazivatisya umovoyu pravilnogo zapisu regulyarnih viraziv Miscyami v pravilno zapisanomu regulyarnomu virazi R nad alfavitom X x1 xn domovimosya nazivati specialno vvedeni znaki rozdilu vertikalni liniyi sho stavlyatsya mizh bud yakimi dvoma znakami cogo virazu znakami u virazi R ye bukvi alfavitu H simvol porozhnogo slova e znak diz yunkciyi iteracijni i zvichajni duzhki Krim cih tak zvanih rozdilnih misc znakiv rozdilu vvoditsya she dva miscya pochatkove i kinceve Pershe yih nih roztashovuyetsya zliva vid samogo livogo znaka virazu R a druge pravoruch vid samogo pravogo znaka Napriklad R z x y z de R regulyarnij viraz Navedemo cej viraz u pravilnij formi R z x y z Provedemo rozmitku Z x y z 1 1 2 3 4 5 6 7 8 9 10 11 Z virazu 1 vidno sho regulyarnij viraz R maye 11 misc Rozgornemo dane regulyarne viraz v slovo tobto poslidovno bukva za bukvoyu vipishemo nebud slovo z predstavlenogo nim podiyi Pri comu rozgortannya budemo zdijsnyuvati perehodyachi vid odnogo miscya danogo regulyarnogo virazu do inshogo i vid pochatkovogo miscya do kincevogo miscya Taki perehodi buvayut dvoh vidiv bezposerednij perehid i perehid cherez bukvu osnovnogo alfavitu H v yakomu zadayetsya reprezentovana virazom podiya Dlya prikladu rozglyanemo procesi rozgortannya rozmichenogo vishe virazhennya R v nalezhat akredituyuchij yim podiyi slova z i xyz Pri rozgortanni virazhennya v pershe slovo neobhidno zdijsniti bezposerednij perehid vid pochatkovogo miscya 1 do miscya 2 perehid cherez bukvu z vid miscya 2 do miscya 3 ta bezposerednij perehid vid 3 do kincevogo miscya 11 Pri rozgortanni virazhennya v slovo xyz poryadok perehodiv bude nastupnij bezposerednij perehid vid miscya 1 do miscya 4 perehid cherez bukvu x vid 4 do 5 bezposerednij perehid vid 5 do 6 perehid cherez bukvu u vid 6 do 7 bezposerednij perehid vid 7 do 10 bezposerednij perehid vid 10 do 8 perehid cherez bukvu z vid 8 do 9 bezposerednij perehid vid 9 do 10 i bezposerednij perehid vid 10 do 11 Nehaj R regulyarnij viraz q xi1 xi2 xik dovilne slovo u vhidnomu alfaviti podiyi reprezentovanoyi virazom R Domovimosya sho misce a u virazhenni R pov yazano slovom q z miscem b v tomu zh virazhenni yaksho vid miscya a do miscya b mozhna perejti za dopomogoyu cherguvannya bud yakogo chisla bezposerednih perehodiv i perehodiv cherez bukvi xi1 xi2 sk slova q vzyatih po odnomu razu v tomu poryadku v yakomu voni vhodyat v slovo Cya umova oznachaye sho misce b q slid za miscem a shorazu koli a pov yazane z miscem b slovom q Takozh domovimosya govoriti sho misce b pidporyadkovane miscem a yaksho vid miscya a do miscem b mozhna perejti za dopomogoyu odnih lishe bezposerednih perehodiv tobto yaksho misce a pov yazane z miscem b porozhnim slovom e Pravila pobudovi osnovnogo algoritmu sintezu skinchenih avtomativ Zadani regulyarni podiyi chislo yakih peredbachayetsya kincevim predstavlyayutsya pravilno zapisanimi regulyarnimi virazami R1 Rp Vse miscya yak osnovni tak i ne osnovni v cih virazah poznachayutsya vertikalnimi riskami liniyami Kozhnomu osnovnim miscem u virazah R 1 R p displaystyle R 1 ldots R p pripisuyetsya yak indeks nevid yemne cile chislo Pri comu vsim pochatkovim miscyam pripisuyetsya odin i toj zhe indeks nul Sho zh do inshih osnovnih misc to voni numeruyutsya v dovilnomu poryadku naturalnimi chislami 1 2 Vsi vvedeni tut indeksi nazivayutsya osnovnimi Osnovni indeksi pidpisuyutsya pid vertikalnimi risami vidpovidnih yim osnovnih misc i pidkreslyuyutsya znizu zagalnoyu dlya kozhnogo z viraziv R 1 R p displaystyle R 1 ldots R p gorizontalnoyu rozdilovoyu risoyu Indeks osnovnij kozhnogo osnovnogo miscya a poshiryuyetsya yak neosnovnij indeks na vsi miscya yak osnovni tak i neosnovni pidlegli miscyu a ale vidminni vid nogo samogo DzherelaEnciklopediya kibernetiki u 2 t za red V M Glushkova Kiyiv Gol red Ukrayinskoyi radyanskoyi enciklopediyi 1973 Sintez cifrovyh avtomatov N G Zaharov V N Rogov Ulyanovsk 2003 Div takozhPortal Matematika Teoriya avtomativ Avtomatni vidobrazhennya Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti gruden 2013 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi