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

-

 

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


 

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

30367. История кратких прилагательных в РЯ и современное состояние 60 KB
  История кратких прилагательных в РЯ и современное состояние Краткие прилагательные первичны а полные вторичны. Исторически прилагательные вторичные слова своим происхождением связанные с существительными. Следующее изменение: образование полных прилагательных краткие местоимения jь j je Краткие: непроизводные первообразные: белъ худъ производные: Основа именная или глагольная суффиксы Суффиксы качественных прилагательных: ък ьк ик: узъкъ далькъ великъ ьн: ясьнъ тьмьнъ ьл: кысьлъ тепьлъ ав: величавъ...
30368. Понятие лексического значения слова 51 KB
  Лексическое значение слова это отражение в слове явлений реальной действительности В. ЛЗС это закреплённое в сознании говорящих соотнесенного звукового комплекса языковой единицы с тем или иным явлением действительности большинство слов называют предметы их признаки количество действия процессы и выступают как полнозначные самостоятельные слова выполняя в языке номинативную функцию. Значение слова отражает только различные признаки т.
30369. Понятие ЧП в свете современной концепции организации предложения 49.5 KB
  Важна дифференциация ГЧП и ВЧП. Второстепенные члены предложения ВЧП. Потебня строит классификацию ВЧП психологическое направление в основе синтаксиса предложение психологическое явление на их соответствие частям речи. В частности Пешковский: следует говорить не о ВЧП а о согласуемых управляемых и примыкающих ЧП.
30370. Предложение как коммуникативная единица. Актуальное членение предложений, средства его выражения. Понятие высказывания 38.5 KB
  Одним из свойств предложения является порядок слов то есть их определённая последовательность. Таким образом все предложения кроме синтаксической структуры имеют деление на логическое подлежащее предмет речи и логическое сказуемое признак. В конечном счёте чешский учёный Вильям Матезиус сказал что деление предложения на две части имеет чисто языковой смысл. Это коммуникативное членение предложения.
30371. Понятие об осложненном предложении. Спорные вопросы теории. Виды осложнения 50 KB
  К понятию осложненного предложения относится: предложения с однородными членами предложения с обособленными членами предложения с вводными и вставными конструкциями предложения с обращением Степень осложнения разная нужно основание для их объединения. Осложнение в семантической структуре предложения диктум и модус Осложнение диктума Я смотрю на звезды; монопредикативное монопропозитивное Я слушаю пенье соловья монопредикативное 2 пропозиции осложнение семантики которое не влечет за собой синтаксическое осложнения Соловей...
30372. Языковой статус сложного предложения. Основные типы СП. ССП 80.5 KB
  Языковой статус сложного предложения. Понятие сложного предложения является основополагающим в синтаксисе. В теории сложного предложения существует множество дискуссионных вопросов в частности вопрос об объёме СП о границах между простым и сложным предложением о понятиях сочинения и подчинения в СП и др. На основе анализов частей сложного предложения можно сделать вывод что поскольку очень часто материальные элементы простых предложений совпадают с материальными элементами сложного предложения СП это сумма нескольких простых предложений.
30373. Технические средства САПР и их развитие 139.5 KB
  Рассматриваются архитектуры ЭВМ в зависимости от последовательности обработки данных. Представляются классы ЭВМ в зависимости от множественности одиночности потоков команд и данных ОКОД ОКМД МКМД. Основное назначение лекции дать более глубокие знания по техническому обеспечению САПР: архитектуры ЭВМ в зависимости от последовательности обработки данных и классы ЭВМ в зависимости от множественности одиночности потоков команд и данных 6. Усложнение решаемых задач и вычислительных алгоритмов САПР привело к внедрению в эту область более...
30374. Технические средства САПР и их развитие. Периферийное оборудование САПР 159 KB
  Каждый метод и устройства реализующие его имеют свои достоинства и недостатки. По программному обслуживанию периферийные устройства САПР делятся на два класса: растровые и координатные векторные. В растровых устройствах выводится мозаичный рисунок из отдельных точек пикселей или ПЭЛов от англ. Все периферийные устройства делятся на три основные группы: средства ввода вывода с машинных носителей; средства ввода вывода с документов; средства непосредственного взаимодействия с ЭВМ.