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

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

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

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

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

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


 

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

82671. Понятие, виды, признаки преступлений против интеллектуальной собственности 67 KB
  Интеллектуальные права на результаты исполнительской деятельности (исполнения), на фонограммы, на сообщение в эфир или по кабелю радио- и телепередач (вещание организаций эфирного и кабельного вещания), на содержание баз данных, а также на произведения науки, литературы и искусства...
82672. Роль и значение биофабрик 17.71 KB
  Биофабрики располагают значительной территорией специальными производствами лабораторными корпусами и вспомогательными сооружениями. Государственный контроль выпускаемой продукции на её безвредность чистоту специфичность и активность осуществляет контрольная лаборатория Биофабрики возглавляемая...
82673. Особливості майнових прав авторів творів 51.78 KB
  Предмет дослідження загальна характеристика майнових прав автора твору. Мета роботи зумовлює виконання таких завдань: 1 дати визначення основним майновим правам автора твору; 2 охарактеризувати основні майнові прав автора.
82674. Велик Вітчизняна війна 85.63 KB
  Міжнародна обстановка і зовнішня політика СРСР напередодні другої світової війни. У цій війні вирішувалася не тільки доля СРСР але і майбутнє світової цивілізації прогресу і демократії. У тих умовах спроби СРСР Великобританії та Франції створити систему повної безпеки в Європі з метою нейтралізації...
82675. Рекомендацій щодо поліпшення умов праці на виробництві 92.09 KB
  На сучасному етапі розвитку України спостерігається загострення проблем в області організації нормальних умов праці. Це зумовлено тим, що значна частина працівників працює у шкідливих або важких умовах. Тому проблема покращення умов праці для будь-якого підприємства є актуальною.
82676. Система правових засобів захисту права власності 48.59 KB
  Суспільство не може існувати без тих чи інших відносин власності: ці відносини визначають його економічну структуру, ідеологічне, моральне і політичне обличчя, тому даний аспект правового регулювання посідає важливе місце у загальній структурі суспільних правовідносин та є актуальним у процесі...
82677. Заболевания верхних дыхательных путей и их осложнения 31.46 KB
  Провоцируются эти заболевания как правило местным или общим переохлаждением на фоне ослабленного иммунитета или перенапряжения организма. Причиной заражения при этих заболеваниях может быть инфицирование от больного человека вирусной и бактериальной инфекцией.
82678. Our Homeland – Kazakstan 22.31 KB
  The Constitution defines the state system as a form of presidential republic considering it the most flexible version in conditions of today. The President ensures coordinated performance of all the branches of state power and accountability of power bodies to the people.
82679. Торговые и неторговые автоматы. Промышленные роботы и манипуляторы 25.61 KB
  Промышленный робот - автономное устройство состоящее из механического манипулятора и перепрограммируемой системы управления которое применяется для перемещения объектов в пространстве и для выполнения различных производственных процессов.