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).

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

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

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

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

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


 

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

1388. Учебник по дэйтрейдингу 1.62 MB
  Биржевая торговля — профессия, не похожая на другие, — требует уникального набора навыков и полнейшей самодисциплины. Независимо от того, каким личным или профессиональным опытом вы обладаете, когда вы впервые приступаете к торговле, вам приходится начинать с самого первого шага.
1389. Основы гидравлики 1.82 MB
  Общие сведения о жидкости. Жидкость как физическое тело. Растворимость газов в капельных жидкостях. Неньютоновские жидкости. Сила давления на криволинейную поверхность, погружённую в жидкость. Истечение жидкости из отверстий и насадков.
1390. Лингвистические аспекты теории перевода 1.89 MB
  Р. Якобсон О лингвистических аспектах перевода. М. А.К.Хэллидей Сопоставление языков. Основы теории закономерных соответствий. Грамматические трансформации и перевод некоторых синтаксических конструкций. К вопросу о типах межъязыковых лексических соответствий. П. Рикер Парадигма перевода.
1391. Стратегический менеджмент: целевое управление персоналом организаций 1.92 MB
  Механизм управления персоналом организаций в сфере материального производства на основе применения сверхдемократичной и одновременно сверхжесткой квалиметрической оценки персонала предприятия.
1392. Лекции по общей патологической анатомии 2.08 MB
  ВВЕДЕНИЕ В КУРС ПАТОЛОГИЧЕСКОЙ АНАТОМИИ. ЭТАПЫ РАЗВИТИЯ ПАТОЛОГИЧЕСКОЙ АНАТОМИИ. СОДЕРЖАНИЕ, ЗАДАЧИ, ОБЪЕКТЫ И МЕТОДЫ ИССЛЕДОВАНИЯ. ВОСПАЛЕНИЕ: ОПРЕДЕЛЕНИЕ, СУЩНОСТЬ, БИОЛОГИЧЕСКОЕ ЗНАЧЕНИЕ. МЕДИАТОРЫ ВОСПАЛЕНИЯ. МЕСТНОЕ И ОБЩЕЕ ПРОЯВЛЕНИЯ ВОСПАЛЕНИЯ. ОСТРОЕ ВОСПАЛЕНИЕ: ЭТИОЛОГИЯ, ПАТОГЕНЕЗ. МОРФОЛОГИЧЕСКОЕ ПРОЯВЛЕНИЕ ЭКССУДАТИВНОГО ВОСПАЛЕНИЯ. ИСХОДЫ ОСТРОГО ВОСПАЛЕНИЯ.
1393. Международный маркетинг, книга 2.21 MB
  ПРЕДПОСЫЛКИ СТАНОВЛЕНИЯ И РАЗВИТИЯ МЕЖДУНАРОДНОГО МАРКЕТИНГА. Основные факторы глобализации мировой экономики. Локальный и глобальный товарный знак. ВЛИЯНИЕ ИНТЕРНЕТА НА ЦЕНОВУЮ ПОЛИТИКУ НА ВНЕШНЕМ РЫНКЕ. Специфические особенности международной рекламы.
1394. Математика управления капиталом Методы анализа риска для трейдеров и портфельных менеджеров 2.36 MB
  Некоторые распространенные ложные концепции. Измерение степени пригодности системы для реинвестирования посредством. Характеристики торговли фиксированной долей и полезные методы. Параметрическое оптимальное f при нормальном распределении.
1395. Общая физика 2.36 MB
  Вектора углового перемещения, угловой скорости и ускорения. Производная единичного вектора (при его повороте). Нормальное и касательное ускорения. Центр инерции системы тел. Теорема о движении центра инерции. Закон сохранения импульса. Работа. Кинетическая энергия. Закон сохранения кинетической энергии. Мощность. Следствия из преобразований Лоренца: длины тел и промежутки времени.
1396. Advanced Animation with DirectX 2.43 MB
  Simulating Cloth and Soft Body Mesh Animation. Using Particles in Animation. Blending Morphing Animations. Timing in Animation and Movement. The source filter uses a single interface to represent a collage of filter objects.