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

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

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

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

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

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


 

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

65745. ОСОБЛИВОСТІ ФОРМУВАННЯ ТЕРАПЕВТИЧНОГО АЛЬЯНСУ У МЕДИЧНОМУ ЗАКЛАДІ ПСИХОНЕВРОЛОГІЧНОГО ПРОФІЛЮ 236 KB
  У зв’язку з реформуванням системи охорони здоров’я зміною характеру відносин між лікарем і пацієнтом упровадженням принципу партнерства у їх взаємодію значною мірою зростає увага до проблеми терапевтичного альянсу В. Проблематику терапевтичного альянсу розглянуто лише в поодиноких наукових...
65746. СОЦІАЛЬНО-ПЕДАГОГІЧНА ПРОФІЛАКТИКА ДЕВІАНТНОЇ ПОВЕДІНКИ ПІДЛІТКІВ У ДІЯЛЬНОСТІ ЗАГАЛЬНООСВІТНЬОЇ ШКОЛИ 183.5 KB
  Незважаючи на те що до проблеми профілактики девіантної поведінки прикуто увагу багатьох науковців кількість девіантних підлітків не припиняє зростати. Спроби ефективної профілактики девіантної поведінки підлітків ускладнені тим що в практичній діяльності загальноосвітньої школи...
65747. Стратегия управления качеством на предприятии на основе стандартов ИСО 182.5 KB
  ИСО предполагает создание системы постоянного контроля качества, которая задействована на всех этапах производства продукции или оказания услуг. Ориентируясь на принципы управления качеством по ИСО, компания декларирует стремление к постоянному совершенствованию качества своей продукции и оптимизации управленческих процессов.
65748. Лизинг как современное направление финансирования бизнеса в России на примере ОАО «Московский завод химконцентратов» 1.22 MB
  Лизинговая операция выгодна всем участвующим: одна сторона получает кредит, который выплачивает поэтапно, и нужное оборудование; другая сторона – гарантию возврата кредита, так как объект лизинга является собственностью лизингодателя или банка...
65749. Учет продукции основного молочного стада и анализ ее производства в современных условиях хозяйствования на примере СПК «Прогресс-Вертелишки» 642.5 KB
  Целью данной дипломной работы является разработка теоретических и практических рекомендаций по совершенствованию учета продукции молочного стада, а также анализ эффективности производства молока в современных условиях хозяйствования и выявление резервов его увеличения.
65750. Изучение рекреационных ресурсов побережья северо-западного Причерноморья 8.59 MB
  Упоминания о природе Черного моря встречаем в римских церковных и арабских хрониках и в описаниях арабских путешественников. Начиная с IVV веков описания Черного моря встречаем в славянских и византийских летописях в сказаниях норманнов и прибалтийских народов.
65753. Терроризмге қарсы күресудің ғылыми-теориялық аспектілері 513.5 KB
  Қазақстан Республикасы терроризммен күресудегі басқа мемлекеттермен ынтымақтасуы. Өткен XX ғасыр ғылым мен технологиядағы бас айналдырар жылдамдықтағы жаңалықтардың ғасыры ғана емес сонымен қатар 100 миллионға тарта адамдар құрбан болған...