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

-

 

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


 

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

3125. Расчет режима резания при фрезеровании 43 KB
  Расчет режима резания при фрезеровании Цель работы: Изучить методику назначения режима резания по таблицам нормативов. Ознакомиться и приобрести навыки работы с нормативами. Задание: На горизонтально-фрезерном станке 6Р82Г,производиться ...
3126. Адвокатура, общественные и частные правоохранительные органы 93 KB
  Адвокатура, общественные и частные правоохранительные органы ВВЕДЕНИЕ. Адвокатура - это добровольное профессиональное объединение граждан, осуществляющее в установленном законом порядке защиту на предварительном следствии, дознании, в суде по уголов...
3127. Потенциал предприятия: формирование и оценка 433 KB
  Теоретическая часть Сравнительный подход в оценке недвижимости и его методы: компании-аналог а, сделок отраслевых коэффициентов. Понятие ценовых мультипликаторов и их виды Сравнительный подход эффективен в случае существования активного рынка с...
3128. Анализ платежеспособных предприятий и разработка методов финансовой санации 268.5 KB
  Введение Финансово-устойчивым является такой хозяйствующий субъект, который за счет собственных средств покрывает средства, вложенные в активы (основные фонды, нематериальные активы, оборотные средства), не допускает неоправданной дебиторской и кред...
3129. Безопасности Жизнедеятельность и Промышленной Экологии 64.5 KB
  Введение Как и всякая отрасль науки экология имеет свои законы,  которые характеризуют взаимоотношение, различных элементов экосистемы и, в конечном итоге, все процессы в биосфере. К сожалению, по сей день не стало доминирующим и безусловным по...
3130. Малый бизнес в России на современном этапе его развития 404 KB
  Современное российское общество переживает чрезвычайно сильный кризис, который проявляется в политике, экономике, идеологии и других сферах жизни общества. Россия в очередной раз стоит перед необходимостью выбора ориентиров для своего дальнейшего развития, и здесь нельзя ошибиться.
3131. Монтаж строительных конструкций 106 KB
  Введение В курсовой работе описываются строительно-монтажные работы по возведению одноэтажного промышленного здания, каркас которого состоит из металлических конструктивных элементов. Условно принято, что нулевой цикл работ уже завершен. Монтаж веде...
3132. Планирование многофакторных экспериментов 207 KB
  Введение Исследование является экспериментом, если входные переменные изменяются исследователем в точно учитываемых условиях, позволяя управлять ходом опытов и воссоздавать их результаты каждый раз при повторении с точностью до случайных ошибок. П...
3133. Приводная станция подвесного конвейера 268 KB
  Техническое задание Приводная станция подвесного конвейера. Исходные данные. Тяговая сила цепи F = 3,0 кН Скорость грузовой цепи v = 0,55 м/с Шаг грузовой цепи p = 80 мм Число зубьев звездочки  Z = 7 Срок службы привода L = 10 лет...