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

-

 

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


 

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

14543. ЕДИНАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ ПОЛИТИКА ЕВРОПЕЙСКОГО СОЮЗА 43.99 KB
  Единая сельскохозяйственная политика Европейского Союза Оглавление Введение2 1. Необходимость и Цели ЕСХП2 2. Начало ЕСХП4 3. Современные реформы ЕСХП5 4. Реформа Сахарного Режима 2005 – 20066 Введение Единая Сельскохозяйственная Политика ЕСХП Евро
14544. Шенгенские соглашения 24.59 KB
  Шенгенские соглашения 1.Общая характеристика Шенгенских соглашений 2.Шенгенское соглашение 1985 г. 3.Шенгенская конвенция 1990 г. 1.Общая характеристика Шенгенских соглашений Шенгенские соглашения система из двух договоров которые были подписаны во второй полови
14545. Образование Европейских сообществ 33.75 KB
  Образование Европейских Сообществ 1. Парижский договор 1951 года и создание Европейского Объединения Угля и Стали1 2. Римский договор 1957 года и создание ЕЭС3 3. Попытка создания сообщества по безопасности и его провал7 4. Римский договор 1957 года и создание Европейского ...
14546. Особенности интеграции в Североамериканском регионе 18.72 KB
  Особенности интеграции в Североамериканском регионе Вся территория Северной Америки является зоной свободной торговли называемой официально Североамериканским Соглашением о Свободной Торговле €œNorth American Free Trade Area€ – НАФТА. В неё входят: США Канада и Мексика. Функц...
14547. ПАРИЖСКИЙ ДОГОВОР 1951 ГОДА И СОЗДАНИЕ ЕВРОПЕЙСКОГО ОБЪЕДИНЕНИЯ УГЛЯ И СТАЛИ 22.04 KB
  Парижский договор 1951 года и создание Европейского Объединения Угля и Стали Парижский Договор был подписан 18 апреля 1951 года вступил в силу 1 января 1952 года. Он положил начало созданию первого интеграционного объединения в Западной Европе – Европейского Объединения Угля ...
14548. УГЛУБЛЕНИЕ И РАСШИРЕНИЕ ЗАПАДНОЕВРОПЕЙСКОЙ ИНТЕГРАЦИИ 18.63 KB
  Углубление и расширение Западноевропейской интеграции Середина 1968 года. На 15 года раньше намеченного срока – завершение создания таможенного союза. 1971 год. Принятие плана Вернера премьерминистра Люксембурга. По его плану намечалось создание к 1980 году экономическог...
14549. ОТ ЕВРОПЕЙСКИХ СООБЩЕСТВ К ЕДИНОМУ ЕВРОПЕЙСКОМУ АКТУ. УГЛУБЛЕНИЕ ЗАПАДНОЕВРОПЕЙСКОЙ ИНТЕГРАЦИИ 31.16 KB
  От Европейских сообществ к единому Европейскому акту. Углубление Западноевропейской интеграции. Оглавление 1. Брюссельский договор 1965 года1 2. Первое расширение ЕЭС2 3. Углубление и расширение Западноевропейской интеграции3 4. Единый Европейский Акт ЕЕА5 1. Бр...
14550. ОБРАЗОВАНИЕ ЕВРОПЕЙСКИХ СООБЩЕСТВ 51.85 KB
  Образование Европейских Сообществ Оглавление 1. Парижский договор 1951 года и создание Европейского Объединения Угля и Стали1 2. Римский договор 1957 года и создание ЕЭС3 3. Попытка создания сообщества по безопасности и его провал7 4. Римский договор 1957 года и создание
14551. МААСТРИХТСКИЙ ДОГОВОР. СОЗДАНИЕ ЕВРОПЕЙСКОГО СОЮЗА 28.63 KB
  Маастрихтский Договор. Создание Европейского Союза. Оглавление 1. Роль правительственных конференций в подготовке Маастрихтского договора1 2. Основные положения договора о Европейском Союзе1 3. Три опоры Европейского Союза. Единое Общеевропейское Гражданство1 4...