22118

Абстрактный синтез конечных автоматов

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Составить аналогичную таблицу описывающую работу конечного автомата не представляется возможным т. множество допустимых входных слов автомата вообще говоря бесконечно. Мы рассмотрим один из возможных способов формального задания автоматов а именно задание автомата на языке регулярных событий. Представление событий в автоматах.

Русский

2013-08-04

25.5 KB

11 чел.

Лекция 4

Абстрактный синтез конечных автоматов.

При синтезе комбинационных схем можно составить таблицу зависимости значения выходного сигнала от комбинации входных. Такая таблица однозначно определяет систему ПФ, описывающую работу КС.

 Составить аналогичную таблицу, описывающую работу конечного автомата, не представляется возможным, т.к. множество допустимых входных слов автомата, вообще говоря, бесконечно. Поэтому для задания КА и используются таблицы переходов и выходов, которые позволяют представить соответствие между бесконечными множествами входных и выходных слов конечными таблицами. В связи с этим, прежде чем приступить к синтезу схемы КА необходимо составить таблицу переходов и выходов, что не всегда является простым делом особенно в тех случаях, когда алгоритм работы автоматов задан в описательной форме. Для того, чтобы упростить и формализовать процедуру построения таблиц переходов и выходов необходимо ввести такую исходную форму задания автоматов, переход к которой от алгоритмов, сформулированных в описательной форме, не представляет трудностей. Мы рассмотрим один из возможных способов формального задания автоматов, а именно, задание автомата на языке регулярных событий.

Представление событий в автоматах.

В основе рассматриваемого  способа задания автоматов, лежит понятие событий, представимых в автоматах.

 Определение. Событием называют любое множество слов входного алфавита X {x1, x2, …,xm} автомата.

Пусть Y{y1, y2, …, yk} – выходной алфавит конечного автомата S с фиксированным начальным состоянием a0. Тогда каждой букве yj, выходного алфавита можно поставить в соответствие множество входных слов Sj(x1, x2,…, xm), которые вызывают появление на выходе автомата буквы yj. Определенное таким образом множество слов Sj(x1, x2, …, xm) называют событием, представленным в автомате выходным сигналом yj.

Поэтому для задания конечного автомата, имеющего выходной алфавит Y{y1, y2, …, yk}, достаточно разбить множество всех возможных входных слов на K событий S1, S2, …, Sk, представленных в автомате выходными сигналами y1, y2, …, yk соответственно. Для частичного автомата необходимо, кроме того, задать множество Sз запрещенных слов. Таким образом, конечный автомат может быть задан таблицей, устанавливающей соответствия между событиями и буквами выходного алфавита. Зная набор событий Sj, можно, не пользуясь таблицами переходов и выходов, найти реакцию автомата на любое входное слово, для чего достаточно определить в множество каких слов входного алфавита оно входит (т.е. какому событию принадлежит).

Событие

буква выходного алфавита

S1(x1, x2,…, xm)

S2(x1, x2,…, xm)

Sk(x1, x2,…, xm)

S(x1, x2,…, xm)

y1

y2

yk

-

 

 Для описания автоматов на языке регулярных событий вводят ряд операций над событиями, т.е. строят алгебру событий. Мы рассмотрим алгебру событий, введенную Клини и усовершенствованную академиком Глушковым В. М.


 

А также другие работы, которые могут Вас заинтересовать

83584. Міжнародна організація цивільної авіації 36.37 KB
  Міжнародна організація цивільної авіації ІКАО була створена відповідно до Конвенції про міжнародну цивільну авіацію 1944 р.: забезпечувати безпечний і впорядкований розвиток міжнародної цивільної авіації в усьому світі; заохочувати мистецтво конструювання й експлуатації повітряних суден у мирних цілях; заохочувати розвиток повітряних трас аеропортів і аеронавігаційних засобів для міжнародної цивільної авіації; задовольняти потреби народів світу у безпечному регулярному ефективному й економічному повітряному транспорті; запобігати...
