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

-

 

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


 

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

618. Исследование многоканальной системы передачи информации с нелинейным уплотнением каналов 56 KB
  Функциональная схема макета. Нелинейное уплотнение каналов. Используются адресные функции значности. Многоканальная система передачи информации.
619. Неврозы у детей и подростков 143.5 KB
  Невротические реакции. Невротические расстройства. Ипохондрический невроз. Истерический невроз. Астенический невроз (неврастения). Невроз навязчивых состояний (обсессивно-компульсивное расстройство). Системные неврозы. Невротические расстройства у детей раннего возраста. Механизмы социальной и школьной дизадаптации, профилактика и коррекция при невротических расстройствах в дошкольном и школьном возрасте.
620. Особенности невербальных средств общения 62.5 KB
  Познакомить педагогов с основными формами невербальной коммуникации. Разобрать с педагогами значение некоторых проявлений невербальной коммуникации. Способствовать развитию педагогической интуиции.
621. Расчет привода цепного транспортёра 273 KB
  Расчёт быстроходного вала (расчёт на статическую прочность). Расчет тихоходного вала (расчёт на статическую и усталостную прочность). Расчет шпоночного соединения. Выбор смазки редуктора. Расчет предохранительного устройства.
622. Разрушение горных пород взрывом 45.5 KB
  Понятие о взрыве и взрывчатом веществе. Кислородный баланс. Определение основных констант взрыва и давления продуктов детонации. Давление продуктов взрыва на стенки зарядной камеры. Определение количества теплоты, выделяющейся при взрыве ВВ.
623. Экологический менеджмент и его функции 145.5 KB
  Функции, инфраструктура и принципы экологического менеджмента. Активное сотрудничество со всеми заинтересованными в экологических аспектах деятельности предприятия лицами и сторонами. Организация потоков загрязняющих веществ и отходов.
624. Совместная обработка нескольких рядов наблюдений 143 KB
  Получить практические навыки проведения экспериментальных исследований по определению метрологических характеристик средств измерений. Оценить равнорассеянность результатов нескольких серий наблюдений.
625. Практика проведения денежных реформ в странах Западной Европы 150 KB
  Денежные реформы Англии и выход из стерлинговых кризисов. Современное положение денежнной системы западноевропейских стран. Значение денежных реформ в развитии денежных систем. Средство выхода из кризисисного состояния и продолжения нормального функционирования национального хозяйства в целом.
626. Дефицитарность общения в детском и подростковом возрасте 154 KB
  Задачи медико-педагогической коррекции при дефицитарнсти общения у детей и подростков. Условия коррекционной работы в лечебно-педагогическом центре. Малая коррекционная группа. Особенности семей детей с дефицитарностью общения. Социально-психологическая работа с семьей аутичного ребенка.