22119

Операции в алгебре событий

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Дизъюнкцией событий S1 S2 Sk называют событие S = S1vS2vvSk состоящее из всех слов входящих в события S1 S2 Sk. Произведением событий S1 S2 Sk называется событие S = S1 S2 Sk состоящее из всех слов полученных приписыванием к каждому слову события S1 каждого слова события S2 затем слова события S3 и т. слова входящие в события S1S2 и S2S1 различны: т. Итерацией события S называется событие{S} состоящее из пустого слова e и всех слов вида S SS SSS и т.

Русский

2013-08-04

24.5 KB

3 чел.

Лекция 5

Операции в алгебре событий.

Алгебра событий включает три операции:

  •  Дизъюнкцию (объединение) событий;
  •  Произведение событий;
  •  Итерацию событий.

Дизъюнкцией событий S1, S2, …, Sk называют событие S = S1vS2v…vSk, состоящее из всех слов, входящих в события S1, S2, …, Sk.

Пример.  Событие S1 содержит слова x1, x2x1, x1x1,т.е. S1 = (x1, x2x1, x1x1), а S2 = (x2, x1x2). Тогда S = S1vS2 = (x1, x2, x1x1, x1x2, x2x1).

 Произведением событий S1, S2, …, Sk называется событие S = S1* S2* …,*Sk, состоящее из всех слов , полученных приписыванием к каждому слову события S1 каждого слова события S2, затем слова события S3 и т.д.

 Пример. S1и S2 те же. S = S1*S2 = (x1x2, x1x1x2, x2x1x2, x2x1x1x2, x1x1x2, x1x1x1x2). Произведение событий не коммутативно, т.е. слова, входящие в события S1S2 и S2S1 различны: т.е. S1S2S2S1 . Поскольку произведение не коммутативно, следует различать операции «умножение справа» и «умножение слева». Например, относительно произведения событий S1S2 можно сказать, что событие S2 умножено на событие S1справа, а событие S1на S2 слева.

Третьей операцией, применяемой в алгебре событий, является одноместная операция итерация, которая применима только к одному событию. Для обозначения итерации вводят фигурные скобки, которые называются итерационными.

Итерацией события S называется событие{S}, состоящее из пустого слова e и всех слов вида S, SS, SSS и т.д. до бесконечности. Т.е. {S} = e v S v SS v SSS v….

 Пример. S = (x2, x1x2).  

{S} = (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …)

 При синтезе конечных автоматов важнейшую роль играют регулярные события. Пусть дан конечный алфавит X = (x1, x2, …, xm).

Определение. Любое событие, которое можно получить из букв данного алфавита с помощью конечного числа операции дизъюнкции, произведения и итерации, называется регулярным событием, а выражение, составленное с помощью этих операций – регулярным выражением.

 Очевидно любое событие, состоящее из конечного множества слов, является регулярным. Действительно, такие события можно представить в виде дизъюнкции всех входящих в него слов, образованных из букв заданного алфавита с помощью операции умножения. События, состоящие из бесконечного числа слов, могут быть как регулярными, так и не регулярными.

Теорема. Любые регулярные выражения и только они представимы в конечных автоматах.

Из этой теоремы следует, что любой алгоритм преобразования информации, который можно записать в виде регулярного выражения, реализуется конечным автоматом. С другой стороны, любые конечные автоматы реализуют только те алгоритмы, которые могут быть записаны в виде регулярных выражений.

Рассмотрим, как можно совершить переход от описательной формы задания алгоритмов работы конечных автоматов к представлению этих алгоритмов в виде регулярных выражений. С целью упрощения такого перехода вводят основные события, из которых с помощью операций дизъюнкции, умножения и итерации можно составить более сложные события, соответствующие заданному алгоритму работы автомата. За основные события принимают такие события, которые более часто встречаются в инженерной практике при синтезе схем ЦВМ.


 

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

27085. SCM 95.29 KB
  supply chain management SCM организационная стратегия и прикладное программное обеспечение предназначенные для автоматизации и управления всеми этапами снабжения предприятия и для контроля всего товародвижения. SCMсистемы охватывает весь товарный цикл: закупку сырья производство распространение товара. Выделяется шесть основных областей на которых сосредоточено управление цепями поставок: производство поставки месторасположение запасы транспортировка и информация В составе SCMсистемы можно условно выделить две подсистемы: SCP ...
27086. Информация в бизнесе. Информационная поддержка бизнеса 15.71 KB
  Информация сведения об объектах и явлениях окружающей среды их параметрах свойствах и состоянии которые воспринимают информационные системы живые организмы управляющие машины и др. Финансовоуправленческие системы включают подкласс малых интегрированных систем. Такие системы предназначены для ведения учета по одному или нескольким направлениям бухгалтерия сбыт склад кадры и т. Системы этого класса обычно универсальны цикл их внедрения невелик иногда можно воспользоваться коробочным вариантом купив программу и самостоятельно...
27087. Документооборот 14.98 KB
  Следует отметить что в этом определении упор делается на словах движение документов то есть их пути из одного подразделения или от одного сотрудника к другому. Автоматизация позволяет сократить время на обработку документов а также снижает риски случайной потери данных кроме того СЭД позволяет руководству контролировать выполнение управленческих решений. Возможность параллельного выполнения операций позволяющая сократить время движения документов и повышения оперативности их исполнения Непрерывность движения документа позволяющая...
27088. Корпоративная информационная система(КИС) 12.02 KB
  Основными блоками корпоративных информационных систем являются: система хранения база данных хранилище; система сбора и концентрации информации; системы поддержки принятия решений – бизнеслогика базируется на обработке; специальные взаимодействия.
27089. ОСНОВНІ ВІДОМОСТІ ПРО ВАГОНИ. ТИПИ, ЗАГАЛЬНА БУДОВА, ТЕХНІКО-ЕКОНОМІЧНІ ПОКАЗНИКИ ВАГОНІВ. ПОЗНАЧКИ ТА НАДПИСИ НА ВАГОНАХ 337.5 KB
  Типи та конструкції сучасних вантажних, пасажирських та рефрижераторних вагонів являють собою доволі складну інженерну побудову. Тому інженери, що працюють в системі вагонного господарства залізничного транспорту та в вагонній промисловості, повинні добре знати конструкцію вагонів
27090. Архитектура CRM систем 91.83 KB
  архитектура CRM систем CRMсистема Customer Relationship Management System система управления взаимодействием с клиентами корпоративная информационная система предназначенная для улучшения обслуживания клиентов путём сохранения информации о клиентах и истории взаимоотношений с клиентами установления и улучшения бизнеспроцедур на основе сохранённой информации и последующей оценки их эффективности. Её основные принципы таковы: наличие единого хранилища информации откуда в любой момент доступны все сведения обо всех случаях...
27091. Архитектура erp систем 35.49 KB
  архитектура erp систем В начале 1990х гг. Системы класса MRPII в интеграции с модулемфинансового планирования Finance Requirements Planning FRP получили название систем планирования ресурсов предприятийEnterprise Resource Planning ERP. В основе ERPсистем лежит принцип создания единого хранилища репозитория данных содержащего всю корпоративную бизнесинформацию: плановую и финансовую информацию производственные данные данные по персоналу и др. Целью ERPсистем является не только улучшение управления производственной деятельностью...
27093. Организация процессов обработки данных в базе данных: формы, запросы, отчеты 38 KB
  Основными компонентами объектами базы данных являются таблицы запросы формы отчеты макросы и модули.Таблица фундаментальная структура системы управления реляционными базами данных. В Microsoft Access таблица это объект предназначенный для хранения данных в виде записей строк и полей столбцов.