83585. Правовий режим повітряного простору. Свобода повітря 37.43 KB
  Згідно з принципом свободи польотів у міжнародному повітряному просторі повітряні судна підпорядковуються в даній сфері юрисдикції держави прапору держави реєстрації Порядок реєстрації повітряних суден визначається внутрішнім правом. Держави зобов\'язані здійснювати контроль за відповідністю зареєстрованих в них повітряних суден вимогам безпеки польотів та за дотриманням ними міжнародних норм. Юрисдикція держави у власному повітряному просторі визначається її територіальним верховенством. Повітряний простір є частиною території держави.
83586. Боротьба з актами незаконного втручання у діяльність цивільної авіації 32.4 KB
  містить цілий ряд статей що відносяться до повітряного піратства під яким розуміють будьякий неправомірний акт насильства затримання що здійснюється в особистих цілях екіпажем або пасажирами приватного літального апарату. У міжнародному просторі урядові судна будьякої держави можуть захопити піратський літальний апарат заарештувати осіб що захопили його та віддати суду своєї держави. Будьяка держава зобов’язана або судити або видавати осіб що скоїли їх.
83587. Поняття і принципи міжнародного космічного права 35.11 KB
  Його основними джерелами є: Договір про принципи діяльності держав з дослідження та використання космічного простору включаючи Місяць та інші небесні тіла 1967 р. Угода про діяльність держав на Місяці та інших небесних тілах 1979 р. Принципи міжнародного космічного права закріплені у Договорі про принципи діяльності держав з дослідження та використання космічного простору включаючи Місяць та інші небесні тіла 1967 р. До них відносяться: дослідження та використання космосу на благо всього людства; рівне право всіх держав на дослідження та...
83588. Правовий режим космічного простору і небесних тіл 35.9 KB
  Розмежування повітряного простору держав на який поширюється їх суверенітет та відкритого космічного простору проходить на висоті 100110 км над рівнем Світового океану. Основоположною особливістю сучасного правового статусу космічного простору та небесних тіл є їх міжнародноправова кваліфікація як надбання всього людства. встановлює що ніяка частина космічного простору включаючи небесні тіла не підлягає національному привласненню ані шляхом проголошення над ними суверенітету ані шляхом використання або окупації; ані будьякими...
83589. Правовий режим космічних обєктів і екіпажів 37.05 KB
  Згідно з Конвенцією про реєстрацію об\'єктів що запускаються В космічний простір 1975 р. держава що здійснює такий запуск реєструє космічний об\'єкт у національному реєстрі. Кожна запускаюча держава представляє Генеральному секретарю ООН у найкоротший строк необхідну інформацію про кожний космічний об\'єкт занесений в її реєстр.
83590. Відповідальність у міжнародному космічному праві 35.62 KB
  Держави несуть міжнародну відповідальність за національну діяльність у космічному просторі включаючи Місяць та інші небесні тіла незалежно від того чи здійснюється вона урядовими органами або неурядовими юридичними особами. У випадку діяльності в космічному просторі включаючи Місяць та інші небесні тіла міжнародної організації відповідальність за виконання Договору про космос несуть разом з міжнародною організацією також і держави що беруть у ній участь. Держава що здійснює або організує запуск об\\\'єкта в космос а також кожна...
83591. Поняття і принципи міжнародного економічного права. Джерела міжнародного економічного права 37.61 KB
  Сучасна практика свідчить, що основну частину МЕП складають норми, що регулюють міждержавні економічні відносини. Так, норми, спрямовані на регулювання правовідносин за участю фізичних та юридичних осіб, переважно регулюють відповідні...
83592. Сучасна система міжнародних економічних організацій 39.05 KB
  На універсальному рівні основними організаціями є ООН її спеціалізовані установи і СОТ. Незважаючи на важливу роль ООН в регулюванні міжнародних економічних відносиносновну роботу з розробки універсальних стандартів в галузі МЕП сьогодні здійснюють МВФ Група Світового банку та СОТ. СОТ була створена в 1994 р. Установчим документом СОТ є Марракешська угода про заснування СОТ 1994 р.