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

-

 

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


 

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

12508. Тұрақты токта физикалық шамаларды өлшеу (өлшеу аспабымен танысу – мультиметрмен) 102.75 KB
  1 Лабораториялық жұмыс. Тұрақты токта физикалық шамаларды өлшеу өлшеу аспабымен танысу мультиметрмен 3.1 Жұмыстың мақсаты: Тұрақты токтағы электрлік кернеу ток қуат кедергіні өлшеу принципін тәсілдерін және әдістерін оқып үйрену метрологиялық өңдеу әдістерін
12509. Формулалар бойынша есептеулер 76 KB
  №2 лабораториялық жұмыс Тақырыбы: Формулалар бойынша есептеулер. 1.Берілгені: Берілген n бүтін және x нақты сандары үшін берілген өрнекті есептеу алгоритмінің блоксхемасын және программасын құру. Өрнектердің мәні циклдік операторлар көмегімен есептеледі. Пр...
12510. Лабораториялық жұмыс. Кернеу мен токты бөлгіштер 34.84 KB
  2 Лабораториялық жұмыс. Кернеу мен токты бөлгіштер 1 Жұмыстың мақсаты: Кернеу мен токты бөлгіштердің жұмыс істеу принципімен танысу. Кернеу мен токты бөлу шарттарын қолданып кернеудің мәнін есептеу және өлшеу арқылы кернеуді бөлудің шартын принцип дәлелдеу. Кернеу ме...
12511. Бұрамды бәсеңдеткіштер классификациясымен, кинематикалық сұлбасымен, байланыстары мен бөлшектерімен танысу 1.31 MB
  №15 Зертханалық жұмыс Бұрамды бәсеңдеткіштер классификациясымен кинематикалық сұлбасымен байланыстары мен бөлшектерімен танысу. Жұмыстың мақсаты: Барлық бөлшектердің қызметін анықтау Ілініс параметрлерін анықтау Бәсеңдеткішті жинау барысында байл...
12512. Өрістік транзистор негізіндегі кең жолақты күшейткіштің резисторлы каскадын зерттеу 34.34 KB
  Лабораториялық жұмыс Тақырыбы: Өрістік транзистор негізіндегі кең жолақты күшейткіштің резисторлы каскадын зерттеу. Жұмыстың мақсаты: Жалпы бастау бойынша жалғанған өрістік транзистор негізіндегі кең жолақты күшейткіш каскады элементтерінің схема көрсеткіштеріне...
12513. Изучение движения тела под действием силы тяжести и силы упругости 245.24 KB
  Практическая работа № 9 Тема работы: Изучение движения тела под действием силы тяжести и силы упругости Тема для изучения: Закон сохранения механической энергии для системы тел в которой действуют потенциальные силы. Цель: сравнить максимальное изменение потен
12514. Программно-целевое планирование и его использование в сфере услуг 50 KB
  Программно-целевое планирование – это один из видов планирования, в основе которого лежит ориентация деятельности на достижение поставленных целей. По сути, любой метод планирования направлен на достижение каких-либо конкретных целей. Но в данном случае в основе самого процесса планирования лежит определение и постановка целей и лишь затем подбираются пути их достижения.
12515. ИССЛЕДОВАНИЕ ЧАСТОТНО УПРАВЛЯЕМОГО ЭЛЕКТРОПРИВОДА С АВТОНОМНЫМ ИНВЕРТОРОМ 3.21 MB
  ИССЛЕДОВАНИЕ ЧАСТОТНО УПРАВЛЯЕМОГО ЭЛЕКТРОПРИВОДА С АВТОНОМНЫМ ИНВЕРТОРОМ Методические указания к учебноисследовательской лабораторной работе по курсу Автоматизированный электропривод для студентов горнонефтяного факультета специальности 180400 ЭАПУ Лаборат
12516. ИЗМЕРЕНИЕ И АНАЛИЗ ОБЩИХ ВИБРАЦИЙ 370.5 KB
  ИЗМЕРЕНИЕ И АНАЛИЗ ОБЩИХ ВИБРАЦИЙ Цель работы: 1 закрепить основные теоретические положения о вибрации как об опасном и вредном производственном факторе; 2 научиться оценивать вибрации на рабочих местах и определять эффективность виброизоляции.