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

-

 

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


 

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

42781. Розрахунок електричних навантажень силової мережі 4.67 MB
  Електроенергетичній галузі притаманні специфічні особливості, зумовлені одноманітністю вироблення і споживання енергії, надзвичайно складним технологічним циклом її одержання, необхідністю централізованого диспетчерського оперативно-технологічного керування всім комплексом у цілому, забезпечення надійності і безпеки функціонування обладнання. Все це робить енергетику надзвичайно матеріалоємною, енергоємною галуззю, з великим інвестиційним циклом і, що дуже важливо, — інтелектуально і наукоємною.
42782. Загрози національній безпеці України на сучасному етапі 72.68 KB
  Теоретичні та нормативноправові основи національної безпеки України. Основні ризики і загрози національній безпеці України. Зовнішні і внутрішні загрози національній безпеці України.
42783. Розрахунок геометричних розмірів та втрат тепла теплової мережі, яка складається з котла теплотраси та теплообмінного апарату 743.07 KB
  Теплообмін – це енергетичний обмін між об’єктами, які взаємодіють між собою в системі, що розглядаються, необхідною і достатньою умовою якої є різниця температур даних областей. Місцевим результатом теплообміну є вирівнювання різниці температур
42784. Методология и методика социологического исследования 116.79 KB
  Теоретико-методологические основы социологического анализа социального самочувствия Показатели и способы изучения социального самочувствия 14 Опыт исследования социального самочувствия
42785. Создание венецианской маски в 3Ds Mx 3.3 MB
  Например это: Рисунок 1Бокал Очевидно что бокал имеет ось симметрии и его можно получить вращая сплайн. Создаём Plneплоскость в окне Front и присваиваем ей материал с данной текстурой бокала получаем такой результат: Рисунок 2заготовка Plne Обводим контур нашего бокала только половину. Должен получиться подобный сплайн: Рисунок 3 На рисунке 3 отмечены две точки начало и конец сплайна. Модель бокала в перспективе должна выглядеть примерно так...
42786. Монетарная политика в рыночной системе и функции Центрального Банка 2.99 MB
  Основные концепции денежнокредитной политики государства. Неоклассическая теория как одна из основ денежнокредитного регулирования. Кейнсианская теория денежнокредитного регулирования. Неоконсервативный подход монетаризм в денежнокредитном регулировании.
42787. Автоматические промышленные средства испытаний изделий на прочность и надежность при воздействии линейных ускорений 521.59 KB
  Точность поддержания ускорения существенно влияет на выбор конструкции и определяет точность изготовления отдельных узлов центрифуги. Факторы влияющие на измерение: изменение температуры окружающей среды отклонение стола от горизонтальной плоскости скорость нарастания ускорения изменение ускорения по площади изделия вибрация возникающая в системе привода центрифуги изменение длины плеча при изменении скорости центрифуги. В процессе разгона центрифуги кроме центробежных сил определяющих линейное ускорение возникают силы инерции...
42788. ПРОФИЛЬ ДОРОЖНОЙ ТРАССЫ. ПОСТРОЕНИЕ ПРОФИЛЯ ДОРОЖНОЙ ТРАССЫ 202.05 KB
  Вычисление координат пунктов замкнутого теодолитного хода. Вычисление координат вершин диагонального теодолитного хода. Вычисление отметок съёмочных точек замкнутого хода. Построение прямоугольной сетки и теодолитного хода Нанесение на план съемочных пикетов пикетных точек.
42789. Анализ и диагностика финансово-хозяйственной деятельности предприятия ОАО «ТНК-ВР Холдинг» 119.62 KB
  Орджоникидзе Кафедра Управление предприятиями МСК Курсовая работа по дисциплине Анализ и диагностика финансовохозяйственной деятельности предприятия на тему: Анализ и диагностика финансовохозяйственной деятельности предприятия ОАО ТНКВР Холдинг Выполнила: студентка группы ЭГ09 Тутарова...